Lesson 8

We are now ready to show that our definition of the parity of a permutation is consistent.

Theorem. For any permutation \(\pi\), the permutation \(\pi\) cannot be both even and odd.

Proof. Assume, for the sake of contradiction, that \(\pi\) can be obtained from the identity permutation by both an odd number of transpositions and an even number of transpositions. In each of these two sequences, replace every transposition with a sequence of neighbor transpositions. A simple but crucial observation is that this replacement does not change the parity of the total number of transpositions. Thus, we obtain two sequences of neighbor transpositions with different parities.

Indeed, each transposition is replaced by a sequence of \(2k+1\) neighbor transpositions, where \(k\) is the number of elements lying between the two elements being swapped. In particular, each replacement increases the total number of transpositions by \(2k\), and therefore preserves its parity.

It follows that \(\pi\) can be obtained from the identity permutation by a sequence \(A\) consisting of an even number of neighbor transpositions and also by a sequence \(B\) consisting of an odd number of neighbor transpositions. Now apply the reversed sequence \(A\) to \(\pi\); this returns the identity permutation. Then apply the sequence \(B\) to the identity permutation; this brings us back to \(\pi\). Hence, starting from \(\pi\), one can return to \(\pi\) using an odd number of neighbor transpositions. It remains to show that this is impossible.

To prove this, fix any two distinct elements \(x\) and \(y\) in the permutation \(\pi\), and consider the number of neighbor transpositions that swap \(x\) and \(y\). Any sequence of neighbor transpositions that starts with \(\pi\) and ends again with \(\pi\) must swap \(x\) and \(y\) an even number of times. Since this holds for every pair of distinct elements, the total number of neighbor transpositions in the sequence must be even. This contradicts the conclusion above.◼