Notes on Conjugation in Sn

6. Conjugation in Sn One thing that is very easy to understand in terms of Sn is conjuga­ tion. Definition 6.1. Let g and h be two elements of a group G. The element ghg −1 is called the conjugate of h by g. One reason why conjugation is so important, is because it measures how far the group G is from being abelian. Indeed if G were abelian, then gh = hg. Multiplying by g −1 on the right, we would have h = ghg −1 . Thus G is abelian iff the conjugate of every element by any other element is the same element. Another reason why conjugation is so important, is that really con­ jugation is the same as translation. Lemma 6.2. Let σ and τ be two elements of Sn . Suppose that σ = (a1 , a2 , . . . , ak )(b1 , b2 , . . . , bl ) . . . is the cycle decomposition of σ. Then (τ (a1 ), τ (a2 ), . . . , τ (ak ))(τ (b1 ), τ (b2 ), . . . , τ (bl )) . . . is the cycle decomposition of τ στ −1 , the conjugate of σ by τ . Proof. Since both sides of the equation τ στ −1 = (τ (a1 ), τ (a2 ), . . . , τ (ak ))(τ (b1 ), τ (b2 ), . . . , τ (bl )) . . . are permutations, it suffices to check that both sides have the same effect on any integer j from 1 to n. As τ is surjective, j = τ (i) for some i. By symmetry, we may as well assume that j = τ (a1 ). Then σ(a1 ) = a2 and the right hand side maps τ (a1 ) to τ (a2 ). But τ στ −1 (τ (a1 )) = τ σ(a1 ) = τ (a2 ). Thus the LHS and RHS have the same effect on j and so they must be equal. D In other words, to find compute the conjugate of σ by τ , just translate the elements of the cycle decomposition of σ. For example suppose σ = (3, 7, 4, 2)(1, 6, 5) 1 in S8 and τ is 1 2 3 4 5 6 7 8 . 3 2 5 1 8 7 6 4 Then the conjugate of σ by τ is τ στ −1 = (5, 6, 1, 2)(3, 7, 8). Now given any group G, conjugation defines an equivalence relation on G. Definition-Lemma 6.3. Let G be a group. We say that two elements a and b are conjugate, if there is a third element g ∈ G such that b = gag −1 . The corresponding relation, ∼, is an equivalence relation. Proof. We have to prove that ∼ is reflexive, symmetric and transitive. Suppose that a ∈ G. Then eae−1 = a so that a ∼ a. Thus ∼ is reflexive. Suppose that a ∈ G and b ∈ G and that a ∼ b, that is, a is conjugate to b. By definition this means that there is an element g ∈ G such that gag −1 = b. But then a = g −1 bg = hbh−1 , where h = g −1 . Thus b ∼ a and ∼ is reflexive. Finally suppose that a ∼ b and b ∼ c. Then there are elements g and h of G such that b = gag −1 and c = hbh−1 . Then c = hbh−1 = h(gag −1 )h−1 = (hg)a(hg)−1 = kak −1 , where k = gh. But then a ∼ c and ∼ is transitive. But then ∼ is an equivalence relation. D Definition 6.4. The equivalence classes of the equivalence relation above are called conjugacy classes. Given an aribtrary group G, it can be quite hard to determine the conjugacy classes of G. Here is the most that can be said in general. Lemma 6.5. Let G be a group. Then the conjugacy classes all have exactly one element iff G is abelian. Proof. Easy exercise. D Proposition 6.6. The equivalence classes of the symmetric group Sn are precisely given by cycle type. That is, two permutations σ and σ ' are conjugate iff they have the same cycle type. 2 Proof. Suppose that σ and σ ' are conjugate. Then by (6.2) σ and σ ' have the same cycle type. Now suppose that σ and σ ' have the same cycle type. We want to find a permutation τ that sends σ to σ ' . By assumption the cycles in σ and σ ' have the same lengths. Then we can pick a correspondence between the cycles of σ and the cycles of σ ' . Pick an integer j. Then j belongs to a cycle of σ. Look at the corresponding cycle in σ ' and look at the corresponding entry, call it j ' . Then τ should send j to j ' . D It is easy to check that then τ στ −1 = σ ' . 3