Skip to content
Tutorials Center
My learning

Topics

Lesson 14 of 37 · Cyclic and Permutation Groups

Cayley's Theorem

See why every finite group sits inside a symmetric group: build the left regular representation of a group in Python and check it respects the operation.

Abstract groups are defined by axioms, but Cayley's theorem says nothing is lost by thinking of them as groups of permutations. Every group, however abstractly defined, is a subgroup of a symmetric group. This justifies the study of permutation groups and gives us a way to compute with any finite group.

Statement

Theorem (Cayley). Every group G is isomorphic to a subgroup of the symmetric group on the set G. In particular, a finite group of order n embeds in S_n.

The idea: left multiplication

For each g ∈ G define a function λ_g : G → G by λ_g(x) = gx.

  1. λ_g is a bijection: it has inverse λ_{g⁻¹}. So λ_g is a permutation of G.
  2. λ_g ∘ λ_h = λ_{gh}: indeed λ_g(λ_h(x)) = g(hx) = (gh)x, by associativity.
  3. g ↦ λ_g is injective: if λ_g = λ_h then g = λ_g(e) = λ_h(e) = h.

So the map g ↦ λ_g sends products to compositions, and it is one-to-one. Its image is a subgroup of the permutations of G that is a copy of G. (The word "isomorphic" is defined precisely in chapter 5; for now it means "the same group under a relabeling".)

Building it in code

We label the elements of ℤ₄ as positions 0..3 and turn each element into a permutation.

Python The left regular representation

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each λ_g is a permutation of four positions, and the four permutations multiply exactly as the group elements add. For ℤ₄ they are the powers of the 4-cycle (0 1 2 3), so ℤ₄ sits inside S₄ as the subgroup generated by a 4-cycle.

A non-abelian example: S₃ inside S₆

Do the same for the group S₃ (of order 6): every element becomes a permutation of the 6 elements of S₃ itself.

Python Embed S₃ in S₆

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

So S₃, order 6, appears as a subgroup of S₆, which has 720 elements. Cayley's embedding is rarely the smallest one (S₃ already sits in S₃), but it works for every group.

Cayley's theorem is the reason we call this subject "group theory" even though many groups arise abstractly. It also gives a practical representation for computer algebra systems. However, in practice we look for smaller permutation representations: the Cayley embedding of a group of order n uses S_n, which is huge.

Consequences

  • Every finite group is "just" a group of permutations: studying S_n and its subgroups covers all finite groups.
  • A permutation representation also leads to the idea of a group acting on a set, developed in lesson 18.
  • The same proof works with right multiplication, or with conjugation (which gives a homomorphism, not necessarily injective).
flowchart LR
    G["Group G<br/>(abstract)"] -->|"g ↦ λ_g"| P["Subgroup of Sym(G)<br/>(permutations)"]
    P -->|"is a copy of"| G

Left multiplication turns each group element into a permutation of the group itself.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. In Cayley's proof, what is λ_g(x)?

    λ_g is left multiplication by g.
  2. 2. Why is g ↦ λ_g injective?

    Evaluating at the identity recovers g from λ_g.
  3. 3. In which symmetric group does Cayley's theorem place a group of order 8?

    A group of order n embeds in S_n by permuting its own n elements.
  4. 4. Which property of the group operation makes λ_g ∘ λ_h = λ_{gh}?

    g(hx) = (gh)x is associativity.

Summary

  • Cayley's theorem: every group is isomorphic to a group of permutations of its own elements.
  • The map g ↦ λ_g (left multiplication) is injective and turns products into compositions.
  • A group of order n embeds in S_n, often not minimally.
  • It motivates groups acting on sets and permutation representations.

Next: Cosets