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

September 10, 2010 -

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 Class Functions « The Unapologetic Mathematician | 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 The Character Table of a Group « The Unapologetic Mathematician | 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 The Character Table of S4 « The Unapologetic Mathematician | 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 The Road Forward « The Unapologetic Mathematician | December 7, 2010 | Reply