Permutations

In Section 1 we considered the set of all mappings . We saw there that the composition of mappings is associative, and that the identity mapping is an identity for composition. However, is not a group, since not every mapping has an inverse, as the next example shows.

As in the previous section, we can hope that the subset
of all mappings which *do* have inverses will form a group.
So we want to find out which mappings have inverses.
To this end we have to recall certain special kinds of mappings.

If is a finite set of size , then without loss of generality
we may take
.
In this case we denote by and by .
A mapping can be conveniently written as
a array of originals and their images:

It is easy to see whether such a mapping is a permutation or not: just check whether the sequence of images contains every element of (and so contains it only once). In particular, we see that a mapping from which is surjective must also be injective, and that a mapping that is injective must also be surjective. It is also easy to find the inverse of a permutation written in this way: you just swap the rows (and re-order, if you are tidy!):

Now we describe another useful way of writing down permutations.

The proof of the above theorem, though not difficult, requires some technical attention, and it would probably not give you deeper insight then a particular example:

You should be able to multiply permutations written as products of cycles,
without reverting
them into the two-row format.
As for finding inverses,
the following is of help:

Edmund F Robertson

11 September 2006