# Abstract Nonsense

## Conjugacy Classes on the Symmetric Group

Point of Post: In this post we discuss the conjugacy class structure of the symmetric group $S_n$.

$\text{ }$

Motivation

Often times knowing the conjugacy classes of a group gives you much information about the group. In particular, we have seen that the number of irreducible characters of a group $G$ is equal to the number of conjugacy classes of $G$. That said, it is often difficult without getting one’s hands dirty to find all the conjugacy classes of a group, and moreover finding the number of elements in each such class. It is an interesting fact that for one of the most important groups (for example, the ‘comfort theorem’ given by Cayley) has easily findable conjugacy classes, and even explicitly computable sized classes–I am of course talking about the symmetric group. So, in this post we shall classify the conjugacy classes of $S_n$ and find their order.

$\text{ }$

Cycle Type

$\text{ }$

Before we can talk about the conjugacy classes of $S_n$ we must discuss the cycle type of an element of $S_n$. In particular we know that every element $\pi\in S_n$ can be written as the product of disjoint cycles, and moreover that up to a permutation of the cycles the product is unique. Thus, every element of $S_n$ may be expressed uniquely as the disjoint product of some number of $1$-cycles, some number of $2$-cycles, all the way up to some number of $n$-cycles. If $\pi\in S_n$ can be written as the product of $k_1$ $1$-cycles, all the way up to $k_n$ $n$-cycles we say that $\pi$ is of type $1^{k_1}\cdots n^{k_n}$ or equivalently that $\pi$ has cycle type $1^{k_1}\cdots n^{k_n}$ which is also sometimes written $(k_1,\cdots,k_n)$. When convenient we denote the cycle type of $\pi$ by $\text{type}(\pi)$. For example, for $\pi\in S_8$ given by $\pi=(1,2,3)(5)(6)(7,8)$ then $\text{type}(\pi)=1^22^13^14^05^06^07^08^0$.

$\text{ }$

Conjugacy Classes of $S_n$

$\text{ }$

Now that we have defined cycle type we may now state the main theorem of this post. Namely:

$\text{ }$

