Cayley's theorem

Every finite group is a permutation group. This is one of the earliest theorems in group theory and the reason algorithmic group theory can reduce arbitrary finite groups to the structured world of permutation representations.

Statement

Cayley (1854). Every group G is isomorphic to a subgroup of Sym(G), the group of all bijections G → G. In particular, every finite group of order n embeds in Sₙ.

Proof

The left regular action sends g ∈ G to the bijection

λg : G → G,   λg(h) = gh.

Each λg is a bijection (inverse is λg⁻¹). The map ρ : G → Sym(G), g ↦ λg, is a homomorphism:

ρ(gh)(x) = (gh)x = g(hx) = ρ(g)(ρ(h)(x)).

It is injective because λg = id ⟹ gh = h ⟹ g = e. Hence ρ is an embedding of G as a subgroup of Sym(G). ∎

Degree |G| is rarely necessary

Cayley's embedding uses degree |G|, but often a much smaller degree suffices — S₇ already contains a group of order 168. The least degree of any faithful action is the minimal faithful permutation degree μ(G); requiring the action to stay in one orbit gives the minimal transitive degree μt(G). The regular action above is the statement μ(G) ≤ μt(G) ≤ |G|.

When Cayley is optimal. μ(G) = |G| for exactly three families (Johnson, 1971): the cyclic p-groups Cpk, the generalized quaternion groups Q₂ⁿ, and the Klein four-group C₂ × C₂. In the first two, a unique subgroup of order p lies inside every nontrivial subgroup, forcing the regular action; the Klein four-group is a small coincidence (2·2 = 2²).

Everywhere else the regular action wastes points: D₄ needs only the 4 vertices of a square, Sₙ and Aₙ only their natural n points, and PSL(2,𝔽7) the 7 points of the Fano plane.

See also

• Minimal faithful degree — how far below |G| the degree can drop.
• Permutation group — the target of Cayley's embedding.
• Group action — the machinery behind the proof.
• Schreier–Sims algorithm — what makes permutation groups algorithmically tractable.
• Wikipedia: Cayley's theorem