Cayley's Theorem

Permutation groups are not just one example among many: every group is one, after an isomorphism. This is Cayley's theorem, and it is the reason permutations are a universal model for symmetry.

Why it works

Cayley's theorem. Every group $G$ is isomorphic to a group of permutations of the set $G$. In particular a group of order $n$ is isomorphic to a subgroup of $S_{n}$.
Proof. For $g \in G$ define $\lambda_{g}: G \to G$ by $\lambda_{g}(x) = gx$.
(1) $\lambda_{g}$ is a permutation: it has the inverse $\lambda_{g^{-1}}$, since $g^{-1}(gx) = x$.
(2) $g \mapsto \lambda_{g}$ is a homomorphism: $\lambda_{gh}(x) = ghx = \lambda_{g}(\lambda_{h}(x))$, so $\lambda_{gh} = \lambda_{g} \circ \lambda_{h}$.
(3) It is one-to-one: if $\lambda_{g}$ is the identity, then $g = ge = \lambda_{g}(e) = e$, so the kernel is trivial.
So $G \cong \{\lambda_{g} : g \in G\}$, a subgroup of the permutations of $G$. $\square$

You have already seen these permutations: $\lambda_{g}$ is row $g$ of the Cayley table, read as a rearrangement of the column headings. That every row is a rearrangement was the cancellation law.

Row $3$ of the table of $U(10)$ reads $3, 9, 1, 7$ under the headings $1, 3, 7, 9$: the permutation $\lambda_{3}$ sends $1 \to 3 \to 9 \to 7 \to 1$.

Worked example: A Cayley permutation in $U(10)$

Write $\lambda_{3}$ for $U(10) = \{1, 3, 7, 9\}$ in cycle notation, using the elements as labels.

$\lambda_{3}(1) = 3$, $\lambda_{3}(3) = 9$, $\lambda_{3}(9) = 27 \equiv 7$, $\lambda_{3}(7) = 21 \equiv 1$.
One cycle: $(1\;3\;9\;7)$, of length $4 = |3|$.

Answer: $(1\;3\;9\;7)$.

Worked example: The shape of every $\lambda_{g}$

In a group of order $12$, $g$ has order $3$. Describe the cycles of $\lambda_{g}$.

Following $x \to gx \to g^{2}x \to g^{3}x = x$ closes up after exactly $|g| = 3$ steps, and never sooner (if $g^{k}x = x$ then $g^{k} = e$).
So every cycle has length $3$, and there are $12/3 = 4$ of them (they are the cosets $\langle g \rangle x$).

Answer: Four 3-cycles.

Worked example: Relabeling $\mathbb{Z}_{6}$

Write $\lambda_{2}$ for $\mathbb{Z}_{6}$ as a permutation in $S_{6}$, labeling the element $k$ as $k + 1$.

$\lambda_{2}(x) = x + 2$: $0 \to 2 \to 4 \to 0$ and $1 \to 3 \to 5 \to 1$.
With labels $k + 1$: $(1\;3\;5)(2\;4\;6)$.

Answer: $(1\;3\;5)(2\;4\;6)$.

Cayley's theorem is about existence, not economy: it puts a group of order $6$ inside $S_{6}$, which has $720$ elements, although $S_{3}$ is already a group of order $6$. Its value is conceptual. Any statement proved for all subgroups of symmetric groups holds for all finite groups, and any finite group can be explored by computer as a set of permutations.

Common mistake

Using $x \mapsto xg$ instead of $x \mapsto gx$. Right multiplication also permutes $G$, but $\rho_{g}(x) = xg$ gives $\rho_{gh}(x) = xgh = \rho_{h}(\rho_{g}(x))$: the order reverses, so $g \mapsto \rho_{g}$ is not a homomorphism in a nonabelian group (it works with $x \mapsto xg^{-1}$). In an abelian group the two agree.

Key idea

Cayley: $g \mapsto \lambda_{g}$, with $\lambda_{g}(x) = gx$, is an isomorphism from $G$ onto a group of permutations of $G$. Each $\lambda_{g}$ is a row of the Cayley table, made of $|G|/|g|$ cycles of length $|g|$.

Sources and further reading

Thomas W. Judson, Abstract Algebra: Theory and Applications (open textbook), chapter 9, Isomorphisms (section 9.1, Cayley's Theorem)

MIT OpenCourseWare 18.703 Modern Algebra (Spring 2013), lecture on Cayley's theorem

John A. Beachy and William D. Blair, Abstract Algebra, online study guide (Northern Illinois University), section 3.6, Permutation Groups (Cayley's theorem)

Cayley's Theorem

Practice

Builds on

Leads to

Sources and further reading