The Unapologetic Mathematician

Mathematics for the interested outsider

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, (1\,2)(1\,3)=(1\,3\,2). 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 (1\,2\,3) is (3\,2\,1). The inverse of (1\,4)(2\,5\,3) is (4\,1)(3\,5\,2).

Now let’s work out an example. Let (1\,2\,3) act on (1\,2) by conjugation. We calculate (1\,2\,3)(1\,2)(3\,2\,1)=(2\,3). What about (1\,3) acting on (1\,2)? We find (1\,3)(1\,2)(3\,1)=(2\,3).

More generally, say g is a permutation in S_n, and that (a_1\,...a_k) is a k-cycle. Then we have the conjugation h=g(a_1\,...\,a_k)g^{-1}. Let’s see what it does to the symbol x.

Either x is g(a_i) for some a_i in the cycle or not. If it is, then h first sends g(a_i) to a_i; then it sends that to a_{i+1}; then it sends that to g(a_{i+1}). If x isn’t of this form, h sends it back to itself. That is, h is another k-cycle: (g(a_1)\,...g(a_k)).

For a product of disjoint cycles the answer is the same. Conjugation by g replaces every x in the cycle notation with g(x). 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

(1\,4)(3\,5\,2)
(5\,2)(1\,3\,4)

they are conjugate by (1\,5\,3)(2\,4). Indeed we can check that (1\,5\,3)(2\,4)(1\,4)(3\,5\,2)(3\,5\,1)(4\,2)=(1\,3\,4)(2\,5).

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 n letters breaks those letters into a bunch of different collections. There’s one cycle structure for every way of writing n as the sum of a bunch of smaller numbers like this. We call such a way of adding up to n a “partition” of n. For example, for n=5 we have

Partition Cycle Structure
5 (1\,2\,3\,4\,5)
4+1 (1\,2\,3\,4)(5)
3+2 (1\,2\,3)(4\,5)
3+1+1 (1\,2\,3)(4)(5)
2+2+1 (1\,2)(3\,4)(5)
2+1+1+1 (1\,2)(3)(4)(5)
1+1+1+1+1 (1)(2)(3)(4)(5)

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

But now we’ve overcounted. If we rotate the letters in a cycle around we have the same permutation: (1\,2\,3\,4)=(2\,3\,4\,1). For the cycle of n_i letters there are n_i choices here that all give the same permutation, so we have to divide n! by each n_i.

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 m_j! where m_j is the number of j‘s in the partition. Then we’re right. Let’s do this for n=5.

Cycle Structure Size of Conjugacy Class
(1\,2\,3\,4\,5) \frac{5!}{5}=24
(1\,2\,3\,4)(5) \frac{5!}{4}=30
(1\,2\,3)(4\,5) \frac{5!}{3*2}=20
(1\,2\,3)(4)(5) \frac{5!}{3*2!}=20
(1\,2)(3\,4)(5) \frac{5!}{2*2*2!}=15
(1\,2)(3)(4)(5) \frac{5!}{2*3!}=10
(1)(2)(3)(4)(5) \frac{5!}{5!}=1

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

So how can we say this in terms of group actions? The group S_n acts on itself by conjugation. There is one orbit for each partition of n. 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 g is the number of permutations (n!) divided by the size of the isotropy subgroup of g.

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

About these ads

February 23, 2007 - Posted by | Algebra, Group Actions, Group theory

3 Comments »

  1. [...] 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 | Reply

  2. [...] 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 | Reply

  3. [...] 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 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 388 other followers

%d bloggers like this: