# The Unapologetic Mathematician

## 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.

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