Abstract Nonsense

Crushing one theorem at a time

Conjugacy Classes on the Symmetric Group


Point of Post: In this post we discuss the conjugacy class structure of the symmetric group S_n.

\text{ }

Motivation

Often times knowing the conjugacy classes of a group gives you much information about the group. In particular, we have seen that the number of irreducible characters of a group G is equal to the number of conjugacy classes of G. That said, it is often difficult without getting one’s hands dirty to find all the conjugacy classes of a group, and moreover finding the number of elements in each such class. It is an interesting fact that for one of the most important groups (for example, the ‘comfort theorem’ given by Cayley) has easily findable conjugacy classes, and even explicitly computable sized classes–I am of course talking about the symmetric group. So, in this post we shall classify the conjugacy classes of S_n and find their order.

\text{ }

Cycle Type

\text{ }

Before we can talk about the conjugacy classes of S_n we must discuss the cycle type of an element of S_n. In particular we know that every element \pi\in S_n can be written as the product of disjoint cycles, and moreover that up to a permutation of the cycles the product is unique. Thus, every element of S_n may be expressed uniquely as the disjoint product of some number of 1-cycles, some number of 2-cycles, all the way up to some number of n-cycles. If \pi\in S_n can be written as the product of k_1 1-cycles, all the way up to k_n n-cycles we say that \pi is of type 1^{k_1}\cdots n^{k_n} or equivalently that \pi has cycle type 1^{k_1}\cdots n^{k_n} which is also sometimes written (k_1,\cdots,k_n). When convenient we denote the cycle type of \pi by \text{type}(\pi). For example, for \pi\in S_8 given by \pi=(1,2,3)(5)(6)(7,8) then \text{type}(\pi)=1^22^13^14^05^06^07^08^0.

\text{ }

Conjugacy Classes of S_n

\text{ }

Now that we have defined cycle type we may now state the main theorem of this post. Namely:

\text{ }

