Skip to content

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

Advertisement

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: