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=\u27e8\sigma \u27e9$ 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=\u27e8\sigma \u27e9$ 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)$ |
References
- 1 D.S. Dummitt, R.M. Foote, Abstract Algebra, Wiley, 2004.
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 |