# The Unapologetic Mathematician

## Conjugates

For some more review, let’s recall the idea of conjugation in a group $G$. We say that two elements $g$ and $h$ are “conjugate” if $g=khk^{-1}$ for some $k\in G$.

This is an equivalence relation — reflexive, symmetric, and transitive. Any element $g$ is conjugate to itself by the group identity; if $g=khk^{-1}$, then $h=k^{-1}g\left(k^{-1}\right)^{-1}$; if $f=jgj^{-1}$ and $g=khk^{-1}$, then $f=(jk)h(jk)^{-1}$. Thus the set underlying the group $G$ 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 $g$ is commonly written $K_g$. The different conjugacy classes are pairwise disjoint, and their union is all of $G$.

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 $(a_1\,a_2\,\dots\,a_k)$ is a $k$-cycle and if $g$ is any other permutation, then we can write down the conjugate:

$\displaystyle g(a_1\,\dots\,a_k)g^{-1}=(g(a_1)\,\dots\,g(a_k))$

And the same goes for any other permutation written in cycle notation: the conjugate by $g$ is given by applying $g$ 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 $(1\,5\,2)(3\,4)$ and $(2\,3\,1)(4\,5)$. Stack them on top of each other:

$\displaystyle\begin{aligned}(1\,5\,2)&(3\,4)\\(2\,3\,1)&(4\,5)\end{aligned}$

turn this into two-line notation

$\displaystyle\left\lvert\begin{matrix}1&5&2&3&4\\2&3&1&4&5\end{matrix}\right\rvert$

and we’ve got a permutation $(1\,2)(3\,4\,5)$ which sends $(1\,5\,2)(3\,4)$ to $(2\,3\,1)(4\,5)$:

$\displaystyle(1\,2)(3\,4\,5)\cdot(1\,5\,2)(3\,4)\cdot(2\,1)(5\,4\,3)=(1\,2\,3)(4\,5)$

which is equivalent to $(2\,3\,1)(4\,5)$. That is, two permutations are conjugate if and only if they have the same cycle type. This is really big. Given a cycle type $\lambda$, we will write the corresponding conjugacy class as $K_\lambda$.

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

$\displaystyle Z_g=\left\{h\in G\vert hgh^{-1}=g\right\}$

and we have the equation

$\displaystyle\lvert K_g\rvert=\frac{\lvert G\rvert}{\lvert Z_g\rvert}$

In the case of $S_n$ — and armed with our formula for conjugating permutations in cycle notation — we can use this to count the size of each $K_\lambda$. We know that $\lvert S_n\rvert=n!$, so all we need is to find out how many permutations $h$ leave a permutation $g$ (with cycle type $\lambda$) the same when we conjugate it to get $hgh^{-1}$. We will write this number as $z_\lambda=\lvert Z_g\rvert$, and similarly we will write $k_\lambda=\lvert K_\lambda\rvert=\lvert K_g\rvert$.

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

Thus if $g$ has cycle type $\lambda=(1^{m_1},2^{m_2},\dots,n^{m_n})$, then we can shuffle the $1$-cycles $m_1!$ ways; we can shuffle the $2$-cycles $m_2!$ ways; and so on until we can shuffle the $n$-cycles $m_n!$ ways. Each $1$-cycle can be rotated into $1$ different position for a total of $1^{m_1}$ choices; each $2$-cycle can be rotated into $2$ different positions for a total of $2^{m_2}$ choices; and so on until each $n$-cycle can be rotated into $n$ different positions for a total of $n^{m_n}$ choices. Therefore we have a total of

$1^{m_1}m_1!2^{m_2}m_2!\dots n^{m_n}m_n!$

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

$\lvert Z_g\rvert=1^{m_1}m_1!2^{m_2}m_2!\dots n^{m_n}m_n!$

and we conclude

$\displaystyle k_\lambda=\lvert K_g\rvert=\frac{\lvert S_n\rvert}{\lvert Z_g\rvert}=\frac{n!}{z_\lambda}=\frac{n!}{1^{m_1}m_1!2^{m_2}m_2!\dots n^{m_n}m_n!}$

As a special case, how many transpositions are there in the group $S_n$? Recall that a transposition is a permutation of the form $(a\,b)$, which has cycle type $(1^{n-2},2^1,3^0,\dots,n^0)$. Our formula tells us that there are

$\displaystyle\frac{n!}{1^{n-2}(n-2)!2^11!3^00!\dots n^00!}=\frac{n!}{(n-2)!2}=\binom{n}{2}$

permutations in this conjugacy class, as we could expect.

## 4 Comments	»

1. [...] say and are conjugate elements of the group . That is, there is some so that . I say that for any -module with [...]

Pingback by | October 15, 2010 | Reply

2. [...] an example, we can start writing down the character table of . We know that conjugacy classes in symmetric groups correspond to cycle types, and so we can write down all [...]

Pingback by | October 20, 2010 | Reply

3. [...] The Character Table of S4 Let’s use our inner tensor products to fill in the character table of . We start by listing out the conjugacy classes along with their sizes: [...]

Pingback by | November 8, 2010 | Reply

4. [...] for the symmetric group , there’s something we can say. We know that conjugacy classes in symmetric groups correspond to cycle types. Cycles correspond to integer partitions of . And from a partition we [...]

Pingback by | December 7, 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": 82, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "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.9146653413772583, "perplexity_flag": "head"}