signature of a permutation SignatureOfAPermutation 2003-02-26 00:32:47 2004-10-31 21:16:19 Definition transposition inversion signature parity even permutation odd permutation permutation \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsfonts} \PMlinkescapeword{proposition} Let $X$ be a finite set, and let $G$ be the group of permutations of $X$ (see permutation group). There exists a unique homomorphism $\chi$ from $G$ to the multiplicative group $\{-1,1\}$ such that $\chi(t)=-1$ for any transposition (loc. sit.) $t\in G$. The value $\chi(g)$, for any $g\in G$, is called the \emph{signature} or \emph{sign} of the permutation $g$. If $\chi(g)=1$, $g$ is said to be of even \emph{parity}; if $\chi(g)=-1$, $g$ is said to be of odd parity. \textbf{Proposition:} If $X$ is totally ordered by a relation $<$, then for all $g\in G$, \begin{equation} \chi(g)=(-1)^{k(g)} \end{equation} where $k(g)$ is the number of pairs $(x,y)\in X\times X$ such that $x<y$ and $g(x)>g(y)$. (Such a pair is sometimes called an \emph{inversion} of the permutation $g$.) \textbf{Proof:} This is clear if $g$ is the identity map $X\to X$. If $g$ is any other permutation, then for some \emph{consecutive} $a,b\in X$ we have $a<b$ and $g(a)>g(b)$. Let $h\in G$ be the transposition of $a$ and $b$. We have \begin{eqnarray*} k(g \circ h)&=&k(g)-1 \\ \chi(g \circ h)&=&-\chi(g) \end{eqnarray*} and the proposition follows by induction on $k(g)$.