Parity of A Permutation - Other Definitions and Proofs

Other Definitions and Proofs

The parity of a permutation of points is also encoded in its cycle structure.

Let be the unique decomposition of into disjoint cycles, which can be composed in any order because they commute. A cycle involving points can always be obtained by composing transpositions (2-cycles):

,

so call the size of the cycle, and observe that transpositions are cycles of size 1. From the decomposition into disjoint cycles we can obtain a decomposition of into transpositions. The number is called the discriminant of, and can also be computed as

if we take care to include the fixed points of as 1-cycles.

When a transposition is applied after a permutation, either and are in different cycles of and

,

or and are in the same cycle of and

.

In both cases, it can be seen that, so the parity of will be different from the parity of .

If is an arbitrary decomposition of a permutation into transpositions, by applying the transpositions after after ... after after the identity (whose is zero) we see that and have the same parity. If we define the parity of as the parity of, what we have shown is that a permutation that has an even length decomposition is even and a permutation that has one odd length decomposition is odd.

Remarks:

• A careful examination of the above argument shows that, and since any decomposition of into cycles whose size sum can be expressed as a composition of transpositions, the number is the minimum possible sum of the sizes of the cycles in a decomposition of, including the cases in which all cycles are transpositions.

• This proof does not introduce a (possibly arbitrary) order into the set of points on which acts.