You are here

Parity Theorem for Permutations - A Reduction Lemma for the Even Identity Lemma

John O. Kiltinen

One technique for proving the Even Identity Lemma is to prove

The Reduction Lemma. If is any expression for the identity permutation in terms of k transpositions, k > 0, then there is another expression for e that uses k - 2 transpositions.

Let us first see how this lemma leads to the Even Identity Lemma. The argument is reductio ad absurdum. If there were an expression for e that used an odd number of transpositions, then by applying the Reduction Lemma to this expression, and then repeatedly to the successors, one could eventually get an expression for the identity in terms of one transposition. This is clearly impossible. If we think in terms of our model, if each marker is in its home box and we swap two of them, then these two are no longer in their home boxes.

To prove the Reduction Lemma, one wants to set forth an algorithm for shortening by two transpositions an expression for the identity permutation. The usual approach is to process the notation for such an expression through a series of steps in which one rewrites certain adjacent pairs of transpositions. After following the algorithm repeatedly, it can be argued that eventually an adjacent pair of equal transpositions must occur. This pair then “drops out” because doing a transposition twice is the same as not doing it at all.

Our proof rests upon a reduction algorithm that tells one how to modify a sequence of transpositions step-by-step to produce a different shorter one. With our algorithm, you can be producing the shorter sequence of transpositions simultaneously while someone is producing the original sequence by swapping markers between boxes.

John O. Kiltinen, " Parity Theorem for Permutations - A Reduction Lemma for the Even Identity Lemma," Convergence (December 2004)