Working with permutations

Permutations are going to be very important throughout this course, so let’s spend some time learning about their structure, and how we can work with them.

Notation

Two types of notation are commonly used when working with permutations: Cauchy’s two-line notation and cycle notation. Both are useful: we’ll work with the two-line notation here, and will introduce cycle notation later in the course. From now on we’ll also assume that the set of (n) things to be permuted is just the set of numbers from 1 up to (n).

With (n=4), consider the permutation that replaces 1 with 2, 2 with 3, 3 with 1, and 4 with 4. We can think of a permutation as a rule, or function, which tells us what to replace each number with. We often use the Greek letter (sigma) (“sigma”) to denote such a function, and so in this example we could write

[sigma(1) = 2, quad sigma(2) = 3, quad sigma(3) = 1, quad sigma(4) = 4.]

Cauchy’s two-line notation is just a way of neatly presenting this function: the top line lists the elements of our set, and the bottom line shows what each one is replaced by when using permutation (sigma).

[sigma = begin{pmatrix} 1 & 2 & 3 & 4 \ sigma(1) & sigma(2) & sigma(3) & sigma(4) end{pmatrix} = begin{pmatrix} 1 & 2 & 3 & 4 \ 2 & 3 & 1 & 4 end{pmatrix}.]

The order of elements that we use in the first row doesn’t really matter, but it’s most natural to list them in increasing order.

Permutations form a group

We’ve seen that a permutation describes a way of jumbling up a set of objects. This operation has some very nice properties.

Composition

Consider using a permutation (sigma) to jumble the elements of the set ({1,2,dots,n}). If we take the output of (sigma), and apply to this a second permutation (let’s call it (mu) (“mu”)), the result is just another permutation of the set ({1,2,dots,n}). We write (mu(sigma)) or (mucircsigma) for the result of applying (sigma) first, then (mu).

For example, suppose that our two permutations are as follows:

[sigma = begin{pmatrix} 1 & 2 & 3 & 4 \ 2 & 3 & 1 & 4 end{pmatrix} qquad mu = begin{pmatrix} 1 & 2 & 3 & 4 \ 1 & 4 & 3 & 2 end{pmatrix} .]

Suppose that we apply (sigma), followed by (mu), to the number 1. First of all we see that (sigma(1) = 2); we then put this into the permutation (mu), which replaces 2 with 4: thus (mu(sigma(1)) = mu(2) = 4). Similarly, (mu(sigma(2)) = mu(3) = 3). Continuing in this way we see that

[mu(sigma) = mucircsigma = begin{pmatrix} 1 & 2 & 3 & 4 \ 4 & 3 & 1 & 2 end{pmatrix} .]

This is called composition of permutations. It’s important to note that the order in which we compose permutations matters! For example, check that if we apply (mu) followed by (sigma) in the above example then we get the permutation

[sigma(mu) = sigmacircmu = begin{pmatrix} 1 & 2 & 3 & 4 \ 2 & 4 & 1 &3 end{pmatrix}]

which is different to what we calculated for (mu(sigma)).

Identity

There exists a trivial permutation, which doesn’t actually jumble up anything! This is called the identity permutation, often written (id), which replaces each number with itself. So if we’re working with (n=4), the identity looks as follows in two-line notation:

[id = begin{pmatrix} 1 & 2 & 3 & 4 \ 1 & 2 & 3 & 4 end{pmatrix}.]

Inverse permutation

A permutation (sigma) jumbles up the elements of our set. But we can always find another permutation, called the inverse permutation, which puts things back in their original order. (Think back to the Caesar cipher: that permuted the plaintext by replacing each letter with the letter 3 further on in the alphabet; to decrypt the ciphertext, you had to undo this operation, by replacing each letter with the letter 3 before it in the alphabet.)

We use the notation (sigma^{-1}) for the permutation that undoes the effect of a permutation (sigma). Here’s an example:

[sigma = begin{pmatrix} 1 & 2 & 3 & 4 \ 2 & 3 & 1 & 4 end{pmatrix} qquad sigma^{-1} = begin{pmatrix} 1 & 2 & 3 & 4 \ 3 & 1 & 2 & 4 end{pmatrix} .]

Check that (sigma(sigma^{-1}) = sigma^{-1}(sigma) =id): in other words, applying a permutation and then its inverse (or the other way around) is the same as applying the identity permutation (i.e. effectively doing nothing).

These properties of permutations (along with something called associativity, which we won’t worry about here) mean that the set of permutations forms something called the symmetric group. Groups are a fundamental object of mathematics: we won’t talk much about them throughout the rest of this course, but if you’re interested in finding out more then try starting here.

Your turn!

Try the following exercises, to check your understanding; use the comments to report how you’re getting on, but be careful not to give away the answers!

1. Check that the inverse to the permutation (mu) given above is (mu^{-1} = begin{pmatrix} 1 & 2 & 3 & 4 \ 1 & 4 & 3 & 2 end{pmatrix} .)
2. Above we calculated (mu(sigma)). Find the inverse of that permutation, ((mu(sigma))^{-1}).
3. Calculate (sigma^{-1}(mu^{-1})). (That is, see what happens when you first apply (mu^{-1}) and then apply (sigma^{-1}).) How does your answer compare to that from Q2?