display | more...
If we define a swap (or transposition) to be the operation of interchanging two items in a permutation, then the relation R = "can be reached by an even number of swaps from" is an equivalence relation on the set of permutations of n objects. It divides the set into two equivalence classes, one "even" and one "odd".

It is not very hard to see that the relation is an equivalence relation. However it is not so obvious that there really are two distinct equivalence classes. To prove this we need to show that a product of an odd number of swaps cannot also be written as a product of an even number of swaps.
We can use induction to prove that if we start with a permutation p and perform k swaps and after that return to the original permutation p, then k is even. Thus it is not possible to go from p to some other permutation q both with an even and an odd number of swaps, because then we could go from p to q and then back to p with an odd number of swaps. Now, there clearly are permutations that can be reached by an odd number of swaps, and thus cannot be reached by an even number of swaps.

This has an implication for eg. the 15 game. In every move you swap the empty field and a tile, so if the permutation of the tiles is "odd" the tiles can never be arranged correctly.
The notion of parity for permutations can be encoded with the ε-notation: Let ε(x1, x2, ..., xn) = 1 if x1 , x2, ..., xn is an even permutation of 1, 2, ..., n and -1 if it is an odd permutation. The map ε : Sn -> {1,-1} is a group homomorphism, and its kernel is the alternating group.

Log in or register to write something here or to contact authors.