The Unapologetic Mathematician

Mathematics for the interested outsider

Conjugates

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:

\displaystyle\begin{aligned}(1\,5\,2)&(3\,4)\\(2\,3\,1)&(4\,5)\end{aligned}

turn this into two-line notation

\displaystyle\left\lvert\begin{matrix}1&5&2&3&4\\2&3&1&4&5\end{matrix}\right\rvert

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

\displaystyle(1\,2)(3\,4\,5)\cdot(1\,5\,2)(3\,4)\cdot(2\,1)(5\,4\,3)=(1\,2\,3)(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.

About these ads

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

4 Comments »

  1. [...] say and are conjugate elements of the group . That is, there is some so that . I say that for any -module with [...]

    Pingback by Class Functions « The Unapologetic Mathematician | October 15, 2010 | Reply

  2. [...] an example, we can start writing down the character table of . We know that conjugacy classes in symmetric groups correspond to cycle types, and so we can write down all [...]

    Pingback by The Character Table of a Group « The Unapologetic Mathematician | October 20, 2010 | Reply

  3. [...] The Character Table of S4 Let’s use our inner tensor products to fill in the character table of . We start by listing out the conjugacy classes along with their sizes: [...]

    Pingback by The Character Table of S4 « The Unapologetic Mathematician | November 8, 2010 | Reply

  4. [...] for the symmetric group , there’s something we can say. We know that conjugacy classes in symmetric groups correspond to cycle types. Cycles correspond to integer partitions of . And from a partition we [...]

    Pingback by The Road Forward « The Unapologetic Mathematician | December 7, 2010 | 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

Follow

Get every new post delivered to your Inbox.

Join 389 other followers

%d bloggers like this: