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.
[…] An article in the February Notices Walt, over at Ars Mathematica points out that the February issue of the Notices of the AMS is up online. I won’t go into it all, but I did want to point out the “What Is…” column on Young Diagrams. I’ll be getting to these myself somewhere down the road, since they’re deeply related to conjugacy classes in symmetric groups. […]
Pingback by An article in the February Notices « The Unapologetic Mathematician | March 1, 2007 |
[…] is why we could calculate the number of permutations with a given cycle type the way we did: we picked a representative of the conjugacy class and calculated […]
Pingback by A few more facts about group actions « The Unapologetic Mathematician | October 26, 2007 |
[…] symmetric group. And it turns out that some nice things happen in this case. We’ve actually already seen a lot of […]
Pingback by Conjugates « The Unapologetic Mathematician | September 10, 2010 |