conjugacy classes in the symmetric group $S_n$

We start by providing an alternate proof that in $S_n$, every permutation has a cycle decomposition, and we prove that the cycle decomposition is essentially unique.

Theorem 1.

Every permutation in $S_n$ has a cycle decomposition that is unique up to ordering of the cycles and up to a cyclic permutation of the elements within each cycle.

Proof.

We construct the cycle decomposition for $\sigma \in S_n$. Let $X=\{1,\mathrm{\dots },n\}$, and regard $\sigma$ as acting on $X$. Let $G=⟨\sigma ⟩$ be the subgroup of $S_n$ generated by $\sigma$. Then $G$ acts on $X$, so by the orbit-stabilizer theorem, it partitions $X$ into a unique set of orbits. In addition, for any orbit $Gx$, we have that

$${\sigma }^{i}x\leftrightarrow {\sigma }^i{G}_x$$

is a bijection, where $G_x$ is the stabilizer of $x$ in $G$.

Now, $G=⟨\sigma ⟩$ is cyclic and thus $G/G_x$ is cyclic as well; its order is the smallest power $d$ of $\sigma$ such that ${\sigma }^d\in G_x$. Note also that $d=|Gx|=[G:G_x]$. Using the explicit bijection above, we see that the unique cosets of $G_x$ in $G$ are

$$G_x,\sigma G_x,\mathrm{\dots },{\sigma }^{d-1}{G}_x$$

and that the elements of $Gx$ are

$$x,\sigma x,\mathrm{\dots },{\sigma }^{d-1}x$$

Thus on any orbit of size $d$, $\sigma$ is a $d$-cycle. This shows that a cycle decomposition exists.

Uniqueness now follows easily, since the cycle determined by $\sigma$ on an element of order $d$ is determined uniquely by construction from the element. Choosing a different element in the same orbit, say ${\sigma }^{j}x$, gives instead

$${\sigma }^{j}x,{\sigma }^{j+1}x,\mathrm{\dots },{\sigma }^{d-1}x,x,\sigma x,\mathrm{\dots },{\sigma }^{j-1}x$$

which is the same cycle permuted left by $j$ . ∎

We can thus write

Definition 1.

If $\sigma \in S_n$ and $\sigma$ is written as the product of the disjoint cycles of lengths $n_1,\mathrm{\dots },n_k$ with $n_i\le n_{i+1}$ for each , then $n_1,\mathrm{\dots },n_k$ is the cycle type of $\sigma$.

The above theorem proves that the cycle type is well-defined.

Theorem 2.

Two permutations $\sigma \mathrm{,}\tau \mathrm{\in }{S}_n$ are conjugate if and only if they have the same cycle type.

Proof.

Assume first that $\sigma$ and $\tau$ are conjugate; say $\tau ={\sigma }_1\sigma {\sigma }_1^{-1}$. Write $\sigma$ as a product of disjoint cycles

$$({\alpha }_1\mathrm{\dots }{\alpha }_a)({\beta }_1\mathrm{\dots }{\beta }_b)(\mathrm{\dots })$$

To show that $\sigma$ and $\tau$ have the same cycle type, it clearly suffices to show that if $j$ follows $i$ in the cycle decomposition of $\sigma$, then ${\sigma }_1(j)$ follows ${\sigma }_1(i)$ in the cycle decomposition of $\tau$. But suppose $\sigma (i)=j$. Then

$$\tau ({\sigma }_1(i))={\sigma }_1\sigma {\sigma }_1^{-1}({\sigma }_1(i))={\sigma }_1\sigma (i)={\sigma }_1(j)$$

and we are done.

Now suppose $\sigma$ and $\tau$ have the same cycle type. Write the cycle decomposition for each permutation in such a way that the cycles are listed in nondecreasing order of their length (including cycles of length 1). We then have (for example)

$\sigma$ $=(a_1)(a_2{a}_3{a}_4)(a_5\mathrm{\dots }{a}_n)$

$\tau$ $=(b_1)(b_2{b}_3{b}_4)(b_5\mathrm{\dots }{b}_n)$

Define ${\sigma }_1$ to be the permutation that takes $a_i$ to $b_i$. Clearly $\sigma \in S_n$, since each of $1,\mathrm{\dots },n$ appears exactly once among the $a_i$ and once among the $b_i$. But also, since the cycle types of $\sigma$ and $\tau$ match, we see that

