You are here

Parity Theorem for Permutations - The Parity of a Permutation

John O. Kiltinen

There is no unique way to express a permutation using transpositions. Imagine starting with n numbered boxes and markers with the identity permutation represented by having marker i in box i for each i. Now suppose that you have some target permutation that you want to achieve by means of a sequence of transpositions. Clearly there are many different orders in which you could do your swaps to get there.

In spite of the variability, one feature is constant in this process: the parity of the number of transpositions that are used for a given permutation. Any two expressions for a given permutation in terms of transpositions have the numbers of transpositions used being of the same parity. Stated formally, the Parity Theorem is this:

The Parity Theorem. Suppose that a is a permutation in Sn. If and are two expressions for a as compositions of sequences of k and m transpositions, then either k and m are both even or they are both odd.

John O. Kiltinen, " Parity Theorem for Permutations - The Parity of a Permutation," Convergence (December 2004)