Odd/Even Permutations

How do you classify a permutation as odd or even (composition of an odd or even number of transpositions)? I somewhat understand the textbook definition of it but I’m having hard time conceptualizing and determining how it is actually determined if it’s odd or even.

Answer

Every permutation can be expressed as the product of one and only one of the following:

  • an odd number of transpositions odd permutation
  • an even number of transpositions even permutation

There are many ways to write a permutation as the product of transpositions, and they can vary in length, but those products will have either an odd or an even number of factors, never both.

If you know cycle notation, knowing the parity (oddness/evenness) can be found fairly easily.

One can always resort to following the pattern:

(a1,a2,a3,a4,a5)=(a1,a5)(a1,a4)(a1,a3)(a1,a2) which is even because there are four transpositions.

Alternatively:

(a1,a2,a3,a4,a5)=(a1,a2)(a2,a3)(a3,a4)(a4,a5)

Again, an even number of transpositions the permutation is even.

You’ll see that the number of transpositions in a product corresponding to a permutation that is a cycle of length n can be expressed as the product of n1 transpositions. So a cycle with a length that is even (has an even number of elements) is ODD, and a cycle with a length that is odd (has an odd number of elements) is EVEN.

If you have a permutation that is the product of disjoint cycles: say three cycles, corresponding to lengths n1,n2,n3, then the number of transpositions representing this permutation can be computed by the parity of (n11)+(n21)+(n31) or simply the parity (oddness/evenness) of n1+n2+n31


One final note: the identity permutation (i.e., the “do nothing” permutation): the permutation which can be represented as the product of one-cycles sending 11,22,,nn is always considered to be an EVEN permutation. Why? Well, note that we can represent the identity permutation by the product, say, of (12)(12)=(12)(12)(3)(n)=(1)(2)(3)(n), so it is indeed an even permutation.

Attribution
Source : Link , Question Author : user65422 , Answer Author : amWhy

Leave a Comment