The cycle structure of permutations

In Week 1 we met the idea of permutations, and saw one way of representing them – the Cauchy two-line notation. We also saw how to compose two permutations together, and how to calculate an inverse permutation. We now need to develop our understanding of the cycle structure of permutations, before seeing how this concept was exploited to break Enigma.

Cycles and cycle notation

Back in Week 1 we started off by considering the following permutation (sigma), which mixes up the elements of the set ({1,2,3,4}):

[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}.]

This two-line notation says that (sigma(1) = 2), (sigma(2) = 3), and so on. The notation is ok when we’re considering permutations of just a few numbers, but quickly gets cumbersome when dealing with permutations of larger sets. A simpler way to describe (sigma) comes from picturing its effect on each of the numbers:

In this diagram, arrows show the effect of the permutation (sigma): the arrow from 1 to 2 indicates that (sigma(1) = 2), for example.

We can do the same for the permutation (mu) that we met back in Week 1.

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

We can see that both permutations can be broken up into disjoint cycles. The permutation (sigma) moves the numbers ({1,2,3}) in one cycle, and the number (4) in its own (trivial) cycle (since (sigma(4) = 4)). Similarly, (mu) moves the numbers ({2,4}) in a cycle, and doesn’t move the numbers (1) and (3).

It’s hopefully clear that we can break up any permutation into cycles in this way. This leads to the idea of cycle notation: we group elements belonging to common cycles within pairs of brackets, with their order within a pair of brackets showing the “direction” in which the cycle moves those elements. So we can write

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

Usually, in fact, we don’t bother to include trivial cycles when writing permutations in this way: any numbers that are missing are understood to be “left alone”, or “fixed”, by the permutation. So we can just write (sigma = (1,2,3)) and (mu=(2,4)): much simpler!

A note on notation

The order of elements within a set of brackets tells us how a permutation cycles between them. So in writing (sigma = (1,2,3)) this tells us that (sigma(1) = 2), (sigma(2) = 3) and (sigma(3) = 1). The same would be true if we were to write (sigma = (2,3,1)), or (sigma = (3,1,2)): these are all equally valid.

Similarly, the order in which we write out disjoint cycles doesn’t matter. The permutation ((1,3)(2,4)) swaps elements 1 and 3, and elements 2 and 4: the same is true of the permutation ((2,4)(1,3)). Both are valid ways of writing the same permutation.

Cycle structure

We’ve observed that a permutation shuffles elements around within disjoint cycles. Note that if we take the diagram for one of those cycles, and keep following the arrows around, we eventually get back to our starting point. For example, applying the cycle ((1,2,3)) once means that (1) gets moved to (2); applying that cycle twice would move (1) to (3); and applying it three times would do nothing – (1) would get moved to (1) (and in fact all elements would end up back at their starting points!).

The order of a cycle is the smallest (positive) number of times that it can be applied in order to bring each element back to its starting point. So the order of ((1,2,3)) is three. The order of the cycle ((2,4)) is two.

It’s easy to see that the order of a cycle is in fact just the number of elements moved by that cycle! We refer to a cycle containing (k) elements as a (k)-cycle: ((1,2,3)) is a 3-cycle, for example. A 2-cycle, such as ((2,4)) above, is usually called a transposition, as it just “transposes” (swaps) two elements.

All of the above allows us to – finally – talk about the cycle structure of a permutation. This is simply a list of the cycle orders, in decreasing order. So the cycle structure of (sigma) is ((3,1)), and the structure of (mu) is ((2,1,1)).

Your turn!

Try the following exercises, to check your understanding; use the comments to ask any questions you may have, but be careful not to give away the answers!

1. Look at the permutations (sigmacircmu) and (mucircsigma) that we formed in Week 1 by composing (sigma) and (mu). Work out how to write these in cycle notation.
2. Write the inverse permutations (sigma^{-1}) and (mu^{-1}) using cycle notation. What do you notice about their cycle structure?