S. D. V. Stephens

notes / Studies in Algebra and Group Theory / chapter 1: Sets and Groups / From my book

B3.4 The Symmetric Group

The symmetric group is arguably the most important finite group. By Cayley’s theorem, every finite group is isomorphic to a subgroup of some . But is also interesting in its own right: its structure illustrates conjugacy classes, normal subgroups, and simplicity. Symmetric groups connect to linear algebra through the sign homomorphism and determinants, and to Galois theory through their role in permuting the roots of polynomials.

Recall from Chapter 2 that has order , and the cycle notation: , for distinct , is the -cycle sending and fixing everything else; a 2-cycle is a transposition; and two cycles are disjoint if they move no common element. As always, permutations compose right to left: means first, then .

3.4.1 Cycle Decomposition

Disjoint cycles and commute. Indeed, if moves , then also moves (otherwise would force ), so fixes both and , and . The same holds with the roles of and exchanged, and if neither moves , then .

Theorem 3.4.1 (Cycle Decomposition Theorem). Every permutation is a product of disjoint cycles of length at least 2, uniquely up to the order of the factors. These cycles are the restrictions of to the orbits of on that have more than one element.

Proof. Existence. Consider the action of on . Fix . The elements of the finite set cannot all be distinct, and the first repetition must be a return to : if with , then because is injective. Let be least with . Then are distinct, and writing any as with shows . So the orbit of is , and on it acts as the -cycle .

The orbits partition (Proposition 3.2.5). Let be the cycles obtained in this way from the orbits with at least two elements; they are disjoint. We check that . If lies in the orbit of , then , and both and are fixed by the other cycles, so . If , every fixes .

Uniqueness. Suppose with the disjoint cycles of length at least 2. If , no moves : otherwise , since the other cycles fix both and . If , then some moves , and the other cycles fix every point that moves; hence for all . So the set of points moved by is the -orbit of , and agrees with there; that is, is the cycle of that orbit constructed above. Hence . ∎

In practice: write down the successive images of 1 under until we return to 1; then do the same starting from the smallest number not yet used, and so on.

Example 3.4.2. For the permutation (with written below ), the successive images of 1 are , and then , while is fixed. So .

Definition 3.4.3 (Cycle type). The cycle type of is the list of lengths of the cycles in its disjoint cycle decomposition, including a 1-cycle for each fixed point; it is a partition of . We write it as , where is the number of -cycles, omitting the terms with .

Example 3.4.4. In , the permutation has cycle type : one fixed point (6), one 2-cycle, and one 3-cycle. The identity has cycle type , and a 6-cycle has type .

3.4.2 Conjugacy in

The conjugacy classes of a group (Definition 3.2.12) are fundamental to its structure and to its representation theory. In they have an elegant description.

Lemma 3.4.5 (Conjugating a cycle). For and a cycle ,

Proof. Write . For , we get (indices mod ), the next entry of the cycle on the right. If , then , so fixes and . ∎

Theorem 3.4.6 (Conjugacy classes of ). Two permutations in are conjugate if and only if they have the same cycle type.

Proof. Conjugate same type. Let and write as a product of disjoint cycles. Then , and by Lemma 3.4.5 each is a cycle of the same length as . These cycles are disjoint because is a bijection, so this is the cycle decomposition of , and has the same cycle type as .

Same type conjugate. Write and as products of disjoint cycles, including 1-cycles for fixed points, listing the cycles in order of decreasing length: Each of appears exactly once in each line, so , , and so on, defines a permutation . By Lemma 3.4.5, . ∎

Corollary 3.4.7 (Number of conjugacy classes of ). The number of conjugacy classes of equals , the number of partitions of (ways of writing as a sum of positive integers, up to order). For example, , , , , , .

Proof. By the theorem, conjugacy classes correspond to cycle types, and every partition is the cycle type of some permutation, for instance . ∎

Example 3.4.8 (Conjugacy classes of and ). In the classes are , the three transpositions, and the two 3-cycles, of sizes . In :

