The symmetric group is arguably the most important finite group. By Cayley’s theorem, every finite group embeds in some . But is also interesting in its own right: its structure illuminates concepts like conjugacy classes, normal subgroups, and simplicity. Moreover, symmetric groups connect to linear algebra through the sign homomorphism and determinants, and to Galois theory through their role in permuting roots of polynomials.
3.4.1 Cycle structure and decomposition
Definition 3.4.1 (Symmetric group). The symmetric group is the group of all bijections under composition. It has order .
Definition 3.4.2 (Cycle notation). A -cycle (or cycle of length ) is a permutation that acts by and fixes all other elements. A 2-cycle is called a transposition. Two cycles are disjoint if they have no elements in common; disjoint cycles commute.
Theorem 3.4.1 (Cycle Decomposition Theorem). Every permutation can be written as a product of disjoint cycles, uniquely up to the order of the factors. The decomposition is obtained by writing out the orbits of acting on .
Proof (Existence and uniqueness of cycle decomposition). Existence: Consider the action of on . The orbits partition . For each orbit where (indices mod ), define the cycle . Fixed points give 1-cycles (usually omitted). Since orbits are disjoint, these cycles are disjoint.
To verify equals the product of these cycles: for any , if is in the orbit giving cycle , then and all other cycles fix , so the product sends .
Uniqueness: Suppose are two decompositions into disjoint cycles. For any , exactly one moves (the others fix it), and that must generate the orbit of under . Similarly for the ’s. Thus and the containing describe the same orbit, hence are the same cycle (up to cyclic rotation of the notation). ∎
Definition 3.4.3 (Cycle type). The cycle type of is the partition of given by the lengths of the cycles in its disjoint cycle decomposition (including 1-cycles for fixed points). We write it as where is the number of -cycles.
Example 3.4.1. In , the permutation has cycle type since there’s one fixed point (6), one 2-cycle, and one 3-cycle. The identity has cycle type . A single 6-cycle has type .
3.4.2 Conjugacy in
Conjugacy classes are fundamental to representation theory. In , they have an elegant characterization.
Theorem 3.4.2 (Conjugacy in ). Two permutations in are conjugate if and only if they have the same cycle type.
Proof of conjugacy classification. Key computation: Let and be a cycle. Then Proof: For any , if , then . If , then , so the cycle fixes , and conjugation gives .
Same type conjugate: Let and have the same cycle type. Define by , etc. Then by the key computation, .
Conjugate same type: If , write as a product of disjoint cycles. By the key computation, is the product of the conjugated cycles, which have the same lengths. Disjointness is preserved since is a bijection. ∎
Proposition 3.4.1 (Number of conjugacy classes in ). The number of conjugacy classes in equals , the number of partitions of . For example, .
Note. This fact that conjugacy classes correspond to partitions is one reason why the representation theory of is so whimsical. 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.
3.4.3 The sign homomorphism and alternating group
Every permutation can be written as a product of transpositions. The number of transpositions is not unique, but its parity is!
Proposition 3.4.2 (Transposition generation). is generated by transpositions. More precisely, every -cycle can be written as a product of transpositions:
Proof (Verification of transposition decomposition). Apply the right side to : sends , then subsequent transpositions fix . So . ✓
Apply to for : transpositions fix . Then sends . Then sends . Subsequent transpositions fix . So . ✓
Apply to : all transpositions except fix , which sends . ✓ ∎
Theorem 3.4.3 (Well-definedness of parity). If are two expressions of as products of transpositions, then .
Proof of parity well-definedness. Consider the polynomial . For , define . Each factor equals for some , so .
For a transposition with : the factor becomes . For , the factor is unchanged. For , the factors and are swapped, contributing no sign change. Similarly for other cases. Careful counting shows (the key is that one factor picks up a sign, and swaps come in pairs).
Thus if , then . If also , then , so . ∎
Definition 3.4.4 (Sign of a permutation). The sign (or signature) of is where is any expression as a product of transpositions. Equivalently, where is the number of cycles (including 1-cycles). A permutation is even if and odd if .
Theorem 3.4.4 (Sign is a homomorphism). The map is a surjective group homomorphism.
Proof that sign is a homomorphism. If and , then , a product of transpositions. Thus . Surjectivity: any transposition has sign . ∎
Definition 3.4.5 (Alternating group). The alternating group is the group of even permutations.
Proposition 3.4.3 (Properties of ). We have:
- with index , so .
- .
- is generated by 3-cycles. In fact, .
- For , is simple (has no proper nontrivial normal subgroups).
Proof of properties (1)-(3). (1)-(2) follow from the First Isomorphism Theorem: .
(3) Every even permutation is a product of an even number of transpositions. We can pair them: . If , then (verify!). If , then . Thus is generated by 3-cycles. For the specific generating set: (if all differ from 1,2; similar manipulations handle other cases). ∎
Note. The simplicity of for is a historically revolutionary result (it regards the non-existence of the quintic formula). It implies that has no quotients except and itself, which means is “irreducible” in a sense. Via Galois theory, this simplicity is precisely why the general quintic polynomial has no solution in radicals: the Galois group of the “generic” degree- polynomial is , and solvability by radicals requires a composition series with abelian quotients. For , blocks this because it’s simple and non-abelian.
Note. The sign homomorphism is intimately related to the determinant: for a matrix , we have . The sign ensures the determinant is alternating in the rows (swapping rows negates the determinant). This is no coincidence: the determinant is the unique alternating multilinear function on vectors with , and “alternating” is encoded by the sign.
Question 4.
- Compute the cycle type and sign of in . (First simplify!)
- How many elements of have cycle type ?
- Prove that the only normal subgroups of are .
- Let . Prove and . What is ?
Show solution
(1) First, multiply the cycles right-to-left. Trace each element: Write . Reading right-to-left: start with , then , then , then .
Trace 1: . So .
Trace 2: . So .
Trace 3: . So (fixed).
Trace 4: . So .
Trace 5: . So .
Thus , cycle type . Sign: two 2-cycles = two transpositions, so (even).
(2) Cycle type means one fixed point, one 2-cycle, one 4-cycle. Choose the fixed point: 7 ways. Choose 4 elements for the 4-cycle from the remaining 6: ways. Arrange them in a 4-cycle: ways. The remaining 2 elements form the 2-cycle: 1 way. Total: .
(3) has order 6. By Lagrange, subgroups have order 1, 2, 3, or 6. Normal subgroups must be unions of conjugacy classes. Conjugacy classes in : (size 1), (size 3), (size 2).
A normal subgroup of order 2 would need size-1 and size-1 classes, but has size 1 and we’d need another element with a size-1 class—none exist. A normal subgroup of order 3 must be . ✓
(4) Check is a subgroup: , etc.—closure holds (verify all products give elements of ). Each non-identity element has order 2. So (Klein four-group).
Normality: consists of plus all products of two disjoint transpositions. These form a conjugacy class in (cycle type ), so is a union of conjugacy classes, hence normal.
has order . The quotient is non-abelian (since is non-abelian and is not all of ), so . Explicitly: acts on the three partitions , and is the kernel.