Is there a systematic way of finding the conjugacy class and/or centralizer of an element?

Is there a systematic way of finding the conjugacy class and centralizer of an element? Could the task be simplified if we are working with "special groups" such as $S_n$ or $A_n$? Are there any intuitive approaches? Thanks.

-
Does anyone know if a group has such an algorithm (to calculate the conjugacy class of an element) then the conjugacy problem for that group is soluble (the obvious algorithm won't terminate in an infinite group)? Would such an algorithm and the conjugacy problem be related? –  user1729 Jan 25 '12 at 10:40

Well, I am happy you call the groups, $S_n$ and $A_n$ special. They are!

So, I'll describe a method for calculating the conjugacy class and hence the centralizer in $S_n$.

Step 1:

This comes from realising that any two elements of the same cycle type are conjugate to each other in $S_n$. How do we prove this startling result?

Proof.

Lemma

For any $\tau, \sigma \in S_n$, since, $\sigma$ is a product of disjoint cycles, let's say for instance, that, cycle decomposition of $\sigma$ is given by $$\sigma=(a_1a_2a_3\cdots a_k)(b_1b_2b_3\cdots b_l)\cdots$$

We claim that $\tau\sigma\tau^{-1}=(\tau(a_1)\tau(a_2)\cdots\tau(a_k))(\tau(b_1)\tau(b_2)\cdots\tau(b_l))\cdots$

Proof of Lemma: The proof is subtle. Suppose $i \overset{\sigma}{\mapsto}j$, we'll prove that $\tau(i) \overset{\tau\sigma\tau^{-1}}{\mapsto}\tau(j)$.

Now \begin{align*}\tau\sigma\tau^{-1}(\tau(i))&=\tau(\sigma(i))\\&=\tau(j)\end{align*} This proves the claim. $\diamond$

So, the cycle type of an element and its conjugate are the same. So, this proves that all elements of the same cycle type are conjugate to each other.$~~~~~~~~~~\blacksquare$

Step-2

This step is a little intuitive. We claim that the number of conjugacy classes in $S_n$ equals the partition of $n$.

Proof.

Firstly, let's prove that the number of cycle types in $S_n$ equal the number of partitions of $n$. The proof of this is rather intuitive. With any permutation, associate the partition whose parts equal the number of elements in a cycle. This gives you the required bijection between the cycle types of $S_n$ and partition of $n$.

To get a feel for it, look at the following in $S_4$:

\begin{align*}(1234)&\cong 4\\(12)(34) &\cong 2+2\\ (34) &\cong 1+1+2(\text{since (1) and (2) are omitted in this notation})\end{align*}

So, now, since two elements of the same cycle type are conjugate in $S_n$$^\dagger, we have that they belong to the same conjugacy class. So, counting the number of cycle types gives you the number of conjugacy classes. So, we have that the number of conjugacy classes is equal to the number of partitions of n. \blacksquare So, we have so far described the conjugacy classes in S_n. But, unfortunately, human brain cannot defeat the symmetry in nature, thanks to people like Ramanujan, little atleast is known about p(n), the number of partitions of n. Among the little, a closed form formula is not one! Now, use the orbit-stabilizer lemma, with the understanding that stabilizer of a point under conjugacy is nothing but its centralizer. For a specific example such as the one you asked Gerry through comments, you can actually work through with this description. For instance, (1234567) in S_n A little more machinery is involved! You need to find the number of r-cycles in S_n for appropriate r. This is merely a combinatorial argument: You should find that this equals,$$\dfrac{\binom{n}{r}\cdot r!}{r}$$Centralizer of (1234567): Nextly, we describe the form of the element that commutes with this element. It should be precisely,$$(1234567)^i \sigma~;~~0\leq i < 6 ~~~\text{$\sigma$is disjoint from$(1234567)$}$$The facts you'll need are: • The order of an$r$-cycle is$r$• Disjoint cycles commute • Cyclic groups are also abelian. Hope this helps. References: Herstein's Exercises and Dummit and Foote's description.$\dagger$This requires a proof! The reader is advised to prove this and not take it on faith because, having written this detailed answer, I'd have added this as well, if I knew the argument :) - I am always willing to add more details, if sought! So, feel free to write to me in the form of comments here! – user21436 Jan 25 '12 at 2:33 Thanks, Kannappan! What if I want a description of the centralizer of (1234567) in$S_n$, So I can't work out the explicit details then compare the elements? Is there a general description? Or am I limited to saying that it contains the elements$\sigma$so that$(\sigma (1) \sigma(2)...\sigma(7))=(1234567)$? – Wanda Jan 25 '12 at 10:19 I have described its centralizer in the last paragraph. (i.e.) I have described the form of the elements that commute with$(1234567)$. So, That's best we can, without sophisticated techniques. And, yes, we can calculate the cardinality of the centralizer! – user21436 Jan 25 '12 at 11:11 Indeed, thanks, but is it possible to show the elements of that form are the only elements that commute with (1234567)? For example doesn't (123456789) also commute with (1234567)? – Wanda Jan 25 '12 at 11:54 Why are you asking whether two elements commute, when you can figure it out on your own? Alternatively, does$(123)$commute with$(12)$? – Gerry Myerson Jan 25 '12 at 12:06 For a finite group, there is a perfectly systematic way: to find the conjugacy class of$x$, just compute every element$g^{-1}xg$, and to find the centralizer, just compare$gx$to$xg$for all$g$in the group. For$S_n$, two elements are conjugate if and only if they have the same cycle structure. So$(123)(45)$is conjugate to$(396)(47)$in$S_9$, but not to$(12)(45)$or$(12345)$or.... There are lots of ways to use other facts you may know about a group or about an element in a group to simplify the calculation of a conjugacy class or a centralizer, but I'm afraid there is no systematic way to list all these facts. They just come with doing examples or reading worked examples in textbooks. - Thanks, suppose I want to find the centralizer of (1234567) in any$S_n$, how might I do that? I would I know what commutes with a given element? – Wanda Jan 25 '12 at 0:55 @Wanda: multiply everything with your element from both left and the right and compare the results? – Henning Makholm Jan 25 '12 at 1:19 First, you can find the size of the conjugacy class of$(1234567)$. Then, you have probably seen a theorem relating the size of the conjugacy class to the size of the centralizer; use this to find the size of the centralizer. Now, there are some elements that "obviously" commute with$(1234567)$; to begin with, its powers, and any permutation disjoint from it. Compare the number of these obvious elements with the known size of the centralizer. If they are equal, you are done. If not, you have to look a little harder to find some not-so-obvious elements commuting with$(1234567)$. – Gerry Myerson Jan 25 '12 at 1:46 There is of course a systematic way of describing the centralizer of a permutation in$S_n\$, as a direct product of wreath products. I seem to remember that this came up before. –  Derek Holt Jan 25 '12 at 6:28
What part of my write-up wasn't general? –  Gerry Myerson Jan 25 '12 at 12:02