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.

Like this:

Posted by John Armstrong | 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 | 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 | 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 | September 10, 2010 | Reply

« Previous | Next »

About this weblog

This is mainly an expository blath, with occasional high-level excursions, humorous observations, rants, and musings. The main-line exposition should be accessible to the “Generally Interested Lay Audience”, as long as you trace the links back towards the basics. Check the sidebar for specific topics (under “Categories”).

I’m in the process of tweaking some aspects of the site to make it easier to refer back to older topics, so try to make the best of it for now.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 91, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9190371036529541, "perplexity_flag": "head"}