PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (194)
Orphanage
Unclass'd
Unproven (498)
Corrections (23)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: High Entry average rating: No information on entry rating
conjugacy classes in the symmetric group $S_n$ (Topic)

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,\ldots,n\}$, and regard $ \sigma$ as acting on $ X$. Let $ G=\langle \sigma\rangle$ 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
$\displaystyle \sigma^i x \leftrightarrow \sigma^i G_x$
is a bijection, where $ G_x$ is the stabilizer of $ x$ in $ G$.

Now, $ G=\langle \sigma\rangle$ 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=\lvert Gx\rvert=[G:G_x]$. Using the explicit bijection above, we see that the unique cosets of $ G_x$ in $ G$ are

$\displaystyle G_x, \sigma G_x, \ldots,\sigma^{d-1} G_x$
and that the elements of $ Gx$ are
$\displaystyle x, \sigma x, \ldots, \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

$\displaystyle \sigma^j x, \sigma^{j+1}x, \ldots,\sigma^{d-1}x, x, \sigma x,\ldots,\sigma^{j-1}x$
which is the same cycle permuted left by $ j$ places. $ \qedsymbol$

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,\ldots,n_k$ with $ n_i\leq n_{i+1}$ for each $ i<k$, then $ n_1,\ldots,n_k$ is the cycle type of $ \sigma$.
The above theorem proves that the cycle type is well-defined.
Theorem 2   Two permutations $ \sigma, \tau\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
$\displaystyle (\alpha_1 \ldots \alpha_a)(\beta_1 \ldots \beta_b)(\ldots)$
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
$\displaystyle \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)

$\displaystyle \sigma$ $\displaystyle =(a_1)(a_2 a_3 a_4)(a_5 \ldots a_n)$    
$\displaystyle \tau$ $\displaystyle = (b_1)(b_2 b_3 b_4)(b_5 \ldots 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,\ldots,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
$\displaystyle \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. $ \qedsymbol$
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. $ \qedsymbol$

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

Theorem 4   Suppose $ \sigma\in S_n$, and let $ m_1,m_2,\ldots m_r$ be the distinct integers (including $ 1$ if applicable) in the cycle type of $ \sigma$, and let there be $ k_i$ cycles of order $ m_i$ in $ \sigma$. (Thus $ \sum k_i m_i=n$). Then the number of conjugates of $ \sigma$ is exactly
$\displaystyle \frac{n!}{(k_1!m_1^{k_1})(k_2!m_2^{k_2})\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 fixed 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,\ldots a_l$ while the second contains $ b_1,\ldots,b_l$, that is the same permutation as if the first cycle contained $ b_1,\ldots,b_l$ and the second contained $ a_1,\ldots,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

$\displaystyle (k_1! m_1^{k_1})(k_2! m_2^{k_2})\ldots (k_r! m_r^{k_r})$
and the result follows. $ \qedsymbol$

For example, let $ n=5$ and let's compute the size of the conjugacy class containing the permutation $ (2~3)(4~5)$. In this case, $ r=2$,

$\displaystyle m_1=1$ $\displaystyle ,\quad k_1=1$    
$\displaystyle m_2=2$ $\displaystyle ,\quad k_2=2$    

and the skeleton for the permutation is
$\displaystyle (\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)(1~3)(4~5)$, the first $ 2$-cycle may be written as $ (1~3)$ or as $ (3~1)$, while the second may be written as either $ (4~5)$ or $ (5~4)$. 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):
$ (1~2)(3~4)$ $ (1~2)(3~5)$ $ (1~2)(4~5)$ $ (1~3)(4~5)$ $ (2~3)(4~5)$
$ (1~3)(2~4)$ $ (1~3)(2~5)$ $ (1~4)(2~5)$ $ (1~4)(3~5)$ $ (2~4)(3~5)$
$ (1~4)(2~3)$ $ (1~5)(2~3)$ $ (1~5)(2~4)$ $ (1~5)(3~4)$ $ (2~5)(3~4)$

Bibliography

1
D.S. Dummitt, R.M. Foote, Abstract Algebra, Wiley, 2004.



"conjugacy classes in the symmetric group $S_n$" is owned by rm50.
(view preamble)

View style:

Also defines:  cycle type
Log in to rate this entry.
(view current ratings)

Cross-references: skeleton, contained, contains, equivalence class, relation, equivalence relation, clear, equivalent, integers, number, conjugate, well-defined, lengths, disjoint, product, size, cosets, power, order, cyclic, stabilizer, bijection, orbits, partitions, orbit-stabilizer theorem, acts on, generated by, subgroup, cyclic permutation, ordering, permutation, cycle, every permutation has a cycle decomposition, proof
There are 6 references to this entry.

This is version 5 of conjugacy classes in the symmetric group $S_n$, born on 2007-06-17, modified 2007-06-18.
Object id is 9613, canonical name is ConjugacyClassesInTheSymmetricGroupS_n.
Accessed 1426 times total.

Classification:
AMS MSC: 20B30 (Group theory and generalizations :: Permutation groups :: Symmetric groups)
 20B05 (Group theory and generalizations :: Permutation groups :: General theory for finite groups)
Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add example | add (any)