Even and Odd Permutations

Begin with the following exercise: verify the following products of permutations:

$$\begin{eqnarray*} (1 2) &=& (1 2) \\ (1 2)(1 3) &=& (1 2 3) \\ (1 2)(1 3)(1 4) &=& (1 2 3 4) \\ (1 2)(1 3)(1 4)(1 5) &=& (1 2 3 4 5) \end{eqnarray*}$$

Although the expressions on the left are not in proper cycle notation, this does show that any cycle can be expressed as a combination of 2-cycles, or exchanges. In fact, a cycle of $n$ objects can be written as a product of $(n-1)$ 2-cycles.

In fact, there are clearly an infinite number of ways to express any permutation as a product of 2-cycles:

$$(1 2 3) = (1 2)(1 3) = (1 2)(1 3)(1 2)(1 2) = (1 2)(1 3)(1 2)(1 2)(1 2)(1 2) = \cdots$$

But it is true that if a permutation can be written as an even number of cycles, any representation will contain an even number of cycles. In the example above, $(1 2 3)$ was expressed as $2, 4, 6, \cdots$ cycles. Similarly, if a permutation allows a representation as an odd number of cycles, all its 2-cycle representations will contain an odd number of 2-cycles. All permutations can be divided into these ``even'' and ``odd'' permutations.

The identity is an even permutation (0 2-cycles), and clearly if you multiply any even permutation by another even permutation, you will get an even permutation. Thus the set of all permutations that are even form a subset of the full symmetric group. This is called the ``alternating group'', and the alternating group on $n$ objects is called $A_n$.

Table 3 is the multiplication table for the alternating group $A_4$. It is a great example of a group that is complicated, but not too complicated. See what subgroups of it you can find.

You've probably seen the sliding block puzzle with $4\times 4$ spaces and 15 blocks numbered 1 through 15, and the object is to try to slide them until they are in order. If you begin will all of them in order except that 14 and 15 are reversed, there is no solution. This can be proved by showing that the sliding operation is like a permutation group, and that the swapping of two blocks amounts to an odd permutation in that group, but the operation of sliding a block is an even permutation. No matter how many even permutations you put together, it will never be odd.

Table 3: The Alternating Group $A_4$

	$(1)$	$(1 2 3)$	$(1 2 4)$	$(1 3 4)$	$(2 3 4)$	$(1 3 2)$	$(1 4 2)$	$(1 4 3)$	$(2 4 3)$	$(1 2)(3 4)$	$(1 3)(2 4)$	$(1 4)(2 3)$
$(1)$	$(1)$	$(1 2 3)$	$(1 2 4)$	$(1 3 4)$	$(2 3 4)$	$(1 3 2)$	$(1 4 2)$	$(1 4 3)$	$(2 4 3)$	$(1 2)(3 4)$	$(1 3)(2 4)$	$(1 4)(2 3)$
$(1 2 3)$	$(1 2 3)$	$(1 3 2)$	$(1 3)(2 4)$	$(2 3 4)$	$(1 2)(3 4)$	$(1)$	$(1 4 3)$	$(1 4)(2 3)$	$(1 2 4)$	$(1 3 4)$	$(2 4 3)$	$(1 4 2)$
$(1 2 4)$	$(1 2 4)$	$(1 4)(2 3)$	$(1 4 2)$	$(1 3)(2 4)$	$(1 2 3)$	$(1 3 4)$	$(1)$	$(2 4 3)$	$(1 2)(3 4)$	$(1 4 3)$	$(1 3 2)$	$(2 3 4)$
$(1 3 4)$	$(1 3 4)$	$(1 2 4)$	$(1 2)(3 4)$	$(1 4 3)$	$(1 3)(2 4)$	$(1 4)(2 3)$	$(2 3 4)$	$(1)$	$(1 3 2)$	$(1 2 3)$	$(1 4 2)$	$(2 4 3)$
$(2 3 4)$	$(2 3 4)$	$(1 3)(2 4)$	$(1 3 4)$	$(1 4)(2 3)$	$(2 4 3)$	$(1 4 2)$	$(1 2)(3 4)$	$(1 2 3)$	$(1)$	$(1 3 2)$	$(1 4 3)$	$(1 2 4)$
$(1 3 2)$	$(1 3 2)$	$(1)$	$(2 4 3)$	$(1 2)(3 4)$	$(1 3 4)$	$(1 2 3)$	$(1 4)(2 3)$	$(1 4 2)$	$(1 3)(2 4)$	$(2 3 4)$	$(1 2 4)$	$(1 4 3)$
$(1 4 2)$	$(1 4 2)$	$(2 3 4)$	$(1)$	$(1 3 2)$	$(1 4)(2 3)$	$(1 3)(2 4)$	$(1 2 4)$	$(1 2)(3 4)$	$(1 4 3)$	$(2 4 3)$	$(1 3 4)$	$(1 2 3)$
$(1 4 3)$	$(1 4 3)$	$(1 2)(3 4)$	$(1 2 3)$	$(1)$	$(1 4 2)$	$(2 4 3)$	$(1 3)(2 4)$	$(1 3 4)$	$(1 4)(2 3)$	$(1 2 4)$	$(2 3 4)$	$(1 3 2)$
$(2 4 3)$	$(2 4 3)$	$(1 4 3)$	$(1 4)(2 3)$	$(1 2 4)$	$(1)$	$(1 2)(3 4)$	$(1 3 2)$	$(1 3)(2 4)$	$(2 3 4)$	$(1 4 2)$	$(1 2 3)$	$(1 3 4)$
$(1 2)(3 4)$	$(1 2)(3 4)$	$(2 4 3)$	$(2 3 4)$	$(1 4 2)$	$(1 2 4)$	$(1 4 3)$	$(1 3 4)$	$(1 3 2)$	$(1 2 3)$	$(1)$	$(1 4)(2 3)$	$(1 3)(2 4)$
$(1 3)(2 4)$	$(1 3)(2 4)$	$(1 4 2)$	$(1 4 3)$	$(2 4 3)$	$(1 3 2)$	$(2 3 4)$	$(1 2 3)$	$(1 2 4)$	$(1 3 4)$	$(1 4)(2 3)$	$(1)$	$(1 2)(3 4)$
$(1 4)(2 3)$	$(1 4)(2 3)$	$(1 3 4)$	$(1 3 2)$	$(1 2 3)$	$(1 4 3)$	$(1 2 4)$	$(2 4 3)$	$(2 3 4)$	$(1 4 2)$	$(1 3)(2 4)$	$(1 2)(3 4)$	$(1)$