Conjugacy classes of symmetric groups

January 10, 2013

I’m preparing a talk about representations of the symmetric group so I’ll write up some of it on this blog.

Recall that every permutation $\pi \in S_n$ can be uniquely decomposed (modulo the order of the cycles) in a product of disjoint cycles. i.e.

$\pi = (i_{11} \cdots i_{1j_1})(i_{21} \cdots i_{2j_2}) \cdots (i_{m1} \cdots i_{mj_m})$

for some $m$ , where $\sum_{k=1}^{m}j_k = n$ . Here for example the cycle $(1234)$ represents the permutation of the set $\{1,2,3,4\}$ that takes 1 to 2, 2 to 3, 3 to 4 and 4 to 1. If $(i_1 \cdots i_j)$ is some cycle of a permutation in $S_n$ and $\sigma \in S_n$ , then

$\tau := \sigma (i_1 \cdots i_j) \sigma^{-1} = (\sigma(i_1) \cdots \sigma(i_j))$ .

Indeed, let $k \in \{ 1, \ldots, n \}$ . If $k = \sigma(i_l)$ for some $1 \leq l \leq j$ , then $\tau(k) = \sigma(i_{l+1})$ . If not, i.e. if $\sigma^{-1}(k) \notin \{ i_1, \ldots, i_j \}$ , then $\tau(k) = \sigma \sigma^{-1}(k) = k$ .

So for some $\pi \in S_n$ with its decomposition in cycles as above, we have, for $\sigma \in S_n$ ,

$\sigma \pi \sigma^{-1} = \sigma(i_{11} \cdots i_{1j_1}) \sigma^{-1} \sigma (i_{21} \cdots i_{2j_2}) \sigma^{-1} \cdots \sigma (i_{m1} \cdots i_{mj_m}) \sigma^{-1}$

$= (\sigma(i_{11}) \cdots \sigma(i_{1j_1})) \cdots (\sigma(i_{m1}) \cdots \sigma(i_{mj_m}))$ .

This shows that the number of $k-$ cycles $(1 \leq k \leq n)$ in the cycle decomposition of $\pi \in S_n$ is preserved under conjugation. Conversely, if $\pi$ and $\pi'$ have the same number of $k-$ cycles for all $1 \leq k \leq n$ in their cycle decomposition, there is an obvious permutation $\sigma \in S_n$ such that $\pi' = \sigma \pi \sigma^{-1}$ . What we get from this is the fact that the “cycle type” completely determines the conjugacy classes in $S_n$ .

For a positive integer $n \in \mathbb{N}$ , a partition of $n$ is an ordered set of integers $\lambda = \lambda_1 \geq \lambda_2 \geq \cdots \lambda_k$ such that $\sum_{i=1}^k \lambda_k = n$ . The notation $\lambda \vdash n$ indicates that $\lambda$ is a partition of $n$ .

For example, $3 \geq 2 \geq 2 \geq 1 \geq 1 \geq 1 \geq 1$ is a partition of $11$ . One way to compactify the notation would be to write this partition as $32^21^4$ .

There is an obvious bijective correspondence between cycle types of permutations in $S_n$ and partitions of $n$ : to the permutation $(i_{11} \cdots i_{1j_1}) \cdots (i_{m_1} \cdots i_{mj_m})$ is associated the partition $\lambda = j_1, \ldots, j_m$ . The conjugacy classes of $S_n$ are thus indexed by the partitions of $n$ .

The function $p(n)$ that associates to a positive integer $n$ the number of partitions of $n$ has been extensively studied. There is no known closed form for this but according to Wikipedia, Hardy & Ramanujan obtained in 1918 an asymptotic formula for $p(n)$ as $n \rightarrow \infty$ :

$p(n) \sim \dfrac{1}{4n\sqrt{3}} \text{exp} \left( \pi \sqrt{ \dfrac{2n}{3}} \right)$ .

By an easy counting argument, we find that for a given partition $\lambda = 1^{k_1} \cdots n^{k_n}$ of $n$ , the number of elements of $S_n$ in the associated conjugacy class is

$\dfrac{n!}{\displaystyle\prod_{j=1}^n (k_j)! j^{k_j}}$ .

From → Algebra, Representation Theory

One Comment

Trackbacks & Pingbacks

Partitions of n, Young tableaux and tabloids. « arbourj's blog

Conjugacy classes of symmetric groups

Trackbacks & Pingbacks

Leave a Reply Cancel reply

Search

Categories

Tags

Conjugacy classes of symmetric groups

Share this:

Like this:

Related

Trackbacks & Pingbacks

Leave a Reply Cancel reply

Search

Categories

Tags