Next: Order of a permutation Up: Groups Previous: SUBGROUPS

# PERMUTATION GROUPS

An important class of groups are permutation groups. One reason for their importance is that every group may be represented as a group of permutations on a suitable set.

Let A be a set, then a permutation of A is a bijection . Read the notes on functions if you are unfamiliar with this idea.

If A is finite then we may as well let and we write such a permutation as

where the are distinct elements of A.

For example, let . There are six permutations for this set, namely , , , , , .

There are two other common ways to write such a permutation. If the set A is understood to be a set of consecutive integers (or an ordered set) then the top line is deleted so we would write

where it is understood that maps 1 to etc. We shall not use this way of writing permutations. The second way, and the method we shall use in these notes, is to write the permutation as a product of disjoint cycles. A cycle is constructed as follows: Choose some starting element, say . Now compute the elements , , and so on until we arrive back at the element i (this is guaranteed if A is finite). Enclose this list of elements of A in parentheses to form the cycle where by we mean applied to i k-times. Now repeat the process to form the next cycle choosing as starting element an element of A that has not appeared in any previous cycle. The process ends when every element of A appears in exactly one cycle. The representation of is then obtained by juxtaposing (multiplying) these disjoint cycles. It is usual to suppress cycles containing only one element.

As an example, if here are two of the three ways we discussed to write a certain permutation

where in the cycle notation we have suppressed the cycles (4)(7)(8). In a cycle such as we mean that the permutation maps 1 to 2, maps 2 to 3 and maps 3 to 1.

Note that the cycle can also be written as since it contains the same information, but could not have been written as .

The six permutations on written as permutations in cycle form are 1, , , , , .

Next: Order of a permutation Up: Groups Previous: SUBGROUPS

Peter Williams
Sun Mar 30 14:48:35 PST 1997