Conjugation and cycle structure invariance

How does cycle structure change when we perform different operations on permutations? More importantly, when doesn’t it change?

Cycle structure of inverse permutations

Hopefully you tried out the exercises at the end of the previous article. There you were asked to work out the cycle structure of the inverse permutations (sigma^{-1}) and (mu^{-1}). You should have found that the cycle structure of (sigma^{-1}) is ((3,1)) – the same as (sigma) – and the cycle structure of (mu^{-1}) is ((2,1,1)) – the same as (mu).

Is this true more generally? Is the cycle structure of a permutation (sigma) always the same as that of its inverse, (sigma^{-1})?

Yes! The easiest way to understand why this is true is to picture cycles moving elements around in a circle: in order to move them back to their starting position (i.e. apply the inverse permutation), we need to move them in the same circle, but now in the opposite direction! For example, the inverse of the 5-cycle ((1,5,2,3,4)) is the 5-cycle ((1,4,3,2,5)):

More generally, if a (k)-cycle contains elements ((x_1,x_2,x_3, dots, x_{k-1},x_k)), its inverse is the (k)-cycle ((x_k,x_{k-1}, dots ,x_3,x_2,x_1)).

Cycle structure under conjugation

A particularly important operation that can be applied to permutations is called conjugation. We say that two permutations (sigma) and (mu) are conjugate if there is some permutation (rho) (“rho”) such that

[sigma = rho^{-1} circ mucirc rho ,.]

That is, if we apply permutation (rho), then (mu), then (rho^{-1}), we get the same result as applying the permutation (sigma).

Example

The permutations (sigma=(1,2,3)) and (mu=(1,4,3)) are conjugate. Why? Let (rho=(2,4)), and note that (rho^{-1} = rho) (since all (rho) does is swap two elements, so the inverse permutation is just to swap them again!).

Then (check!):

• (mu circ rho = (1,4,2,3))
• (rho^{-1} circ mucirc rho = (1,2,3) = sigma,.)

We can also talk of starting with some permutation (mu), and conjugating it by another permutation (rho): this just means forming the permutation (rho^{-1}circ mucirc rho). So in the above example, conjugating the 3-cycle ((1,4,3)) by the transposition ((2,4)) gives the 3-cycle ((1,2,3)).

What do you notice? When we conjugated (mu) by (rho) in this example, we ended up with another 3-cycle: the cycle structure of (rho^{-1}circ mucirc rho) was the same as that of (mu). The mathematician inside you should be asking “Does this always happen?” Let’s try some more examples – you should check these calculations for yourself!

• If (mu=(1,3,5)(2,4)) and (rho = (1,2,5)) then (rho^{-1}circ mucirc rho = (1,4)(2,5,3)): both (mu) and its conjugation by (rho) have cycle structure ((3,2)).
• If (mu=(1,2,3,4,5)) and (rho=(1,3)(2,5)) then (rho^{-1}circ mucirc rho = (1,4,2,3,5)): in this case both (mu) and its conjugation are 5-cycles.

Looks promising! What conjugation does can be thought of as a three-step process:

1. (rho) relabels all of the elements;
2. (mu) permutes the elements, using their new labels;
3. (rho^{-1}) undoes the relabelling from the first step.

The result is a permutation which has the same structure as (mu).

Example

Consider once again the example with (mu=(1,2,3,4,5)) and (rho=(1,3)(2,5)), and let’s picture what happens when we conjugate (mu) by (rho). We know that (mu) is a 5-cycle, so we expect the same to be true of (rho^{-1}circ mucirc rho).

First we write out the elements as numbered circles, as in our previous diagrams, but we now add an extra label to each element which shows the effect of the permutation (rho): these are the small blue numbers above each circle – you can see that these new labels switch (transpose) the pairs ((1,3)) and ((2,5)).

We now apply the permutation (mu), looking only at these new (small, blue) labels. So we apply the 5-cycle ((1,2,3,4,5)) as follows:

Finally, we can undo the effect of (rho) by deleting the small blue labels: reading the original (large, black) numbers, we can see that these are being shuffled according to the 5-cycle ((1,4,2,3,5)), as we expected.

The important message here is that conjugation doesn’t change cycle structure. Next we’ll see how this simple fact was used to break Enigma…