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.