2 Sets and functions 2.16 Transpositions Further reading

2.17 Sign

2.17.1 Definition of odd and even permutations

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

Definition 2.17.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. We won’t do this since we want to save the word parity for integers.)

Example 2.17.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_{0},\ldots,a_{m-1})$ as a product of $m-1$ transpositions

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

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

2.17.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.

Theorem 2.17.1.

No permutation is both odd and even.

To prove this we need to do a little work.

Lemma 2.17.2.

For any $k,l\geqslant 0$ and any distinct numbers $a,b,x_{1},\ldots,x_{k},y_{1},\ldots,y_{l}$ we have

(a,b)(a,x_{1},\ldots,x_{k},b,y_{1},\ldots,y_{l})=(a,x_{1},\ldots,x_{k})(b,y_{1% },\ldots,y_{l}).

Proof.

This will be a problem set exercise. ∎

We know every permutation can be written as a product of disjoint cycles. We are now going to be interested in how many cycles it takes to express a given permutation, and we will include all 1-cycles in our count. For example, in $S_{4}$ the identity $\operatorname{id}=(1)(2)(3)(4)$ has four cycles, the transposition $(1,2)=(1,2)(3)(4)$ has three cycles, the permutation

\begin{pmatrix}1&2&3&4\\ 2&3&1&4\end{pmatrix}=(1,2,3)(4)

has two cycles as does $(1,2)(3,4)$ , and the permutation $(1,2,3,4)$ has one cycle only.

Lemma 2.17.3.

If $s\in S_{n}$ has $r$ cycles and $t$ is a transposition then $t s$ has $r+1$ or $r-1$ cycles.

Proof.

Let $s=c_{1}c_{2}\cdots c_{r}$ be a disjoint cycle decomposition for $s$ , remembering that we include any 1-cycles in this product so that each number between 1 and $n$ appears in exactly one of these cycles.

Let $t=(a,b)$ . There are two possibilities: either $a$ and $b$ belong to the same $c_{i}$ , or they belong to different $c_{i}$ s.

In the first case, because disjoint cycles commute we can assume $a$ and $b$ belong to $c_{1}$ , which we can write as $(a,x_{1},\ldots,x_{k},b,y_{1},\ldots,y_{l})$ for some distinct numbers $x_{i}$ and $y_{j}$ . Lemma 2.17.2 then shows us that

ts=(a,x_{1},\ldots,x_{k})(b,y_{1},\ldots,y_{l})c_{2}\cdots c_{r}

has $r+1$ cycles.

In the second case, because disjoint cycles commute we can assume $a$ belongs to $c_{1}$ and $b$ to $c_{2}$ . Write the disjoint cycles $c_{1}$ as $(a,x_{1},\ldots,x_{k})$ and $c_{2}$ as $(b,y_{1},\ldots,y_{l})$ . Then multiplying Lemma 2.17.2 on the left by $(a,b)$ gives

(a,b)(a,x_{1},\ldots,x_{k})(b,y_{1},\ldots,y_{l})=(a,x_{1},\ldots,x_{k},b,y_{1% },\ldots,y_{k})

(2.4)

and so

ts=(a,x_{1},\ldots,x_{k},b,y_{1},\ldots,y_{k})c_{3}c_{4}\cdots c_{r}

has $r-1$ cycles. ∎

Let’s consider two examples to illustrate the two cases in this proof. Take $n=7$ , $t=(1,2)$ , $c_{1}=(1,4,2,3)$ , $c_{2}=(5,7)$ , $c_{3}=(6)$ , and

s=c_{1}c_{2}c_{3}=(1,4,2,3)(5,7)(6)

so the number $r$ of cycles in $s$ is equal to 3. We are in the first case of the proof since 1 and 2 both belong to the same cycle $c_{1}$ from $s$ . You can check that

(1,2)(1,4,2,3)=(1,4)(2,3)

so that

ts=(1,4)(2,3)(4,7)(6)

has $r+1=4$ cycles.

