2 Sets and functions 2.15 Transpositions Further reading

2.16 Sign

2.16.1 Definition of odd and even permutations

Theorem 2.15.3 says that every permutation can be expressed as a product of transpositions.

Definition 2.16.1.

A permutation is odd if it can be expressed as a product of an odd number of transpositions and even if it can be expressed as a product of an even number of transpositions.

(Sometimes people refer to the parity of a permutation to mean whether it is odd or even.)

Example 2.16.1.

•

$(1,2)$ is odd.
•

$\operatorname{id}=(1,2)(1,2)$ is even.
•

$(1,2,3)=(1,2)(2,3)$ is even.
•

The expression for an $m$ -cycle $a=(a_{1},\ldots,a_{m})$ as a product of $m-1$ transpositions

$(a_{1},\ldots,a_{m})=(a_{1},a_{2})(a_{2},a_{3})\cdots(a_{m-1},a_{m})$

in Lemma 2.15.2 shows that an $m$ cycle is even if $m$ is odd and odd if $m$ is even.

2.16.2 The odd xor even theorem

It seems possible that a permutation could be odd AND even at the same time, but this isn’t the case. The proof is a little strange because it involves a seemingly-unrelated polynomial — if you prefer a proof that refers only to permutations, take a look at the unassessed exercises.

Theorem 2.16.1.

No permutation is both odd and even.

Proof.

Let $s\in S_{n}$ . If $s$ could be written both as a product of an even number and an odd number of transpositions, say

s=t_{1}t_{2}\cdots t_{2a}=t^{\prime}_{1}t^{\prime}_{2}\cdots t^{\prime}_{2b+1}

then we could rearrange to get

\operatorname{id}=t_{2a}t_{2a-1}\cdots t_{2}t_{1}t^{\prime}_{1}t^{\prime}_{2}% \cdots t^{\prime}_{2b+1}

which expresses the identity permutation as a product of an odd number $2(a+b)+1$ of transpositions. So it’s enough to show that this is impossible.

Introduce variables $x_{1},x_{2},\ldots,x_{n}$ . Given any polynomial $f$ in these variables and any permutation $s\in S_{n}$ , we define a new polynomial $s(f)$ which is obtained by replacing every variable $x_{i}$ in $f$ by $x_{s(i)}$ . For example, if $s=(1,2,3)$ and $f=x_{1}x_{2}+x_{3}^{4}+x_{5}$ then

	$\displaystyle s(f)$	$\displaystyle=x_{s(1)}x_{s(2)}+x_{s(3)}^{4}+x_{s(5)}$
		$\displaystyle=x_{2}x_{3}+x_{1}^{4}+x_{5}.$

Now define

\Delta_{n}=\prod_{1\leqslant i<j\leqslant n}(x_{i}-x_{j})

so that, for example,

\Delta_{3}=(x_{1}-x_{2})(x_{1}-x_{3})(x_{2}-x_{3}).

Let $t=(a,b)$ be any transposition, where $a<b$ . We have $t(\Delta_{n})=-\Delta_{n}$ , because $t$ only affects factors of $\Delta_{n}$ containing $x_{a}$ or $x_{b}$ , and the only factors to change sign are $(x_{a}-x_{i})$ with $a<i\leqslant b$ and $(x_{i}-x_{b})$ with $a\leqslant i<b$ , a total of $2(b-a)-1$ sign changes (as $(x_{a}-x_{b})$ appears in both cases). It follows that any product of an odd number of transpositions sends $\Delta_{n}$ to $-\Delta_{n}$ . Since the identity sends $\Delta_{n}$ to $\Delta_{n}$ , it cannot be written as the product of an odd number of transpositions. ∎

2.16.3 Sign of a permutation

Definition 2.16.2.

•

The sign of a permutation is $1$ if it is even and $-1$ if it is odd.
•

We write $\operatorname{sign}(s)$ for the sign of the permutation $s$ .

So if $s$ can be written as a product of $m$ transpositions, $\operatorname{sign}(s)=(-1)^{m}$ .

Lemma 2.16.2.

For any two permutations $s$ and $t$ , $\operatorname{sign}(st)=\operatorname{sign}(s)\operatorname{sign}(t)$

Proof.

If $s$ can be written as a product of $m$ transpositions and $t$ can be written as a product of $n$ transpositions, then $s t$ can be written as a product of $m+n$ transpositions. So

	$\displaystyle\operatorname{sign}(st)$	$\displaystyle=(-1)^{n+m}$
		$\displaystyle=(-1)^{m}(-1)^{n}$
		$\displaystyle=\operatorname{sign}(s)\operatorname{sign}(t)$

∎

This rule about the sign of a product means that

•

an even permutation times an even permutation is even,
•

an even permutation times an odd permutation is odd, and
•

an odd permutation times an odd permutation is even

just like when we multiply odd and even integers.

2.16.4 Two results on the sign of a permutation

Lemma 2.16.3.

1.

Even length cycles are odd and odd length cycles are even.
2.

If $s$ is any permutation, $\operatorname{sign}(s)=\operatorname{sign}(s^{-1})$ .

Proof.

1.

We saw in the proof of Lemma 2.15.2 that if $a=(a_{1},\ldots,a_{m})$ is any $m$ -cycle,

$(a_{1}\ldots,a_{m})=(a_{1},a_{2})(a_{2},a_{3})\cdots(a_{m-1},a_{m})$

so an $m$ -cycle can be written as a product of $m-1$ transpositions. The number of transpositions in this expression therefore has the opposite parity to $m$ , as required.
2.

If $s=t_{1}\cdots t_{m}$ is a product of $m$ transpositions, $s^{-1}=t_{m}^{-1}\cdots t_{1}^{-1}$ . But the inverse of a transposition is a transposition, so $s^{-1}$ is also the product of $m$ transpositions.

∎

Another way to express the first part of this lemma would be to say that $\operatorname{sign}(a_{1},\ldots,a_{m})=(-1)^{m-1}$ .