Permutation Groups and Symmetric Groups: Full Guide

A permutation of a set X is a bijection from X to itself — a complete reshuffling. All permutations of X, composed one after another, form the symmetric group S_X (S_n when X = {1, …, n}). A permutation group is any subgroup of a symmetric group.

Symmetric groups are universal: Cayley's theorem says every group is isomorphic to a permutation group. They model real rearrangements — card shuffles, Rubik's cube twists — and their cycle structure controls parity and conjugacy, including the proof that the quintic has no general radical formula via A_5.

Key Concepts

• Cycle notation: (1 3 2) means 1 → 3 → 2 → 1. Disjoint cycles commute; every permutation factors uniquely into disjoint cycles.
• Size: |S_n| = n!. Order of a permutation: lcm of its disjoint cycle lengths.
• Transposition: a 2-cycle; every permutation is a product of transpositions.
• Sign: sgn(σ) = +1 for an even number of transpositions, −1 for odd. The sign is well defined.
• Alternating group A_n: the even permutations; |A_n| = n!/2 (n ≥ 2), normal in S_n.
• Composition order: read right to left: (στ)(x) = σ(τ(x)).

Formulas

• Group size: |S_n| = n!. (Counts only; no physical units.)
• Order of σ: lcm of its disjoint cycle lengths l_1, …, l_k.
• Sign: sgn(στ) = sgn(σ)·sgn(τ); an l-cycle has sign (−1)^{l−1}.
• Conjugacy: two permutations are conjugate in S_n iff they have the same cycle type.
• Limit: the order formula needs the disjoint cycle decomposition — simplify overlapping cycles first.

Worked Example

Work in S_3 (6 elements: e, (12), (13), (23), (123), (132)). Multiply στ = (12)(123), reading right to left: 1 →τ 2 →σ 1, so 1 ↦ 1; 2 →τ 3 →σ 3, so 2 ↦ 3; 3 →τ 1 →σ 2, so 3 ↦ 2. The result is (23). Order check: τ = (123) has one 3-cycle, so order 3 (τ^2 = (132), τ^3 = e). Sign check: sgn(τ) = (−1)^{3−1} = +1, sgn((12)) = −1, so sgn(στ) = −1 — and (23) is indeed a transposition.

Common Misconceptions

• "Permutation multiplication is commutative." Not for n ≥ 3: (12)(123) = (23) but (123)(12) = (13).
• "(12)(34) has order 4." Cycle lengths are 2 and 2, so the order is lcm(2, 2) = 2.
• "The sign depends on the decomposition." Every transposition decomposition of one permutation has the same parity — that theorem is what makes A_n well defined.

Real-World Applications

• Puzzles: the Rubik's cube group is a permutation group on its stickers; solvability questions are permutation questions.
• Cryptography: substitution ciphers are permutations; modern block ciphers use permutation networks.
• Sorting algorithms: every sort rearranges data by a permutation; counting inversions measures distance from sorted order.
• Galois theory: the Galois group of a polynomial is a permutation group on its roots; the simplicity of A_5 proves the quintic has no general radical formula.

Symmetric groups package every possible rearrangement into one algebraic object; cycle notation, order via lcm, and the sign homomorphism give you complete control over how permutations behave and combine.