The Unapologetic Mathematician

Mathematics for the interested outsider


For some more review, let’s recall the idea of conjugation in a group G. We say that two elements g and h are “conjugate” if g=khk^{-1} for some k\in G.

This is an equivalence relation — reflexive, symmetric, and transitive. Any element g is conjugate to itself by the group identity; if g=khk^{-1}, then h=k^{-1}g\left(k^{-1}\right)^{-1}; if f=jgj^{-1} and g=khk^{-1}, then f=(jk)h(jk)^{-1}. Thus the set underlying the group G can be partitioned into “conjugacy classes”: two group elements are in the same conjugacy class if and only if they are conjugate. The conjugacy class containing a group g is commonly written K_g. The different conjugacy classes are pairwise disjoint, and their union is all of G.

Now, since these days we’re concerned with the symmetric group. And it turns out that some nice things happen in this case. We’ve actually already seen a lot of these!

First of all, when we write a permutation in cycle notation it’s easy to see what conjugation does to it. Indeed, if (a_1\,a_2\,\dots\,a_k) is a k-cycle and if g is any other permutation, then we can write down the conjugate:

\displaystyle g(a_1\,\dots\,a_k)g^{-1}=(g(a_1)\,\dots\,g(a_k))

And the same goes for any other permutation written in cycle notation: the conjugate by g is given by applying g to each symbol in the cycle notation. In particular, any two conjugate permutations have the same cycle type. In fact, the converse is also true: given any two permutations with the same cycle type, we can find a permutation that sends the one to the other.

For example, consider the permutations (1\,5\,2)(3\,4) and (2\,3\,1)(4\,5). Stack them on top of each other:


turn this into two-line notation


and we’ve got a permutation (1\,2)(3\,4\,5) which sends (1\,5\,2)(3\,4) to (2\,3\,1)(4\,5):


which is equivalent to (2\,3\,1)(4\,5). That is, two permutations are conjugate if and only if they have the same cycle type. This is really big. Given a cycle type \lambda, we will write the corresponding conjugacy class as K_\lambda.

We also know from some general facts about group actions that the number of elements in the conjugacy class K_g is equal to the number of cosets of the “centralizer” Z_g. We recall that the centralizer of g is the collection of group elements that commute with g. That is:

\displaystyle Z_g=\left\{h\in G\vert hgh^{-1}=g\right\}

and we have the equation

\displaystyle\lvert K_g\rvert=\frac{\lvert G\rvert}{\lvert Z_g\rvert}

In the case of S_n — and armed with our formula for conjugating permutations in cycle notation — we can use this to count the size of each K_\lambda. We know that \lvert S_n\rvert=n!, so all we need is to find out how many permutations h leave a permutation g (with cycle type \lambda) the same when we conjugate it to get hgh^{-1}. We will write this number as z_\lambda=\lvert Z_g\rvert, and similarly we will write k_\lambda=\lvert K_\lambda\rvert=\lvert K_g\rvert.

So, how can we change the cycle notation of g and get something equivalent back again? Well, for any k-cycle in g we can rotate it around in k different ways. For instance, (1\,2\,3) is the same as (2\,3\,1) is the same as (3\,1\,2). We can also shuffle around any cycles that have the same length: (1\,2)(3\,4) is the same as (3\,4)(1\,2).

Thus if g has cycle type \lambda=(1^{m_1},2^{m_2},\dots,n^{m_n}), then we can shuffle the 1-cycles m_1! ways; we can shuffle the 2-cycles m_2! ways; and so on until we can shuffle the n-cycles m_n! ways. Each 1-cycle can be rotated into 1 different position for a total of 1^{m_1} choices; each 2-cycle can be rotated into 2 different positions for a total of 2^{m_2} choices; and so on until each n-cycle can be rotated into n different positions for a total of n^{m_n} choices. Therefore we have a total of

1^{m_1}m_1!2^{m_2}m_2!\dots n^{m_n}m_n!

different ways of writing the same permutation g. And each of these ways corresponds to a permutation in Z_g. We have thus calculated

\lvert Z_g\rvert=1^{m_1}m_1!2^{m_2}m_2!\dots n^{m_n}m_n!

and we conclude

\displaystyle k_\lambda=\lvert K_g\rvert=\frac{\lvert S_n\rvert}{\lvert Z_g\rvert}=\frac{n!}{z_\lambda}=\frac{n!}{1^{m_1}m_1!2^{m_2}m_2!\dots n^{m_n}m_n!}

As a special case, how many transpositions are there in the group S_n? Recall that a transposition is a permutation of the form (a\,b), which has cycle type (1^{n-2},2^1,3^0,\dots,n^0). Our formula tells us that there are

\displaystyle\frac{n!}{1^{n-2}(n-2)!2^11!3^00!\dots n^00!}=\frac{n!}{(n-2)!2}=\binom{n}{2}

permutations in this conjugacy class, as we could expect.

September 10, 2010 Posted by | Algebra, Group theory, Representation Theory, Representations of Symmetric Groups | 4 Comments



Get every new post delivered to your Inbox.

Join 366 other followers