## Group Theory I.5 (Parity of a Permutation)

First, we consider the special case of a cycle of length 2, (ab), which is a simple swap of two elements. Such a permutation is called a transposition. We already know that every permutation is a product of disjoint cycles. Furthermore, every cycle can be written as a product of transpositions:

(a1a2, …, ar) = (a1a2)(a2a3) … (ar-1ar)

This means:

Every permutation can be written as a product of transpositions.

It is easy to see that this representation is far from unique. For instance, in degree 3, we already have (1, 2) = (1, 3)(2, 3)(1, 3). Nevertheless, we shall define the following.

A permutation is said to be even (resp. odd) if it can be written as a product of an even (resp. odd) number of transpositions.

As the reader may suspect, a permutation cannot be both even and odd. The remainder of this post is devoted to the proof of this amazing result.

As a first observation, if we can write a permutation as a product of transpositions $\tau_1 \tau_2 \ldots \tau_r = \rho_1 \rho_2 \ldots \rho_s$ such that r+s is even, then we have:

$\tau_1 \tau_2 \ldots \tau_r \rho_s^{-1} \ldots \rho_2^{-1} \rho_1^{-1} = id.$

But $\rho_i^{-1} = \rho_i$ since it is a transposition. Hence, it suffices to prove this.

An odd number of transpositions cannot compose to give the identity map.

The approach is to count the number of “crossed pairs”, i.e. let σ be the product of an odd number of r transpositions, and let m be the number of pairs of (ij), ij, such that σ(i) < σ(j). We claim that m and r have the same parity! To do this, we compare the number of crossings for these two permutations:

σ and   τ := σ (a, b).

Note that most of the time σ(i) = τ(i) and trouble only occurs when i = a or i = b, i.e. the following three cases:

• (i, j) = (a, b) : this (i, j) is a crossed pair for σ if and only if it is not a crossed pair of τ;
• i = a, but ja, b : a crossed pair is a negative value of (ij)(σ(i) – σ(j)), so to compute the parity of the number of crossed pairs, we take the product of all these terms and look at the sign:

for σ :  $\prod_{j\ne a,b} (a - j)(\sigma(a) - \sigma(j))$;

for τ$\prod_{j \ne a,b} (a-j)(\tau(a) - \tau(j)) = \prod (a-j)(\sigma(b) - \sigma(j))$.

• i = b, but j ≠ ab : now we take the products:

for σ :  $\prod_{j\ne a,b} (b - j)(\sigma(b) - \sigma(j))$;

for τ$\prod_{j \ne a,b} (b-j)(\tau(b) - \tau(j)) = \prod (b-j)(\sigma(a) - \sigma(j))$.

Thus, the product for both σ and τ is:

$\prod_{j \ne a,b} (a-j)(b-j)(\sigma(a) - \sigma(j))(\sigma(b) - \sigma(j)),$

which are equal (and not just possess the same sign)! This completes our proof.

The following result follows straight from the definition:

The product of two permutations of the same parity is even.

The product of two permutations of different parity is odd.

Example : What is the permutation of the riffle-shuffle in Section I.3?

Answer : The permutation is given by (2, 6, 8, 9, 5, 3)(4, 7). We use the above recipe to convert cycle to product of transpositions: (2, 6, 8, 9, 5, 3) = (2, 6)(6, 8)(8, 9)(9, 5)(5, 3). Since the permutation is a product of 5 + 1 = 6 permutations, it is even.

[ Incidentally, one sees from this proof, that a cycle is odd (resp. even) if and only if it has even (resp. odd) length. ]

This entry was posted in Group Theory Notes and tagged , , , , , . Bookmark the permalink.