Group Theory

7 The Symmetric Group

Definition 7.1. The symmetric group \(S_n\) is automorphism group of a set of \(n\) elements.

The set of \(n\) elements will be \(\{1,\dots ,n\}\). Given an element of \(S_n\), its action on \(\{1, \dots ,n\}\) breaks it up into orbits. The action on each orbit is called a cycle. It can be represented by choosing a base point and using Theorem 1.2 writing the cosets corresponding to the subgroup of the group generated by element. For example, the cycle \((123)\) comes from the element that sends \(1\) to \(2\), \(2\) to \(3\), and \(3\) to \(1\). It is a \(3\)-cycle since it has \(3\) elements, and has two other equivalent forms, \((231)\), and \((312)\). Any action breaks up into orbits, so we can represent an element of \(S_n\) in its cycle form. For example, \((132)(45)\) is an element of \(S_5\). We say that the cycle type of an element is the size of the orbits in increasing order. For example in \(S_6\), \((132)(45)\) has cycle type \([1,2,3]\), and \((123456)\) has cycle type \([6]\).

If \(a,b\) are elements of \(S_n\), then we can think about how \(b^{-1}ab\) acts on the set. Namely \(b^{-1}ab(b^{-1}x) = b^{-1}a(x)\), so \(b^{-1}ab\) sends \(b^{-1}x\) to \(b^{-1}ax\), so we see that the cycle type has stayed the same, only the cycles have changed by \(b\). Conversely by varying \(b\), we see that the cycle types are exactly the conjugacy classes.

Let’s try to understand the structure of \(S_n\). \(S_1\) is trivial, and \(S_2\) is \(C_2\). \(S_3\) has a subgroup of index \(2\), hence is the semidirect product \(C_3\rtimes C_2\), where the action is given by the inversion map. This is the same as \(D_3\). \(S_4\) has a normal subgroup \(C_2\times C_2\) generated by \([2,2]\) cycles. The short exact sequence (non canonically) splits by looking at a copy of \(S_3\) as the stabilizer of \(4\). Then we have \(S_4 = (C_2\times C_2)\rtimes S_3\). The automorphism group of \(C_2\times C_2\) is \(\GL _2(\FF _2)\), so we need to find out how \((123)\) and \((12)\) act. If the first copy of \(C_2\) is given by \((12)(34)\) and the second copy by \((23)(14)\), then conjugation by \((12)\) sends \((23)(14) = (0,1)\) to \((13)(24) = (1,1)\) and \((1,0)\) to itself. Thus it is given by \(\begin {pmatrix}1 & 1\\ 0 & 1 \end {pmatrix}\). \((123)\) conjugates \((12)(34)\) to \((23)(14)\) and \((23)(14)\) to \((31)(24)\), so is given by \(\begin {pmatrix}0 & 1\\ 1 & 1 \end {pmatrix}\).

Understanding \(S_n\) for \(n\geq 5\) is either harder or simpler, depending on your perspective. In particular they only have one nontrivial normal subgroup. To define this, consider the homomorphism \(\sgn \) from \(S_n\) to \(\ZZ ^\times = \pm 1\) defined by \(\sgn (\sigma ) = \prod _{i< j} \frac {\sigma (i)-\sigma (j)}{i-j}\). This is clearly a homomorphism, and it isn’t hard to see that any \(2\)-cycle is sent to \(-1\). Thus it is surjective for \(n \geq 2\), and the kernel is called the alternating group on \(n\) elements and is denoted \(A_n\). We can look at an element’s cycle type to see whether or not it is in \(A_n\), since we only need to see how many \(2\)-cycles it takes to obtain that element.

For \(n = 1,2\), \(A_n\) is trivial. \(A_3 = C_3\), and \(A_4 = (C_2 \times C_2) \rtimes C_3\) from our similar description of \(S_4\).

Now let’s study \(A_n\) for \(n \geq 5\). I claim that they are simple, meaning that they have no nontrivial proper normal subgroups (they are simple objects in the category of groups). So far the only other simple groups we have seen are \(C_p\) for prime \(p\).

Lemma 7.2. \(3\)-cycles generate \(A_n\) for any \(n\).

Proof. WLOG, let \((123\dots k)\) be a cycle in an element of \(A_n\). if \(k\) is odd, we can write \((1(k-1)k)\dots (145)(123)= (123\dots k)\). If \(k\) is even, then we must have \(n \geq k+2\), so that we can use \(((k+1)1(k+2))(1k(k+1))\dots (145)(123)\), and by induction on \(n\), we are done. □

Theorem 7.3. \(A_n\) is simple for \(n \neq 4\).

Proof. We have already verified this for \(n \leq 4\). To show that \(A_n\) is simple for \(n \geq 5\), it suffices to produce a \(3\)-cycle in any nontrivial normal subgroup by the previous lemma, since we can conjugate by something in \(A_n\) to get any other (this uses \(n \geq 5)\).

Suppose we have a nontrivial element. By taking a large enough power, we can suppose that it contains only prime cycles in its cycle decomposition for a particular prime \(p\). If they are \(2\)-cycles, either we have \((12)(34)\) (up to relabeling) or \((12)(34)(56)\dots \). In the first case, observe \((12)(45)\) is conjugate, so that (this uses \(n \geq 5\))

\[(12)(34)(12)(45) = (345)\]

In the second, observe that

\[(12)(34)(56)(14)(36)(52)=(135)(264)\]

so we can assume \(p=3\).

For \(p\) odd, if we have at least \(2\) \(p\)-cycles \((12\dots p)((p+1)\dots (2p))\), note that \((1(2p-1)(2p-2)\dots (p+1))(p\dots 2(2p))\) is conjugate and that their product is \((1(2p))(p(2p-1))\), so taking an appropriate power, we reduce to the case of a \([2,2]\) cycle, which we already saw produces a \(3\)-cycle. □

In particular, for \(n\geq 5\), \(A_n\) is the commutator subgroup of \(S_n\), and further commutators will again yield \(A_n\).