Theorem 2.15.3 says that every permutation can be expressed as a product of transpositions.
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.)
is odd.
is even.
is even.
The expression for an -cycle as a product of transpositions
in Lemma 2.15.2 shows that an cycle is even if is odd and odd if is even.
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.
No permutation is both odd and even.
Let . If could be written both as a product of an even number and an odd number of transpositions, say
then we could rearrange to get
which expresses the identity permutation as a product of an odd number of transpositions. So it’s enough to show that this is impossible.
Introduce variables . Given any polynomial in these variables and any permutation , we define a new polynomial which is obtained by replacing every variable in by . For example, if and then
Now define
so that, for example,
Let be any transposition, where . We have , because only affects factors of containing or , and the only factors to change sign are with and with , a total of sign changes (as appears in both cases). It follows that any product of an odd number of transpositions sends to . Since the identity sends to , it cannot be written as the product of an odd number of transpositions. ∎
The sign of a permutation is if it is even and if it is odd.
We write for the sign of the permutation .
So if can be written as a product of transpositions, .
For any two permutations and ,
If can be written as a product of transpositions and can be written as a product of transpositions, then can be written as a product of transpositions. So
∎
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.
Even length cycles are odd and odd length cycles are even.
If is any permutation, .
We saw in the proof of Lemma 2.15.2 that if is any -cycle,
so an -cycle can be written as a product of transpositions. The number of transpositions in this expression therefore has the opposite parity to , as required.
If is a product of transpositions, . But the inverse of a transposition is a transposition, so is also the product of transpositions.
∎
Another way to express the first part of this lemma would be to say that .