cycle typedescriptionsize of class
identity1
transpositions 6
, two disjoint transpositions3
3-cycles8
4-cycles6

and .

Note. That conjugacy classes of correspond to partitions of is one reason the representation theory of is so rich: the irreducible representations of are also indexed by partitions of , and the character table can be computed combinatorially. This is a whole subject in itself; Chapter 14 works out the case .

3.4.3 Generators of

Proposition 3.4.9 (Generators of ).

  1. Every -cycle is a product of transpositions:
  2. is generated by the transpositions.
  3. For , is generated by the adjacent transpositions , .

Proof. (a) The rightmost factor acts first. Apply the right side to : sends , and the remaining transpositions fix ; so . Apply it to with : the transpositions fix ; then sends ; then sends ; and the remaining transpositions fix . So . Apply it to : every factor except the last, , fixes , and that one sends . Elements outside are fixed by both sides.

(b) By the Cycle Decomposition Theorem every permutation is a product of cycles, and by (a) every cycle is a product of transpositions. (The identity is the empty product.)

(c) By (b) it suffices to write each transposition , , as a product of adjacent transpositions. We induct on . If , then . If , Lemma 3.4.5 gives since sends and fixes , and . By induction is a product of adjacent transpositions, hence so is . ∎

Note. Part (c) is the mathematics behind the bubble sort algorithm. Multiplying on the right by swaps the entries in positions and of the list , since . Bubble sort puts the list in order by such swaps, , which writes . Chapter 12 shows that the least number of adjacent transpositions needed is the number of inversions of , defined next.

3.4.4 The Sign Homomorphism and the Alternating Group

Definition 3.4.10 (Inversions and sign). An inversion of is a pair with and . Let be the number of inversions. The sign of is A permutation is even if and odd if .

Example 3.4.11. In , the 3-cycle sends to . Its inversions are and , so it is even. For a transposition with , the inversions are itself and the pairs and with ; there are of them, an odd number, so every transposition is odd.

Lemma 3.4.12 (A product formula for the sign). For ,

Proof. As runs over the two-element subsets of , so does , because is a bijection. Hence , and the product in the lemma has absolute value 1. A factor is negative exactly when is an inversion, so the sign of the product is . ∎

Theorem 3.4.13 (The sign is a homomorphism). The map is a homomorphism. For it is surjective.

Proof. Let . By Lemma 3.4.12, The second product is . In the first, the factor is unchanged when and are exchanged, so it depends only on the set . As runs over all two-element subsets, so does ; hence the first product equals . So . For , the transposition has sign , so is surjective. ∎

Corollary 3.4.14 (Parity and transpositions).

  1. If is a product of transpositions, then . Hence the number of transpositions in any such expression of is even if is even and odd if is odd.
  2. A -cycle has sign .
  3. If is the number of cycles of , counting 1-cycles, then .

Proof. (a) Each transposition has sign , and is a homomorphism. (b) A -cycle is a product of transpositions (Proposition 3.4.9). (c) If the cycles of have lengths , with , then by (b) . ∎

So the parity of the number of transpositions needed to write is well defined, even though the number itself is not: . This is the nontrivial point; everything else about the sign is bookkeeping.

Definition 3.4.15 (Alternating group). The alternating group is , the group of even permutations.

Proposition 3.4.16 (Properties of ). Let .

  1. , , , and .
  2. For , is generated by the 3-cycles. In fact .

Proof. (a) is the kernel of the surjective homomorphism , so it is normal, and the First Isomorphism Theorem gives . Hence and by Lagrange’s theorem.

(b) A 3-cycle is even, since . Conversely, let . By Corollary 3.4.14, any expression of as a product of transpositions has an even number of factors, so is a product of pairs . Each pair is a product of 3-cycles: it is if ; if the pair shares exactly one element, we may write it as ; and if , then So is generated by the 3-cycles.