Theorem: Let $S_n$ denote the symmetric group. Then, for any$\pi$ and $\pi'$ in $S_n$ one has that $\pi$ is conjugate to $\pi'$ if and only if $\text{type}(\pi)=\text{type}(\pi')$.

Proof: We begin by noting that if $\sigma\in S_n$ and $(a_1,\cdots,a_m)$ is a cycle on $S_n$ then

$\text{ }$

$\sigma(a_1,\cdots,a_m)\sigma^{-1}=(\sigma(a_1),\cdots,\sigma(a_m))$

$\text{ }$

With this observation in hand we note then if $\text{type}(\pi)=\text{type}(\pi')$ then we may write

$\text{ }$

$\pi=(a_{1,1,1})\cdots(a_{1,k_1,1})\cdots (a_{n,1,1},\cdots,a_{n,1,n})\cdots(a_{n,k_n,1},\cdots,a_{n,k_n,n})$

$\text{ }$

(where the indices mean $\text{what size cycle},\text{ what number cycle of that size cycle},\text{what element in that particular cycle}$) and

$\text{ }$

$\pi'=(b_{1,1,1})\cdots(b_{1,k_1,1})\cdots (b_{n,1,1},\cdots,b_{n,1,n})\cdots(b_{n,k_n,1},\cdots,b_{n,k_n,n})$

$\text{ }$

and so (since they are written in disjoint cycle notation, thus the numbers appearing form a partition) we may define $\sigma\in S_n$ by $\sigma(a_{q,r,s})=b_{q,r,s}$ and so

$\text{ }$

$\sigma\pi\sigma^{-1}=\sigma(a_{1,1,1})\sigma^{-1}\sigma\cdots\sigma^{-1}\sigma(a_{1,k_1,1})\sigma^{-1}\sigma\cdots \sigma^{-1}\sigma(a_{n,1,1},\cdots,a_{n,1,n})\sigma^{-1}\sigma\cdots\sigma^{-1}\sigma(a_{n,k_n,1},\cdots,a_{n,k_n,n})\sigma^{-1}$

$\text{ }$

but by our observation this is equal to

$\text{ }$

$(\sigma(a_{1,1,1}))\cdots(\sigma(a_{1,k_1,1}))\cdots (\sigma(a_{n,1,1}),\cdots,\sigma(a_{n,1,n}))\cdots(\sigma(a_{n,k_n,1}),\cdots,\sigma(a_{n,k_n,n}))$

$\text{ }$

which by construction is equal to $\pi'$.

$\text{ }$

Conversely, if $\pi$ and $\pi'$ are conjugate,using $\pi$‘s disjoint cycle notation from above and the same calculation, we see that

$\text{ }$

$\pi'=\sigma\pi\sigma^{-1}=(\sigma(a_{1,1,1}))\cdots(\sigma(a_{1,k_1,1}))\cdots (\sigma(a_{n,1,1}),\cdots,\sigma(a_{n,1,n}))\cdots(\sigma(a_{n,k_n,1}),\cdots,\sigma(a_{n,k_n,n}))$

$\text{ }$

and since $\sigma$ is a bijection so that this last cycle decomposition is a disjoint cycle decomposition we may conclude that $\text{type}(\pi)=\text{type}(\pi')$. $\blacksquare$

$\text{ }$

$\text{ }$

Thus, we see that each conjugacy class of $S_n$ corresponds uniquely to a cycle type $1^{k_1}\cdots n^{k_n}$— consequently we will often refer to a conjugacy class in $S_n$ by the corresponding cycle type of its elements. The interesting thing is that we can calculate the size of this conjugacy class. Namely:

$\text{ }$

Theorem: Let $1^{k_1}\cdots n^{k_n}$ be a conjugacy class in $S_n$. Then, the cardinality of this conjugacy class is

$\text{ }$

$\displaystyle \frac{n!}{k_1!1^{k_1}\cdots k_n! n^{k_n}}=\prod_{j=1}^{n}\frac{n}{k_j!j^{k_j}}$

$\text{ }$

Proof: Let $\pi=(a_{1,1,1})\cdots(a_{1,k_1,1})\cdots (a_{n,1,1},\cdots,a_{n,1,n})\cdots(a_{n,k_n,1},\cdots,a_{n,k_n,n})$ be an element of $1^{k_1}\cdots n^{k_n}$. We seek to find the size of the centralizer $\bold{C}_G(\pi)$. To do this we note that by our previous observation that for any $\sigma\in S_n$ we have that

$\text{ }$

$\sigma\pi\sigma^{-1}=(\sigma(a_{1,1,1}))\cdots(\sigma(a_{1,k_1,1}))\cdots (\sigma(a_{n,1,1}),\cdots,\sigma(a_{n,1,n}))\cdots(\sigma(a_{n,k_n,1}),\cdots,\sigma(a_{n,k_n,n}))$

$\text{ }$

We thus see that $\sigma$ must map a $j$-cycle to a $j$-cycle for which there are $k_j!$ ways to do. Thus, if we fix a particular permutation of the $j$-cycles then choosing a particular $j$-cycle we see that $\sigma$ must only cyclically permute the elements of this cycle, for which there are obviously $j$ ways to do, and thus within each fixed choice of permutations of the $j$-cycles there are $j^{k_j}$ choices for $\sigma$‘s action. Thus, for each $j\in[n]$ there are $k_j! j^{k_j}$ choices and thus the total number of choices for $\sigma$ is $k_1!1^{k_1}\cdots k_n! n^{k_n}$. Thus, we may conclude that $\#\left(\bold{C}_G(\pi)\right)=k_1!1^{k_1}\cdots k_n! n^{k_n}$ from where the conclusion follows by the orbit-stabilizer theorem. $\blacksquare$

$\text{ }$

$\text{ }$

References:

1. Simon, Barry. Representations of Finite and Compact Groups. Providence, RI: American Mathematical Society, 1996. Print.