A permutation of n elements can be written as an ordered list of the numbers 1 through n. (Other notational conventions exist; this one will be familiar to computer programmers.) For instance, the permutation x = {2,3,1,5,4} moves the element in position 1 to position 2, 2 to 3, and 3 back to 1, while elements in positions 4 and 5 are swapped.
If x and y are two such permutations, their composition moves i to y[x[i]]. For instance, let y = {5,2,1,3,4}, and compose by writing y[x[i]] for each i. Hence xy = {2,1,5,4,3}.
Given a permutation, count how many times a larger number precedes a smaller number in the list. If this count is even the permutation is even, else it is odd. The identity permutation, {1,2,3,4,5}, has zero pairs out of order, hence it is even. The permutation {5,4,3,2,1} has ten pairs out of order, and is also even.
If two adjacent elements are swapped, i.e. a transposition, the parity of the permutation is reversed. The swap only changes the pair in question; all other pairs are unaffected. The swapped elements are moved into or out of ascending order, hence the parity is flipped.
Every permutation can be implemented by a series of transpositions. There may be many ways to do this, but an even permutation is always achieved using an even number of transpositions, and an odd permutation requires an odd number of transpositions.
The composition of even permutations is even. The first is achieved using an even number of transpositions, and so is the second, hence the composition is built using an even number of transpositions, and is even. In general, even and odd permutations add together just like even and odd numbers. Parity is a group homomorphism from the permutation group G into Z2.
If G includes odd permutations, the even permutations form a proper subgroup that maps to 0 under parity, while the odd permutations map to 1. The even permutations form the kernel of the parity homomorphism, and are a normal subgroup in G.
| A permutation x can also be represented by drawing two rows of n dots, and joining dot i in the top row to dot x[i] in the bottom row. For example, the diagram on the right represents the permutation {3,1,5,4,2}. The number of pairs out of order is the number of crossings in the diagram, since the pair x[i],x[j] is out of order if and only if the line from i to x[i] crosses the line from j to x[j]. For example, the line from 1 to 3 crosses the line from 2 to 1, corresponding to the pair 3,1 which is out of order. So a permutation is even if and only if the diagram has an even number of crossings. |
|