$${\sigma }_1\sigma {\sigma }_1^{-1}(b_i)={\sigma }_1\sigma (a_i)={\sigma }_1(a_j)=b_j$$

where $a_j$, $b_j$ are the ”‘next”’ elements in their respective cycles. Thus $\tau ={\sigma }_1\sigma {\sigma }_1^{-1}$ and we are done. ∎

Corollary 3.

The number of conjugacy classes in $S_n$ is the number of partitions of $n$.

Proof.

Each distinct cycle type in $S_n$ represents a distinct partition of $n$, and each cycle type represents a conjugacy class. The result follows. ∎

We can give an explicit for the size of each conjugacy class in $S_n$.

Theorem 4.

Suppose $\sigma \mathrm{\in }{S}_n$, and let $m_{\mathrm{1}}\mathrm{,}{m}_{\mathrm{2}}\mathrm{,}\mathrm{\dots }\mathit{}{m}_r$ be the distinct integers (including $\mathrm{1}$ if applicable) in the cycle type of $\sigma$, and let there be $k_i$ cycles of order $m_i$ in $\sigma$. (Thus $\mathrm{\sum }{k}_i\mathit{}{m}_i\mathrm{=}n$). Then the number of conjugates of $\sigma$ is exactly

$$\frac{n!}{(k_1!m_1^{k_1})(k_2!m_2^{k_2})\mathrm{\cdots }(k_r!m_r^{k_r})}$$

Proof.

The size of a conjugacy class is the number of cycles of the given cycle type. Choose a cycle type, and order the cycles in some order. Consider the $n!$ possible assignments of the integers from $1$ to $n$ into the ”‘holes”’ in the cycles. Call two such arrangements equivalent if they define the same permutation. It is clear that this is an equivalence relation, and that the relation partitions the arrangements. We will determine the size of each equivalence class.

Consider a particular arrangement (i.e. permutation), and consider the $k_i$ cycles of order $m_i$ in that permutation. Each of the cycles can be written in $m_i$ different ways (by starting with a different element). Also, the cycles themselves can appear in any of $k_i!$ possible orders while still representing the same permutation. Thus if, for example, $k_i=2$ and the first cycle contains $a_1,\mathrm{\dots }{a}_l$ while the second contains $b_1,\mathrm{\dots },b_l$, that is the same permutation as if the first cycle contained $b_1,\mathrm{\dots },b_l$ and the second contained $a_1,\mathrm{\dots },a_l$. So there are $k_i!m_i^{k_i}$ equivalent permutations considering the cycles of order $m_i$. So the total number of permutations, considering each of the possible cycle orders, equivalent to the given permutation is

$$(k_1!m_1^{k_1})(k_2!m_2^{k_2})\mathrm{\dots }(k_r!m_r^{k_r})$$

and the result follows. ∎

For example, let $n=5$ and let’s compute the size of the conjugacy class containing the permutation $(23)(45)$. In this case, $r=2$,

$m_1=1$ $,k_1=1$

$m_2=2$ $,k_2=2$

and the skeleton for the permutation is

$$(\cdot )(\cdot \cdot )(\cdot \cdot )$$

There are $5!=120$ ways of placing $1,2,3,4,5$ into this skeleton. However, given a particular choice, say $(2)(13)(45)$, the first $2$-cycle may be written as $(13)$ or as $(31)$, while the second may be written as either $(45)$ or $(54)$. In addition, either pair can appear first ($k_2=2$). The number of choices for ways to represent the $2$-cycles is thus $2!\cdot 2^2=8$. The formula in the theorem indeed predicts that there are $5!/(2!\cdot 2^2)=120/8=15$ permutations with this cycle type; in fact, they are (omitting the trivial $1$-cycles):

$(12)(34)$	$(12)(35)$	$(12)(45)$	$(13)(45)$	$(23)(45)$
$(13)(24)$	$(13)(25)$	$(14)(25)$	$(14)(35)$	$(24)(35)$
$(14)(23)$	$(15)(23)$	$(15)(24)$	$(15)(34)$	$(25)(34)$

Title	conjugacy classes in the symmetric group $S_n$
Canonical name	ConjugacyClassesInTheSymmetricGroupSn
Date of creation	2013-03-22 17:16:24
Last modified on	2013-03-22 17:16:24
Owner	rm50 (10146)
Last modified by	rm50 (10146)
Numerical id	8
Author	rm50 (10146)
Entry type	Topic
Classification	msc 20B05
Classification	msc 20B30
Defines	cycle type