Lecture 21: Conjugacy Classes for Symmetric and Alternating Groups

Lecture 21: Symmetric and Alternating Groups 21 21.1 Conjugacy Classes for Symmetric and Alternating Groups Review Recently, we have been discussing the conjugation action of a group on itself. In particular, it is possible to decompose a group into its conjugacy classes, which is similar to decomposing a set into its orbits (like we were doing last week). Last time, we looked at the icosahedral group and saw its class equation and fgured out information based on that. 21.2 Cycle Type Today, we will be looking at the conjugacy classes for Sn and An , the symmetric group and the alternating group, which consists of even permutations. Recall that a permutation σ ∈ Sn can be written in cycle notation. This is a very useful way of writing a permutation. Example 21.1 (Cycle Notation) For example, the permutation (123)(45) takes 1 to 2 to 3 to 1, and 4 to 5 back to 4. Given the cycle type, it is easy to defne and fgure out the sign of a permutation. A 1-cycle will have sign +1, a 2-cycle will have sign −1, and so on, where a k-cycle will have sign (−1)k−1 . For example, (123)(45) has sign −1 = (+1)(−1) = −1, where the signs of each cycle are multiplied. In particular, even permutations are permutations that have an even number of even-length cycles.75 Guiding Question What are the conjugacy classes of Sn ? It turns out that the sign will be a very helpful tool in determining the conjugacy classes. Let’s look at an example. Example 21.2 If σ = (123), then for p ∈ Sn , let the conjugate be τ = pσp−1 . Let’s say p(1) = i, p(2) = j, and p(3) = k. Evaluating the conjugate on i gives τ (i) = pσp−1 (p(1)) = p(σ(1)) = p(2) = j. Similarly, τ (j) = p(σ(2)) = p(3) = k. It turns that in cycle notation, τ = (ijk) = (p(1)p(2)p(3)). It is easy to check that τ fxes all the other points. So conjugating a 3-cycle produces another 3-cycle with diferent points. Consider a more complicated permutation. 75 It’s confusing: an even-length cycle makes a permutation odd. Lecture 21: Symmetric and Alternating Groups Example 21.3 For σ = (123)(47) · · · , conjugating by p gives (p(1)p(2)p(3))(p(4)p(7)) · · · . It turns out that the lengths of the cycles in a permutation don’t change upon conjugation! Defnition 21.4 Given σ ∈ Sn , the cycle type of σ is the number of 1-cycles, 2-cycles, and so on, that show up in the cycle notation. The cycle type is conjugation-invariant. If τ = pσp−1 , then σ and τ have the same cycle type. For example, (47)(123) has cycle type (2, 3). In fact, if σ and τ have the same cycle type, then they are conjugate. Example 21.5 Take σ = (145)(23) and τ = (234)(15). Simply by matching cycles, we can defne p ∈ Sn taking 1 7−→ 2, 4 7−→ 3, 5 7−→ 4, 2 7−→ 1, and 3 7−→ 5; that is, p = (12)(354). This p is constructed to be such that pσp−1 = τ.a a Try working through this by hand! The upshot is this proposition. Proposition 21.6 Two permutations σ and τ are conjugate if and only if σ and τ have the same cycle type. 21.3 Conjugacy Classes in Sn Conjugation in Sn can be understood well by looking at cycles. Guiding Question What are the conjugacy classes in Sn ? From our characterization of when two permutations are conjugate, this can certainly be done! Let’s start with an example. Example 21.7 For S3 , there are three conjugacy classes: cycle type 3, 2 + 1, and 1 + 1 + 1. For example, representatives could be (123), (12), and the identity permutation. Now, we can do more complicated computations. For instance, we may want to fnd out the size of a given conjugacy class. Lecture 21: Symmetric and Alternating Groups Example 21.8 (Conjugacy classes in S4 ) For a permutation x = (1234) ∈ S4 , the conjugacy class C(x) is all 4−cycles in S4 . For each 4-cycle, there are 24 orderings of 1, 2, 3, and 4, and each one is overcounted by a factor of 4. For example, (1234) = (2341) = (3412) = (4123). So there are 24/4 = 6 elements in the conjugacy class. Alternatively, where the stabilizer is Z(x), then |C(x)| = |G| . |Z(x)| Since conjugation is essentially "relabeling" the numbers in the original permutation, replacing 1 with p(1), 2 with p(2), and so on, the elements in the stabilizer should relabel the numbers 1 through n in such a way that the permutation is still the same. For instance, relabeling (1234) to (2341) gives the same permutation x. In this case, because there are 4 diferent starting points to the cycle, there are 4 permutations p ∈ Z(x) that stabilize x. So again, |G| 24 |C(x)| = = = 6. |Z(x)| 4 Essentially, the redundancy in cycle notation gives us diferent ways to write the same permutation, and dividing out by this redundancy (the stabilizer) gives the size of the conjugacy class. Cycle notation also simplifes these computations for larger symmetric groups. Example 21.9 (Conjugacy Class in S13 ) Consider x = (123)(456)(78910)(11)(12)(13) ∈ S13 . What is the stabilizer Z(x) of x? For the 4-cycles, there are 4 choices for where to start the cycle. Any reordering of 12, 11, and 13 doesn’t change the fact that 12, 11, and 13 are fxed; there are 3! ways to order the 1-cycles. For the 3-cycles, there are 3 starting points each, but the 3-cycle (123) could also be mapped to (456), so there are 2! ways to order the two 3-cycles, and 3 starting points each. In general, if there are k ℓ−cycles, there are ℓ starting points for each cycle, and k! ways to order them. So |Z(x)| = 2! · 3 · 3 · 4 · 3! · 1 · 1 · 1 = 432. Then, |C(x)| = 13! . 432 So fnding the sizes of conjugacy classes is really just doing some combinatorics for the size of stabilizer. Given the size of the stabilizer, since we know the size of the entire group, |Sn | = n!, dividing by |Z(x)| directly gives |C(x)|, without having to compute every permutation in the conjugacy class. 21.4 Class Equation for S4 Now, we can work out the class equation for S4 without too much pain. Lecture 21: Symmetric and Alternating Groups Example 21.10 (Class Equation for S4 ) The order of S4 is |S4 | = 4! = 24. Then, there are only fve possible cycle types, listed on the left column of the table. These are the diferent ways to sum to 4. cycle type 4 3+1 2+1+1 2+2 1+1+1+1 |Z(x)| 4 3 2 · 2! = 4 2! · 2 · 2= 8 24 |C(x)| 6 8 6 3 1. The size of the stabilizer for cycle type 4 is 4, as we worked out already. For 3, there are three possible places to start the cycle, so there are three permutations fxing the cycle type. For 2 + 1 + 1, there are 2 ways to pick a starting point for the 2-cycle and 2! = 4 ways to order the 1-cycles, which gives 4 total. The rest of the middle row follows similarly. We have |C(x)| = |G|/|Z(x)|, so the right row, the size of the conjugacy class, is found by dividing |G| = 24 by the middle row, the size of the stabilizer. The class equation then says 24 = 1 + 3 + 6 + 8 + 6. What about the alternating group? The conjugacy classes for A4 can also be determined. Example 21.11 (Conjugacy classes for A4 ) What are the conjugacy classes for A4 ? The alternating group A4 is a subgroup of S4 . In fact it is the kernel of the sign homomorphism, so it is a normal subgroup. In particular, a normal subgroup is fxed under conjugation, so A4 is the union of conjugacy classes. Using the defnition of the sign, the cycle types 3 + 1, 2 + 2, and 1 + 1 + 1 + 1 all correspond to the elements in A4 . Then, taking the sizes of the corresponding conjugacy classes, we have |A4 | = 12 = 1 + 3 + 8, but since 8 is not a factor of 12, this is actually not the class equation for A4 . What’s going wrong? If an element σ is conjugate to another element τ in A4 , it is a diferent notion than being σ being conjugate to τ in S4 ! In particular, σ and τ can be conjugate in S4 , since we need τ = pσp−1 for p ∈ S4 , without being conjugate in A4 , since we require that τ = qσq −1 for q ∈ A4 . If it is possible to fnd two elements conjugate by an odd permutation but not an even permutation, then they will be conjugate in S4 but not A4 . Consider x ∈ An ≤ Sn . The conjugacy class of x in An is CA (x) = {y ∈ A : y = pxp−1 , p ∈ An }, the subset of elements in An conjugate to x by some even permutation, which is a subset of CS (x) = {y ∈ An : y = pxp−1 , p ∈ Sn }. Similarly, the stabilizer for A is a subgroup of the stabilizer for S. ZA (x) = {p ∈ An : px = xp} ≤ ZS (x) = {p ∈ Sn : px = xp}. Using the counting formula, |CA (x)| · |ZA (x)| = |An | = so |CA (x)| · |ZA (x)| = 1 |Sn |, 2 1 |CS (x)| · |ZS (x)|. 2 Lecture 21: Symmetric and Alternating Groups The product difers by a factor of 2 for An and Sn . Additionally, |ZA (x)| is a factor of |ZS (x)|, as it is a subgroup. Our analysis leads us to two possibilities: • Case 1. In this case, |CA (x)| = |CS (x)| and |ZA (x)| = 12 |ZS (x)|. Here, the conjugacy class stays the same size, but only half of the permutations that stabilize them are even and in An . • Case 2. In this case, |CA (x)| = 12 |CS (x)| and |ZA (x)| = |ZS (x)|. So the size of the conjugacy class is split in half when going from Sn to An , and only half of them are conjugate by even permutations. Since the sizes of the stabilizers of x are the same, every p ∈ Sn such that px = xp is even, and lives inside of An . In our example, 8 must split, since it does not divide 12, and 1 and 3 cannot split because when they are split, they are split into halves, and they are odd numbers. Thus, the class equation for A4 must be, by simple numerics, |A4 | = 12 = 1 + 3 + 4 + 4. In the 8 = 4 + 4 case, x = (123), and this is the case where the conjugacy class does split, which means the stabilizer group does not get any smaller. Thus, every p such that px = xp is even. This is what it means for the stabilizer group not to get any smaller! Example 21.12 What happens for S5 ? What about A5 ? For S5 , the class equation looks like 120 = 1 + 10 + 15 + 20 + 20 + 30 + 24 . The even classes have size 1, 15, 20, and 24. We currently have |A5 | = 60 = 1 + 15 + 20 + 24, which is not the class equation. Clearly, 1 and 15 do not split, since they are odd. Since 24 is not a factor of 60 (but 24/2 = 12 is), it must split. The question remains if 20 splits into 10 + 10 or not. We can show directly that there is an odd permutation that commutes with it, and so it cannot split. So the class equation is 60 = 1 + 15 + 20 + 12 + 12 . These examples demonstrate that after our analysis of cycle types in symmetric and alternating groups, determining the class equation is not so much algebra and more counting and combinatorics. 21.5 Student Question Student Question. Why do we care about An ? Does it show up as the symmetry group of some object? Answer. Since we are working with low numbers and dimensions, there are lots of coincidences where the groups that show up will be the same as each other, even if they aren’t actually related in a general way for higher dimensions. In fact, A4 shows up in the symmetry group of the tetrahedron, and we had A5 show up as the symmetry group of the icosahedron. But in general, An is (maybe? Davesh said he didn’t really know/hadn’t thought about it) not necessarily the symmetry group of some higher-dimensional geometric object. But in 18.702 we will study the symmetries of equations (Galois frst studied these) instead of geometric objects, and it is very easy to write down equations that have An or Sn as (part of ) their symmetry groups. In fact, group theory evolved at the same time as studying symmetries of non-geometric objects evolved (Galois again?) The reason why we care about An is this idea that simple groups are "building blocks" in some sense, and An for n = 5 and higher is simple, and in fact it is essentially the only (interesting?) simple normal subgroup of Sn . So if we care about Sn then we automatically care about An , since An is a "building block" of Sn . In general, people like to break down problems into studying the simple subgroups of certain groups, and then studying the ways in which the simple groups can combine into the larger groups, in order to understand the larger group as a whole. Lecture 21: Symmetric and Alternating Groups There are lots of ways of combining groups that get pretty complicated, and this is defnitely something a lot of people are working on. The two ways of combining groups that get their own names are the "direct product" and the "semidirect product," which is a slightly more nonabelian way of combining groups. In this case, getting from An to Sn is just a semidirect product in some way.