Conjugacy classes in symmetric groups

Let’s work out how symmetric groups act on themselves by conjugation. As I’m writing I notice that what I said before about composition of permutations is sort of backwards. It’s one of those annoying conventions that doesn’t really change anything, but can still be a bit confusing. From here on when we write permutations in cycle notation we compose by reading the cycles from right to left. That is, . Before I was reading them left to right. The new way behaves more like group actions. The exposition comes after the jump.

First of all, it’s useful to have a quick way of inverting a permutation. All we have to do is write it down in cycle notation, then reverse all the cycles. The inverse of is . The inverse of is .

Now let’s work out an example. Let act on by conjugation. We calculate . What about acting on ? We find .

More generally, say is a permutation in , and that is a -cycle. Then we have the conjugation . Let’s see what it does to the symbol .

Either is for some in the cycle or not. If it is, then first sends to ; then it sends that to ; then it sends that to . If isn’t of this form, sends it back to itself. That is, is another -cycle: .

For a product of disjoint cycles the answer is the same. Conjugation by replaces every in the cycle notation with . In particular, conjugation preserves the cycle structure of the permutation. On the other hand, given two permutations with the same cycle structure we can find a conjugation between them by writing them one above the other and sending a letter on the top to the letter just below it. If we have the two permutations

they are conjugate by . Indeed we can check that .

This is big. Permutations are conjugate if and only if they have the same cycle structure.

So what sort of cycle structures are there? The cycle notation for a permutation of letters breaks those letters into a bunch of different collections. There’s one cycle structure for every way of writing as the sum of a bunch of smaller numbers like this. We call such a way of adding up to a “partition” of . For example, for we have

Partition	Cycle Structure

How many permutations are in each class? Let’s say we’re looking at a partition of into . We shuffle around all n$ letters in ways and then take the first of them, then the next , and so on until only are left.

But now we’ve overcounted. If we rotate the letters in a cycle around we have the same permutation: . For the cycle of letters there are choices here that all give the same permutation, so we have to divide by each .

We’ve still overcounted! If there are two cycles of the same length we don’t care if we do first one and then the other since they share no letters in common. We have to further divide by where is the number of ‘s in the partition. Then we’re right. Let’s do this for .

Cycle Structure	Size of Conjugacy Class

We can check that these numbers add up to , as they should. They also square with Mark Dominus’ post.

So how can we say this in terms of group actions? The group acts on itself by conjugation. There is one orbit for each partition of . We can calculate the size of the orbit corresponding to a given partition as above. If we watch closely, we’ve also found the isotropy subgroup of a given permutation: it’s the subgroup generated by permutations that rotate cycles and those that swap cycles of different types. In fact, the size of this group is exactly what we use to calculate the size of a conjugacy class! The number of permutations conjugate to a given permutation is the number of permutations () divided by the size of the isotropy subgroup of .

Pay attention to these things, they get even more interesting.