Now let . It suffices to show that every 3-cycle lies in . Let be distinct elements of . Each identity below can be checked directly, or with Lemma 3.4.5:

  • 3-cycles moving both 1 and 2 are and ;
  • 3-cycles moving 1 but not 2 are of the form ;
  • 3-cycles moving 2 but not 1 are of the form ;
  • 3-cycles moving neither are of the form , and by the previous case.

The last identity is Lemma 3.4.5, since sends and fixes and . ∎

For , is simple; the proof is in Chapter 11 (Theorem 11.4.9). For this fails: has a normal subgroup of order 4 (Question 3.4 below). The group is simple, but abelian.

Note. The simplicity of for is a historically important result, tied to the non-existence of a formula for the roots of a general quintic. The quadratic formula contains a , and the ambiguity of the sign is a permuting the two roots; Cardano’s formula for cubics has nested square and cube roots, whose ambiguities combine to an permuting the three roots. A formula for the roots of a degree 5 equation would need a built-in symmetry, but the symmetries of any expression built from -th roots are assembled from cyclic groups , in the sense that they admit a chain of subgroups, each normal in the next, with abelian quotients. Since is simple and non-abelian, admits no such chain. Galois theory makes this precise.

Note. The sign is intimately related to the determinant (Section 5.4): for an matrix , , and is the determinant of the permutation matrix of . The sign is what makes the determinant alternating: swapping two rows, or two columns, negates it.

Example 3.4.17 (The converse of Lagrange’s theorem fails). The group has order but no subgroup of order 6. Suppose had order 6, so , and let be a 3-cycle. If , the two cosets of are and , and is one of them. It is not , since would give ; so and . But then , because , a contradiction. Hence contains all eight 3-cycles of (choose the fixed point in 4 ways, then one of two cyclic orders of the other three), which is impossible since .

Example 3.4.18 (The commutator subgroup of ). For , , and hence . Since is abelian, , so . For , and there is nothing more to show. For , every 3-cycle is a commutator, and the 3-cycles generate (Proposition 3.4.16). So .

Question 3.4.19.

  1. Compute the cycle type and sign of in . (First simplify!)
  2. How many elements of have cycle type ?
  3. Let . Prove that is a subgroup isomorphic to , that , and that .
  4. Show that the normal subgroups of are , , , and .
Show solution

(a) Multiply the cycles right to left: first , then , then , then . Trace each element: Thus , of cycle type , and : is even. (Alternatively, the signs of the four factors are , whose product is .)

(b) Choose the fixed point (7 ways), then the four elements of the 4-cycle from the remaining six ( ways), then arrange them in a 4-cycle ( ways, since a -cycle on a given set of elements can be written in exactly one way with a chosen element first, followed by an ordering of the other ). The remaining two elements form the 2-cycle. Total: .

(c) By direct computation, the product of any two distinct non-identity elements of is the third, for example , and each non-identity element has order 2. So is a subgroup in which every element satisfies , and , , , is an isomorphism , as the two multiplication tables agree. The non-identity elements of form the conjugacy class of cycle type (Theorem 3.4.6), so is a union of conjugacy classes and hence normal (Proposition 3.2.13).

For the quotient, let act on the set of the three ways to split into two pairs, by applying to every entry. This gives a homomorphism . The transposition fixes and swaps and , and sends . So contains elements of orders 2 and 3, its order is divisible by 6, and is surjective. Each element of fixes all three ; for instance sends and , so it fixes . Thus . By the First Isomorphism Theorem , so and .

(d) A normal subgroup is a union of conjugacy classes containing , and its order divides 24. The classes of have sizes (Example 3.4.8). The sums of with some of that divide 24 are , , , and , each obtained in only one way. The union of size 4 is , which is a normal subgroup by (c). The union of size 12 consists of the identity, the products of two disjoint transpositions, and the 3-cycles; these are exactly the even permutations (Corollary 3.4.14), so this union is . Hence the normal subgroups of are , , , and . Since , is also a normal subgroup of .