Parity Theorem for Permutations - An Enabling Lemma

One way to prove the Parity Theorem is first to prove the

Even Identity Lemma. If e is the identity permutation in S_n that maps every element to itself, and if where the t_i’s are transpositions, then k is an even number.

Before considering a proof of this lemma, let us show how it leads very directly to a proof of the Parity Theorem. Suppose that we have two expressions, and , for a permutation a in terms of transpositions. Then, since the inverse of a composition of a sequence of permutations is the composition of their inverses in the reverse order, and since every transposition is its own inverse, it follows that

This shows that e can be expressed using k + m transpositions. Once the lemma is established, we will know that k + m is an even number. This assures that k and m are either both even numbers or they are both odd numbers.