Permutation/Sign/Introduction/Section

Definition

Let ${}M=\{1,\ldots ,n\}$ and let ${}\pi$ be a permutation on ${}M$. Then we call the number

${}\operatorname {sgn} (\pi )=\prod _{i<j}{\frac {\pi (j)-\pi (i)}{j-i}}\,$

the sign of the permutation ${}\pi$.

The sign is ${}1$ or ${}-1$, because in the numerator and in the denominator, up to sign, the same differences ${}\pm (j-i)$ occur. Thus, for the sign, there are only two possible values. For ${}\operatorname {sgn} (\pi )=1$, we say that ${}\pi$ is an even permutation, and for ${}\operatorname {sgn} (\pi )=-1$, we say that ${}\pi$ is an odd permutation.

Definition

Let ${}M=\{1,\ldots ,n\}$ and let ${}\pi$ be a permutation on ${}M$. We call an index pair

${}i<j\,$

an inversion (of ${}\pi$), if ${}\pi (i)>\pi (j)$

holds.

Lemma

Let ${}M=\{1,\ldots ,n\}$ and let ${}\pi$ be a permutation on ${}M$. Let ${}k={\#\left(F\right)}$ denote the number of inversions of ${}\pi$. Then the sign of ${}\pi$ equals

${}\operatorname {sgn} (\pi )=(-1)^{k}\,.$

Proof

We write

${}{\begin{aligned}\operatorname {sgn} (\pi )&=\prod _{i<j}{\frac {\pi (j)-\pi (i)}{j-i}}\\&=\prod _{(i,j)\in F}{\frac {\pi (j)-\pi (i)}{j-i}}\prod _{(i,j)\not \in F}{\frac {\pi (j)-\pi (i)}{j-i}}\\&=(-1)^{k}\prod _{(i,j)\in F}{\frac {\pi (i)-\pi (j)}{j-i}}\prod _{(i,j)\not \in F}{\frac {\pi (j)-\pi (i)}{j-i}}\\&=(-1)^{k},\end{aligned}}$

because, after this reordering, we have in the numerator as well as in the denominator the product of all positive differences.

$\Box$

Example

We consider the permutation

${}x$	${}1$	${}2$	${}3$	${}4$	${}5$	${}6$
${}\sigma (x)$	${}2$	${}4$	${}6$	${}5$	${}3$	${}1$

with the cycle representation

$\langle 1,2,4,5,3,6\rangle .$

The inversions are

$(1,6),\,(2,5),\,(2,6),\,(3,4),\,(3,5),\,(3,6),\,(4,5),\,(4,6),\,(5,6),$

so there are ${}9$ of those. The sign is ${}(-1)^{9}=-1$ due to fact, and the permutation is odd.

The sign is a group homomorphism in the sense of the following definition.

Definition

Let ${}(G,\circ ,e_{G})$ and ${}(H,\circ ,e_{H})$ denote groups. A mapping

$\psi \colon G\longrightarrow H$

is called group homomorphism, if the equality

${}\psi (g\circ g')=\psi (g)\circ \psi (g')\,$

holds for all

${}g,g'\in G$.

Theorem

The sign mapping

$S_{n}\longrightarrow \{1,-1\},\pi \longmapsto \operatorname {sgn} (\pi ),$

is a

group homomorphism.

Proof

Let two permutations ${}\pi$ and ${}\rho$ be given. Then

${}{\begin{aligned}\operatorname {sgn} (\pi \circ \rho )&=\prod _{i<j}{\frac {(\pi \circ \rho )(j)-(\pi \circ \rho )(i)}{j-i}}\\&={\left(\prod _{i<j}{\frac {(\pi \circ \rho )(j)-(\pi \circ \rho )(i)}{\rho (j)-\rho (i)}}\right)}\prod _{i<j}{\frac {\rho (j)-\rho (i)}{j-i}}\\&={\left(\prod _{i<j,\,\rho (i)<\rho (j)}{\frac {\pi (\rho (j))-\pi (\rho (i))}{\rho (j)-\rho (i)}}\right)}{\left(\prod _{i<j,\,\rho (i)>\rho (j)}{\frac {\pi (\rho (j))-\pi (\rho (i))}{\rho (j)-\rho (i)}}\right)}\,\operatorname {sgn} (\rho )\\&={\left(\prod _{i<j,\,\rho (i)<\rho (j)}{\frac {\pi (\rho (j))-\pi (\rho (i))}{\rho (j)-\rho (i)}}\right)}{\left(\prod _{i<j,\,\rho (i)>\rho (j)}{\frac {\pi (\rho (i))-\pi (\rho (j))}{\rho (i)-\rho (j)}}\right)}\,\operatorname {sgn} (\rho )\\&=\prod _{k<\ell }{\frac {\pi (\ell )-\pi (k)}{\ell -k}}\operatorname {sgn} (\rho )\\&=\operatorname {sgn} (\pi )\operatorname {sgn} (\rho ).\end{aligned}}$

$\Box$

Lemma

Let ${}M=\{1,\ldots ,n\}$ and let ${}\pi$ be a permutation on ${}M$. Let

${}\pi =\tau _{1}\cdots \tau _{r}\,$

be written as a product of ${}r$ transpositions. Then the sign can be described as

${}\operatorname {sgn} (\pi )=(-1)^{r}\,.$

Proof

Suppose that the transposition ${}\tau$ swaps the numbers ${}k<\ell$. Then

${}{\begin{aligned}\operatorname {sgn} (\tau )&=\prod _{i<j}{\frac {\tau (j)-\tau (i)}{j-i}}\\&=\prod _{i<j,\,i,j\neq k,\ell }{\frac {\tau (j)-\tau (i)}{j-i}}\cdot \prod _{i<j,\,i=k,j\neq \ell }{\frac {\tau (j)-\tau (i)}{j-i}}\cdot \prod _{i<j,\,i\neq k,j=\ell }{\frac {\tau (j)-\tau (i)}{j-i}}\cdot \prod _{i<j,\,i=k,j=\ell }{\frac {\tau (j)-\tau (i)}{j-i}}\\&=\prod _{j>k,\,j\neq \ell }{\frac {j-\ell }{j-k}}\cdot \prod _{i\neq k,\,i<\ell }{\frac {k-i}{\ell -i}}\cdot {\frac {k-\ell }{\ell -k}}\\&=\prod _{j>\ell }{\frac {j-\ell }{j-k}}\cdot \prod _{i<k}{\frac {k-i}{\ell -i}}\cdot \prod _{k<j<\ell }{\frac {j-\ell }{j-k}}\cdot \prod _{k<i<\ell }{\frac {k-i}{\ell -i}}\cdot (-1)\\&=-1.\end{aligned}}$

The last equation follows from the fact that, in the first and the second product, all numerators and denominators are positive, and the fact that, in the third and in the forth product, the numerators are negative and the denominators are positive. Therefore, as the index sets of the third and the fourth product coincide, all the signs cancel each other.

The statement follows from the case of a transposition via the homomorphism property.

$\Box$

Remark

Let ${}I$ be an arbitrary set with ${}n$ elements, but without an ordering, and let ${}\pi$ be a permutation on ${}I$. Then we can not talk about inversions, and the definition of sign via products of differences is not directly applicable. However, we can look at fact in order to define the sign in this slightly more general situation. For this, we write ${}\pi$ as a product of ${}r$ transpositions and define

${}\operatorname {sgn} (\pi )={\begin{cases}1\,,{\text{ in case }}r{\text{ is even}}\,,\\-1\,,{\text{ in case }}r{\text{ is odd}}\,.\end{cases}}\,$

To see that this is well-defined, we consider a bijection

$\varphi \colon I\longrightarrow \{1,\ldots ,n\}.$

The permutation ${}\pi$ on ${}I$ defines on ${}\{1,\ldots ,n\}$ the permutation ${}\pi '=\varphi \pi \varphi ^{-1}$. Let ${}\pi =\tau _{1}\cdots \tau _{r}$ be a representation as a product of ${}r$ transpositions on ${}I$. Then

${}\pi '=\varphi \pi \varphi ^{-1}=\varphi \tau _{1}\cdots \tau _{r}\varphi ^{-1}=\varphi \tau _{1}\varphi ^{-1}\varphi \tau _{2}\varphi ^{-1}\varphi \cdots \varphi ^{-1}\varphi \tau _{r}\varphi ^{-1}=\tau _{1}'\tau _{2}'\cdots \tau _{r}'\,,$

where ${}\tau _{j}'=\varphi \tau _{j}\varphi ^{-1}$. These are also transpositions, so that the parity of ${}r$ is determined by the sign of ${}\pi '$.