conjugacy classes in the symmetric group Sn


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

Theorem 1.

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

Proof.

We construct the cycle decomposition for σSn. Let X={1,,n}, and regard σ as acting on X. Let G=σ be the subgroupMathworldPlanetmathPlanetmath of Sn generated by σ. Then G acts on X, so by the orbit-stabilizer theorem, it partitionsMathworldPlanetmathPlanetmath X into a unique set of orbits. In additionPlanetmathPlanetmath, for any orbit Gx, we have that

σixσiGx

is a bijection, where Gx is the stabilizerMathworldPlanetmath of x in G.

Now, G=σ is cyclic and thus G/Gx is cyclic as well; its order is the smallest power d of σ such that σdGx. Note also that d=|Gx|=[G:Gx]. Using the explicit bijection above, we see that the unique cosets of Gx in G are

Gx,σGx,,σd-1Gx

and that the elements of Gx are

x,σx,,σd-1x

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

Uniqueness now follows easily, since the cycle determined by σ on an element of order d is determined uniquely by construction from the element. Choosing a different element in the same orbit, say σjx, gives instead

σjx,σj+1x,,σd-1x,x,σx,,σj-1x

which is the same cycle permuted left by j . ∎

We can thus write

Definition 1.

If σSn and σ is written as the product of the disjoint cycles of lengths n1,,nk with nini+1 for each i<k, then n1,,nk is the cycle type of σ.

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

Theorem 2.

Two permutations σ,τSn are conjugatePlanetmathPlanetmath if and only if they have the same cycle type.

Proof.

Assume first that σ and τ are conjugate; say τ=σ1σσ1-1. Write σ as a product of disjoint cycles

(α1αa)(β1βb)()

To show that σ and τ have the same cycle type, it clearly suffices to show that if j follows i in the cycle decomposition of σ, then σ1(j) follows σ1(i) in the cycle decomposition of τ. But suppose σ(i)=j. Then

τ(σ1(i))=σ1σσ1-1(σ1(i))=σ1σ(i)=σ1(j)

and we are done.

Now suppose σ and τ 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)

σ =(a1)(a2a3a4)(a5an)
τ =(b1)(b2b3b4)(b5bn)

Define σ1 to be the permutation that takes ai to bi. Clearly σSn, since each of 1,,n appears exactly once among the ai and once among the bi. But also, since the cycle types of σ and τ match, we see that

σ1σσ1-1(bi)=σ1σ(ai)=σ1(aj)=bj

where aj, bj are the ”‘next”’ elements in their respective cycles. Thus τ=σ1σσ1-1 and we are done. ∎

Corollary 3.

The number of conjugacy classesMathworldPlanetmath in Sn is the number of partitions of n.

Proof.

Each distinct cycle type in Sn 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 Sn.

Theorem 4.

Suppose σSn, and let m1,m2,mr be the distinct integers (including 1 if applicable) in the cycle type of σ, and let there be ki cycles of order mi in σ. (Thus kimi=n). Then the number of conjugates of σ is exactly

n!(k1!m1k1)(k2!m2k2)(kr!mrkr)
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 equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath if they define the same permutation. It is clear that this is an equivalence relation, and that the relationMathworldPlanetmathPlanetmath partitions the arrangements. We will determine the size of each equivalence classMathworldPlanetmath.

Consider a particular arrangement (i.e. permutation), and consider the ki cycles of order mi in that permutation. Each of the cycles can be written in mi different ways (by starting with a different element). Also, the cycles themselves can appear in any of ki! possible orders while still representing the same permutation. Thus if, for example, ki=2 and the first cycle contains a1,al while the second contains b1,,bl, that is the same permutation as if the first cycle contained b1,,bl and the second contained a1,,al. So there are ki!miki equivalent permutations considering the cycles of order mi. So the total number of permutations, considering each of the possible cycle orders, equivalent to the given permutation is

(k1!m1k1)(k2!m2k2)(kr!mrkr)

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,

m1=1 ,k1=1
m2=2 ,k2=2

and the skeleton for the permutation is

()()()

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 (k2=2). The number of choices for ways to represent the 2-cycles is thus 2!22=8. The formulaMathworldPlanetmathPlanetmath in the theorem indeed predicts that there are 5!/(2!22)=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 groupMathworldPlanetmathPlanetmath Sn
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