Theorem: Let S_n denote the symmetric group. Then, for any\pi and \pi' in S_n one has that \pi is conjugate to \pi' if and only if \text{type}(\pi)=\text{type}(\pi').

Proof: We begin by noting that if \sigma\in S_n and (a_1,\cdots,a_m) is a cycle on S_n then

\text{ }

\sigma(a_1,\cdots,a_m)\sigma^{-1}=(\sigma(a_1),\cdots,\sigma(a_m))

\text{ }

With this observation in hand we note then if \text{type}(\pi)=\text{type}(\pi') then we may write

\text{ }

\pi=(a_{1,1,1})\cdots(a_{1,k_1,1})\cdots (a_{n,1,1},\cdots,a_{n,1,n})\cdots(a_{n,k_n,1},\cdots,a_{n,k_n,n})

\text{ }

(where the indices mean \text{what size cycle},\text{ what number cycle of that size cycle},\text{what element in that particular cycle}) and

\text{ }

\pi'=(b_{1,1,1})\cdots(b_{1,k_1,1})\cdots (b_{n,1,1},\cdots,b_{n,1,n})\cdots(b_{n,k_n,1},\cdots,b_{n,k_n,n})

\text{ }

and so (since they are written in disjoint cycle notation, thus the numbers appearing form a partition) we may define \sigma\in S_n by \sigma(a_{q,r,s})=b_{q,r,s} and so

\text{ }

\sigma\pi\sigma^{-1}=\sigma(a_{1,1,1})\sigma^{-1}\sigma\cdots\sigma^{-1}\sigma(a_{1,k_1,1})\sigma^{-1}\sigma\cdots \sigma^{-1}\sigma(a_{n,1,1},\cdots,a_{n,1,n})\sigma^{-1}\sigma\cdots\sigma^{-1}\sigma(a_{n,k_n,1},\cdots,a_{n,k_n,n})\sigma^{-1}

\text{ }

but by our observation this is equal to

\text{ }

(\sigma(a_{1,1,1}))\cdots(\sigma(a_{1,k_1,1}))\cdots (\sigma(a_{n,1,1}),\cdots,\sigma(a_{n,1,n}))\cdots(\sigma(a_{n,k_n,1}),\cdots,\sigma(a_{n,k_n,n}))

\text{ }

which by construction is equal to \pi'.

\text{ }

Conversely, if \pi and \pi' are conjugate,using \pi‘s disjoint cycle notation from above and the same calculation, we see that

\text{ }

\pi'=\sigma\pi\sigma^{-1}=(\sigma(a_{1,1,1}))\cdots(\sigma(a_{1,k_1,1}))\cdots (\sigma(a_{n,1,1}),\cdots,\sigma(a_{n,1,n}))\cdots(\sigma(a_{n,k_n,1}),\cdots,\sigma(a_{n,k_n,n}))

\text{ }

and since \sigma is a bijection so that this last cycle decomposition is a disjoint cycle decomposition we may conclude that \text{type}(\pi)=\text{type}(\pi'). \blacksquare

\text{ }

\text{ }

Thus, we see that each conjugacy class of S_n corresponds uniquely to a cycle type 1^{k_1}\cdots n^{k_n}— consequently we will often refer to a conjugacy class in S_n by the corresponding cycle type of its elements. The interesting thing is that we can calculate the size of this conjugacy class. Namely:

\text{ }

Theorem: Let 1^{k_1}\cdots n^{k_n} be a conjugacy class in S_n. Then, the cardinality of this conjugacy class is

\text{ }

\displaystyle \frac{n!}{k_1!1^{k_1}\cdots k_n! n^{k_n}}=\prod_{j=1}^{n}\frac{n}{k_j!j^{k_j}}

\text{ }

Proof: Let \pi=(a_{1,1,1})\cdots(a_{1,k_1,1})\cdots (a_{n,1,1},\cdots,a_{n,1,n})\cdots(a_{n,k_n,1},\cdots,a_{n,k_n,n}) be an element of 1^{k_1}\cdots n^{k_n}. We seek to find the size of the centralizer \bold{C}_G(\pi). To do this we note that by our previous observation that for any \sigma\in S_n we have that

\text{ }

\sigma\pi\sigma^{-1}=(\sigma(a_{1,1,1}))\cdots(\sigma(a_{1,k_1,1}))\cdots (\sigma(a_{n,1,1}),\cdots,\sigma(a_{n,1,n}))\cdots(\sigma(a_{n,k_n,1}),\cdots,\sigma(a_{n,k_n,n}))

\text{ }

We thus see that \sigma must map a j-cycle to a j-cycle for which there are k_j! ways to do. Thus, if we fix a particular permutation of the j-cycles then choosing a particular j-cycle we see that \sigma must only cyclically permute the elements of this cycle, for which there are obviously j ways to do, and thus within each fixed choice of permutations of the j-cycles there are j^{k_j} choices for \sigma‘s action. Thus, for each j\in[n] there are k_j! j^{k_j} choices and thus the total number of choices for \sigma is k_1!1^{k_1}\cdots k_n! n^{k_n}. Thus, we may conclude that \#\left(\bold{C}_G(\pi)\right)=k_1!1^{k_1}\cdots k_n! n^{k_n} from where the conclusion follows by the orbit-stabilizer theorem. \blacksquare

\text{ }

\text{ }

References:

1. Simon, Barry. Representations of Finite and Compact Groups. Providence, RI: American Mathematical Society, 1996. Print.

Advertisements

May 10, 2011 - Posted by | Algebra, Group Theory | , , , , ,

1 Comment »

  1. […] It is clear from our classification of conjugacy classes in that the number of conjugacy classes is equal to the number of different […]

    Pingback by Partitions, Ferrer’s Diagrams, and Young Tableaux « Abstract Nonsense | May 10, 2011 | Reply


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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: