Brian Bi

Return to table of contents for Brian's unofficial solutions to Artin's Algebra

Section 7.5. Conjugation in the Symmetric Group

Exercise 7.5.1

The proof is by induction. Clearly the claim holds for \(n = 1\) and \(n = 2\). For the inductive case, suppose \(\sigma \in S_n\) and consider \(\sigma\) as a bijection on \(\{1, \ldots, n\}\). Suppose \(\sigma(n) = k\). Let \(\sigma' = (n\ n-1)(n-1\ n-2) \ldots (k+1\ k) \sigma\). Then \(\sigma'(n) = n\). This implies that the restriction of \(\sigma'\) to \(\{1, \ldots, n-1\}\) is a permutation. By the induction hypothesis, \(\sigma'\) is a product of transpositions. Therefore \(\sigma = (k\ k+1)\ldots(n-2\ n-1)(n-1\ n)\sigma'\) is a product of transpositions.
As \((1\ 2\ 3 \ldots n) = (1\ 2)(2\ 3)\ldots(n-1\ n)\), it is clear that \(n-1\) transpositions suffice, even when they are required to only transpose adjacent elements. We will also show that \(n-1\) transpositions are required. Define \(I(\sigma) = \sum_{C \in \sigma} (|C| - 1)\) where \(C\) ranges over all cycles in the cycle decomposition of \(\sigma\). Clearly \(I(1) = 0\) and \(I((1\ 2\ 3 \ldots n)) = n-1\). Let \(\sigma \in S_n\) and let \(\tau = (i\ j)\) be a transposition. If neither \(i\) nor \(j\) is permuted by \(\sigma\), then \(I(\tau\sigma) = I(\sigma) + 1\). If either \(i\) or \(j\) is permuted by \(\sigma\) but not the other, then the effect of left-multiplication by \(\tau\) is merely to lengthen one cycle, and again \(I(\tau\sigma) = I(\sigma) + 1\). If both \(i\) and \(j\) are permuted by \(\sigma\) but belong to different cycles, then left-multiplication by \(\tau\) joins together the two cycles, and \(I(\tau\sigma) = I(\sigma) + 1\). Finally, if \(i\) and \(j\) belong to the same cycle in \(\sigma\), then left-multiplication by \(\tau\) could either shorten this cycle or split it into two cycles, and in either case \(I(\tau\sigma) = I(\sigma) - 1\). So the \(I\) value of a product of \(n-2\) transpositions can be at most \(n-2\). The desired result follows.
Let \(x = (1\ 2\ldots n)\) and \(y = (1\ 2)\). Then \(xyx^{-1} = (2\ 3)\). Further conjugation by \(x\) yields \((3\ 4)\) and so on. Therefore the subgroup generated by \(x\) and \(y\) contains all transpositions of pairs of adjacent elements. The desired result follows from (a).

Exercise 7.5.2 The centralizer of \((1\ 2)\) consists of those elements of \(S_5\) that are invariant under conjugation by \((1\ 2)\). Since conjugation by \((1\ 2)\) simply exchanges 1 and 2 in the cycle representation of \(\sigma \in S_5\), it is obvious that we won't get back the same permutation if either 1 or 2 gets mapped to some element other than the other. All other \(\sigma\)—those that permute 3, 4, 5 arbitrarily but either fix 1 and 2 or else exchange them—do commute with \((1\ 2)\). So the centralizer has the structure \(S_2 \times S_3\).

Exercise 7.5.3 We can analyze all possible cycle decompositions:

There is a 7-cycle. Then the permutation has order 7.
There is a 6-cycle. Then the permutation has order 6.
There is a 5-cycle and the other two elements are exchanged. Then the order is 10
There is a 5-cycle and the other two elements are fixed. The order is 5.
There is a 4-cycle and a 3-cycle. The order is 12.
There is a 4-cycle and a 2-cycle, or a 4-cycle with the other three elements fixed. The order is 4.
There are two 3-cycles. The order is 3.
There is one 3-cycle and either one or two 2-cycles. The order is 6.
There is one 3-cycle and the other four elements are fixed. The order is 3.
There is at least one transposition and no cycles of higher order. The order is 2.
The identity has order 1.

So all orders of elements in \(S_7\) are 1, 2, 3, 4, 5, 6, 7, 10, and 12. We can compute the number of elements of each order as well, but it's tedious and not especially enlightening.

Exercise 7.5.4 Conjugation of \(\sigma\) by some element \(\tau \in S_7\) relabels the elements of the cycles in \(\sigma\). If \(\tau\) relabels 1 to 3, then it must relabel 3 to 5 and 5 to 1 in order to preserve the cycle \((1\ 5\ 3)\). Likewise if it relabels 1 to 5 then it must relabel 5 to 3 and 3 to 1. A similar analysis shows that the relabelling among 2, 4, and 6 can be the identity or a 3-cycle. There are therefore \(3 \times 3 = 9\) permutations of this kind that commute with \(\sigma\). But we can also relabel one of the elements 1, 5, 3 as one of the elements 2, 4, 6. It's clear that once we choose which of 2, 4, and 6 to relabel 1 to, and which of 1, 5, and 3 to relabel 2 to, the other relabellings are determined in order to end up with the same cycles. This gives another \(3 \times 3 = 9\) choices, for a total of 18 permutations that commute with \(\sigma\). The size of \(C(\sigma)\) is \(7! \div 18 = 280\).

Exercise 7.5.5 This follows from Exercise 2.6.4 and Proposition 7.5.1.

Exercise 7.5.6 Let \(G\) be a subgroup of \(S_4\) of order 4. Consider the following cases:

\(G\) is cyclic. That is, \(G\) is generated by some element of \(S_4\) of order 4, which can only be a 4-cycle. A 4-cycle and its inverse will generate the same subgroup, so there are \(3!/2 = 3\) such subgroups. None of these subgroups is normal, because the conjugation of \((a\ b\ c\ d)\) by \((a\ b)\) is \((b\ a\ c\ d)\), which isn't in the subgroup.
\(G\) contains a transposition, call it \((a\ b)\). Two subcases can be ruled out, namely where \(G\) also contains another transposition that isn't \((c\ d)\) (because then \(G\) would have to have order at least 6) and where \(G\) contains a double-transposition of the form \((a\ c)(b\ d)\) (multiplying this by \((a\ b)\) in both orders generates 2 new distinct elements of \(G\), so such \(G\) can't have order 4). This leaves only one possibility, which is that \(G = \{1, (a\ b), (c\ d), (a\ b)(c\ d)\}\). There are 3 such subgroups, and each is isomorphic to \(V_4\). None of these are normal, since conjugation of \((a\ b)\) by \((a\ c)\) would give \((b\ c)\), which isn't in the subgroup.
\(G\) consists only of the identity and double transpositions. There are in fact only three double transpositions, so \(G = \{1, (1\ 2)(3\ 4), (1\ 3) (2\ 4), (1\ 4)(2\ 3)\}\). Such \(G\) is isomorphic to \(V_4\). Also, conjugation on any of the three double transpositions must yield a double transposition, so this subgroup is normal, making it the only normal subgroup of \(S_4\) of order 4.

Exercise 7.5.7 Let \(G\) be a subgroup of \(S_n\) with index 2. Recall that such \(G\) must be normal. For \(n = 2\) the result is obvious. The following cases remain:

\(n = 3\). The class equation of \(S_3\) is \(6 = 1 + 2 + 3\) and obviously the only way to get 3 by adding up terms on the right including 1 is \(1 + 2\), so there is only one normal subgroup of order 3, which is \(A_3\).
\(n = 4\). The class equation of \(S_4\) is \(24 = 1 + 3 + 6 + 6 + 8\). We can apply the same reasoning as in case 1.
\(n > 4\). We will use the fact that \(A_n\) is simple. Consider \(G' = G \cap A_n\). Then \(G'\) is a normal subgroup of \(S_n\), and hence of \(A_n\) as well. So \(G'\) is either trivial or \(A_n\). If \(G'\) is \(A_n\), then \(G\) is also \(A_n\). But if \(G'\) is trivial then \(G\) consists of the identity and \(n!/2 - 1 \geq 3\) odd permutations. Let \(\sigma\) be one of these odd permutations. Then there's another odd permutation \(\tau\) in \(G\) that isn't \(\sigma^{-1}\). So \(\sigma\tau\) is an even permutation that is in \(G\) and isn't the identity, so a contradiction has been reached.

Exercise 7.5.8 The case \(n = 2\) is trivial. For the case \(n = 3\) we have the sign homomorphism from \(S_3\) to \(S_2\). For the case \(n = 4\), Example 2.5.13 gives a surjective homomorphism from \(S_4\) to \(S_3\). But for \(n \ge 5\) there can never be a surjective homomorphism from \(S_n\) to \(S_{n-1}\). This is because the kernel of such a homomorphism would have to be a normal subgroup of \(S_n\) of order \(n\), but in Exercise 7.4.2 we showed that the only proper normal subgroup of \(S_n\) is \(A_n\). So in fact we can make the stronger statement that for \(n \ge 5\), the image of \(S_n\) under a homomorphism must be isomorphic to \(S_n\) itself, the trivial group, or \(C_2\).

Exercise 7.5.9 Write \(q = (a\ b\ c)\). If \(p\) relabels \(a\) then it must relabel it as either \(b\) or \(c\), but this determines how \(b\) and \(c\) are relabelled too (in order to get the same cycle as the result). So \(p\) may relabel \(\{a, b, c\}\) in a 3-cycle, or not at all. The action of \(p\) on the remaining \(n - 3\) elements must be an even permutation in order for \(p\) to be even overall, but that part can be arbitrary. There are therefore \(3|A_{n-3}|\) possible values for \(p\). For \(n \ge 5\) this is just \(3(n-3)!/2\).

Exercise 7.5.10 These are just applications of Proposition 7.5.1. For \(S_4\) the following cases exist:

The 4-cycles. There are 6 of these. The centralizer of \((1\ 2\ 3\ 4)\) therefore has order 4. Therefore it's just the subgroup generated by \((1\ 2\ 3\ 4)\), which is therefore isomorphic to \(C_4\).
The 3-cycles. There are 8 of these. The centralizer of \((1\ 2\ 3)\) therefore has order 3, and similarly to Case 1 we conclude that it is just \(C_3\).
The double transpositions. There are 3 of these. The centralizer of \((1\ 2)(3\ 4)\) has order 8. It's easy to see that \(1, (1\ 2), (3\ 4), (1\ 2)(3\ 4)\) belong to the centralizer. If an element of the centralizer maps 1 to either 3 or 4 then it must map 2 to the other, and therefore must also map 3 to either 1 or 2 and 4 to the other. The other four elements of the centralizer are therefore \((1\ 3)(2\ 4), (1\ 4)(2\ 3), (1\ 3\ 2\ 4), (1\ 4\ 2\ 3)\). Thus, the centralizer is a group of order 8 that is not cyclic and has exactly two elements of order 4. We classified groups of order 8 in Exercise 7.3.4, and the only possibility that fits the criteria is \(D_4\).
The single transpositions. There are 6 of these. The centralizer of \((1\ 2)\) has order 4 and by inspection it's just \(\{1, (1\ 2), (3\ 4), (1\ 2)(3\ 4)\}\) which is isomorphic to \(V_4\).
The identity, which belongs to its own conjugacy class. The centralizer is all of \(S_4\).

This gives the class equation \(24 = 1 + 3 + 6 + 6 + 8\) as expected.

For \(S_5\) the following cases exist:

The 5-cycles. There are \(4! = 24\) of these since there are 4 choices of where to send 1, then 3 choices of where to send \(\sigma(1)\), and so on. The centralizer therefore has order 5. So the centralizer is just the subgroup generated by the 5-cycle (it is isomorphic to \(C_5\)).
The 4-cycles. There are \(5 \times 3! = 30\) of these. Again, the centralizer therefore has the same order as the cycle itself, so it must be isomorphic to \(C_4\).
The products of a 3-cycle and a transposition, like \((1\ 2\ 3)(4\ 5)\). There are \(\binom{5}{3} \times 2 = 20\) of these, so the centralizer has order 6. But the order of this permutation itself is also 6, so the centralizer is just the subgroup generated by this permutation, which is evidently isomorphic to \(C_3 \times C_2\).
The 3-cycles. There are again 20 of these, and it's not hard to see that the centralizer of \((1\ 2\ 3)\) is just \(\langle (1\ 2\ 3) \rangle \times \langle (4\ 5) \rangle\), because any relabelling of 1, 2, and 3 must be in a 3-cycle so that we end up with the same 3-cycle result. That is, the centralizer is again isomorphic to \(C_3 \times C_2\).
The double transpositions, of which there are 15. A representative is \((1\ 2)(3\ 4)\). It's clear that any relabelling that gives back \((1\ 2) (3\ 4)\) must fix 5, so this case reduces to Case 3 for \(S_4\). That is, the centralizer is isomorphic to \(D_4\).
The transpositions. There are 10 of these. A representative is \((1\ 2)\). An element of the centralizer, if it relabels 1, must relabel it to 2, and vice versa, otherwise the resulting transposition will be different. On the other hand, the relabelling of 3, 4, and 5 can be arbitrary. So in this case the centralizer is isomorphic to \(C_2 \times S_3\).
The identity, again.

This gives the class equation \(120 = 1 + 10 + 15 + 20 + 20 + 24 + 30\), which is what was promised.

Exercise 7.5.11

Suppose not all elements of \(C\) form a single conjugacy class in \(A_n\). Choose \(a, b \in C\) that are not conjugate in \(A_n\). Thus \(b = \sigma a \sigma^{-1}\) for some odd permutation \(\sigma\). Now let \(c \in C\). If \(c = \tau b \tau^{-1}\) for some even permutation \(\tau\), then \(b\) and \(c\) are conjugate in \(A_n\). Otherwise, \(c = (\tau\sigma) a (\tau\sigma)^{-1}\) and \(\tau\sigma\) is even, so \(a\) and \(c\) are conjugate in \(A_n\). This establishes that all elements of \(C\) are conjugate to either \(a\) or \(b\). Denote these two conjugacy classes in \(A_n\) by \(C_a\) and \(C_b\). The map \(\varphi : C_a \to C_b\) given by conjugation by \(\sigma\) is one-to-one and has an inverse, namely conjugation by \(\sigma^{-1}\), so it is a bijection, and \(|C_a| = |C_b|\).

Again, let \(a \in C\). By the orbit-stabilizer theorem, the conjugacy class \(a\) belongs to in \(A_n\) will be half the size of \(C\) iff the centralizer of \(a\) in \(A_n\) is the same size as the centralizer of \(a\) in \(S_n\), that is, if the centralizer of \(a\) in \(S_n\) is already a subgroup of \(A_n\). Otherwise—precisely when there exists an odd permutation that \(a\) commutes with—the centralizer of \(a\) in \(A_n\) will consist of only the even elements of the centralizer of \(a\) in \(S_n\), and thus be half the size, and \(C\) will be a single conjugacy class in \(A_n\).
The conjugacy classes of even permutations in \(S_4\) are that of the identity, the eight 3-cycles, and the three double transpositions. Obviously the identity is also a conjugacy class of \(A_4\), and the three double transpositions must form a single conjugacy class since their number is odd. The eight 3-cycles can't form a single conjugacy class in \(A_4\) because 8 doesn't divide 12. So the class equation of \(A_4\) is \(12 = 1 + 3 + 4 + 4\).

The conjugacy classses of even permutations in \(S_5\) are that of the identity, the 24 5-cycles, the 20 3-cycles, and the 15 double transpositions. Again, the double transpositions must form a single conjugacy class in \(A_5\) because they are odd in number. The 20 3-cycles are all conjugate to each other in \(A_5\) by Lemma 7.5.5(b). In Exercise 7.5.10 we found that the centralizer of a 5-cycle is simply the cyclic group of order 5 generated by that 5-cycle. All 5 elements of the centralizer are therefore even, so this is also the centralizer of that 5-cycle in \(A_5\). This implies that the conjugacy class of 5-cycles in \(S_5\) is split into two conjugacy classes in \(A_5\). In conclusion, the class equation of \(A_5\) is \(60 = 1 + 12 + 12 + 15 + 20\), which matches what was determined in the text geometrically for \(I\).
Although the text says permutations of odd order, I assume that Artin really meant odd permutations. The proof of part (a) applies just as well to each conjugacy class of odd permutations of \(S_n\), provided that we replace statements like \(a\) and \(b\) are conjugate in \(A_n\) with \(a\) and \(b\) belong to the same \(A_n\)-orbit. Therefore we can at first conclude that each conjugacy class of odd permutations of \(S_n\) is either an \(A_n\)-orbit or the union of two \(A_n\)-orbits of equal size. Applying the test to distinguish the two possibilities, we find that since an odd permutation always commutes with at least one odd permutation (namely itself) it follows that its conjugacy class in \(C_n\) always forms a single \(A_n\)-orbit.

Exercise 7.5.12 In \(S_6\) there are \(5! = 120\) 6-cycles, \(\binom{6}{5} \times 4! = 144\) 5-cycles, \(\binom{6}{4} \times 3! = 90\) 4-cycles, another 90 permutations consisting of a 4-cycle and the transposition of the remaining two elements, \(\binom{6}{3} \times 2^2 \times \frac{1}{2} = 40\) double 3-cycles (where the factor of one-half accounts for the fact that choosing 3 elements for the first 3-cycle is equivalent to choosing the other 3 elements), \(\binom{6}{3} \times 2 \times 3 = 120\) pairs of a 3-cycle and a 2-cycle, \(\binom{6}{3} \times 2 = 40\) single 3-cycles, \(\binom{6}{2} \binom{4}{2} \times \frac{1}{6} = 15\) triple transpositions, \(\binom{6}{2} \binom{4}{2} \times \frac{1}{2} = 45\) double transpositions, \(\binom{6}{2} = 15\) single transpositions, and the identity. So the class equation of \(S_6\) is \(720 = 1 + 15 + 15 + 40 + 40 + 45 + 90 + 90 + 120 + 120 + 144\).

The conjugacy classes of even permutations in \(S_6\) are the 144 5-cycles, the 90 4-cycle and 2-cycle pairs, the 40 double 3-cycles, the 40 3-cycles, the 45 double transpositions, and the identity. The 45 double transpositions must form a single conjugacy class in \(A_6\) because there are an odd number of them. The 144 5-cycles must be split into two conjugacy classes because 144 doesn't divide \(|A_5| = 360\). The 40 3-cycles are conjugate to each other in \(A_6\) by Lemma 7.5.5(b). We argue that any two permutations containing a 4-cycle and a 2-cycle, say \(a, b\) are conjugate to each other. For if \(b = \sigma a \sigma^{-1}\) with \(\sigma\) odd, then we also have \(b = (\tau\sigma) a (\tau\sigma)^{-1}\) where \(\tau\) transposes the two elements involved in the 2-cycle in \(b\), and now \(\tau\sigma\) is even. Lastly, for a double 3-cycle such as \((1\ 2\ 3)(4\ 5\ 6)\), the centralizer contains odd elements such as \((1\ 4)(2\ 5)(3\ 6)\), so the centralizer in \(A_n\) has only half the size, so the conjugacy class has the same size. This establishes that the class equation of \(A_6\) is \(360 = 1 + 40 + 40 + 45 + 72 + 72 + 90\).