First, we consider the special case of a cycle of length 2, (a, b), 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:
(a1, a2, …, ar) = (a1, a2)(a2, a3) … (ar-1, ar)
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 such that r+s is even, then we have:
But 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 (i, j), i < j, 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 j ≠ a, b : a crossed pair is a negative value of (i – j)(σ(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 σ : ;
for τ : .
- i = b, but j ≠ a, b : now we take the products:
for σ : ;
for τ : .
Thus, the product for both σ and τ is:
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. ]