Conjugates

For some more review, let’s recall the idea of conjugation in a group . We say that two elements and are “conjugate” if for some .

This is an equivalence relation — reflexive, symmetric, and transitive. Any element is conjugate to itself by the group identity; if , then ; if and , then . Thus the set underlying the group can be partitioned into “conjugacy classes”: two group elements are in the same conjugacy class if and only if they are conjugate. The conjugacy class containing a group is commonly written . The different conjugacy classes are pairwise disjoint, and their union is all of .

Now, since these days we’re concerned with the symmetric group. And it turns out that some nice things happen in this case. We’ve actually already seen a lot of these!

First of all, when we write a permutation in cycle notation it’s easy to see what conjugation does to it. Indeed, if is a -cycle and if is any other permutation, then we can write down the conjugate:

And the same goes for any other permutation written in cycle notation: the conjugate by is given by applying to each symbol in the cycle notation. In particular, any two conjugate permutations have the same cycle type. In fact, the converse is also true: given any two permutations with the same cycle type, we can find a permutation that sends the one to the other.

For example, consider the permutations and . Stack them on top of each other:

turn this into two-line notation

and we’ve got a permutation which sends to :

which is equivalent to . That is, two permutations are conjugate if and only if they have the same cycle type. This is really big. Given a cycle type , we will write the corresponding conjugacy class as .

We also know from some general facts about group actions that the number of elements in the conjugacy class is equal to the number of cosets of the “centralizer” . We recall that the centralizer of is the collection of group elements that commute with . That is:

and we have the equation

In the case of — and armed with our formula for conjugating permutations in cycle notation — we can use this to count the size of each . We know that , so all we need is to find out how many permutations leave a permutation (with cycle type ) the same when we conjugate it to get . We will write this number as , and similarly we will write .

So, how can we change the cycle notation of and get something equivalent back again? Well, for any -cycle in we can rotate it around in different ways. For instance, is the same as is the same as . We can also shuffle around any cycles that have the same length: is the same as .

Thus if has cycle type , then we can shuffle the -cycles ways; we can shuffle the -cycles ways; and so on until we can shuffle the -cycles ways. Each -cycle can be rotated into different position for a total of choices; each -cycle can be rotated into different positions for a total of choices; and so on until each -cycle can be rotated into different positions for a total of choices. Therefore we have a total of

different ways of writing the same permutation . And each of these ways corresponds to a permutation in . We have thus calculated

and we conclude

As a special case, how many transpositions are there in the group ? Recall that a transposition is a permutation of the form , which has cycle type . Our formula tells us that there are

permutations in this conjugacy class, as we could expect.