Next take $n=7$ , $t=(1,2)$ and $c_{1}=(1)$ , $c_{2}=(3,6,4)$ , $c_{3}=(5,2,7)$ , and

s=c_{1}c_{2}c_{3}=(1)(3,6,4)(5,2,7)

so the number $r$ of cycles in $s$ is again 3. We are in the second case of the proof since 1 and 2 belong to $c_{1}$ and $c_{3}$ . Rewriting $c_{3}$ as $(2,7,5)$ and using the identity (2.4),

(1,2)(1)(2,7,5)=(1,2,7,5)

(you should check this by computing the left hand side). It follows

$\displaystyle ts$	$\displaystyle=tc_{1}c_{2}c_{3}$
	$\displaystyle=tc_{1}c_{3}c_{2}$	disjoint cycles commute
	$\displaystyle=(1,2)(1)(2,7,5)(3,6,4)$
	$\displaystyle=(1,2,7,5)(3,6,4)$

and $t s$ has $r-1=2$ cycles.

The parity of an integer is whether it is even or odd. Two integers are said to have the same parity if they are either both even or odd, otherwise they are said to have the opposite parity.

Lemma 2.17.4.

Let $t=t_{1}\cdots t_{k}$ be a product of transpositions, each of which belongs to $S_{n}$ . If $n$ is even then the number of cycles in $t$ has the same parity as $k$ , and if $n$ is odd then the number of cycles in $t$ has the opposite parity to $k$ .

For example, let $n$ be the odd number 3. In $S_{3}$ the product $(1,2)(2,3)(1,2)$ of two transpositions is equal to $(1,3)(2)$ which has two cycles. The parity of the number of cycles is opposite to the parity of $k$ , and the same is true of any product of transpositions in $S_{n}$ for any odd $n$ . Now let $n$ be the even number 4. In $S_{4}$ the product $(1,2)(3,4)(2,3)(1,4)$ of four transpositions is equal to $(1,3)(2,4)$ which has two cycles. The parity of the number of cycles is the same as the parity of $k$ , and the same is true of any product of transpositions in $S_{n}$ for any even $n$ .

Proof.

We will do the case when $n$ is even, the odd case being similar. We prove by induction on $k$ that the number of cycles in $t_{1}t_{2}\cdots t_{k}$ has the same parity as $k$ . The base case is $k=1$ when the product is just $t_{1}$ which has $n-1$ cycles (the 2-cycle from $t_{1}$ and then $n-2$ one-cycles), an odd number of cycles.

For example, if $n=6$ then $t_{1}$ might be

(2,4)=(1)(2,4)(3)(5)(6)

which has five cycles.

For the inductive step, consider a product $t_{1}t_{2}\cdots t_{k}$ . If $k$ is even then $k-1$ is odd, so by the inductive hypothesis $t_{2}\cdots t_{k}$ has an odd number $r$ of cycles, and by Lemma 2.17.3 $t_{1}t_{2}\cdots t_{k}$ has $r+1$ or $r-1$ cycles, which in either case is an even number. If $k$ is odd then $k-1$ is even, so by the inductive hypothesis $t_{2}\cdots t_{k}$ has an even number $r$ of cycles and then by the same Lemma as before $t_{1}\cdots t_{k}$ has $r\pm 1$ cycles, an odd number. ∎

Finally we can prove the main theorem, that no permutation is both odd and even.

Proof.

Suppose $n$ is even and we can write $s\in S_{n}$ as a product of $k$ transpositions, and also as a product of $k^{\prime}$ transpositions. Lemma 2.17.4 shows that both $k$ and $k^{\prime}$ has the same parity as the number of cycles in $s$ , in particular, $k$ and $k^{\prime}$ have the same parity. The argument for odd $n$ is similar. ∎

2.17.3 Sign of a permutation

Definition 2.17.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.17.5.

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.17.4 Two results on the sign of a permutation

Lemma 2.17.6.

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.16.1 that if $a=(a_{0},\ldots,a_{m-1})$ is any $m$ -cycle,

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

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_{0},\ldots,a_{m-1})=(-1)^{m-1}$ .