Cayley’s Theorem

At a Glance

• Frequency: 1 sub-part across 1 of 14 years (2017)
• Priority tier: T4
• Marks (count): 10 (1)
• Average solve time: ~12 min
• Difficulty mix: medium 1
• Section: A | Dominant type: proof

Why This Chapter Matters

Cayley’s theorem is one of the great unifying results of group theory: it says that abstract groups are, in a precise sense, nothing more than groups of symmetries. UPSC 2017 tested it as a Section A proof question worth 10 marks — the entire proof fits cleanly in under a page if you know the left regular representation. Beyond its intrinsic importance, the construction used in the proof (left multiplication as a permutation) reappears in the proofs of Sylow’s theorems.

Minimum Theory

Statement

Theorem (Cayley, 1854). Every group $G$ is isomorphic to a subgroup of $S_{|G|}$ (the symmetric group on $|G|$ elements). In particular, every group of order $n$ embeds in $S_n$.

The Left Regular Representation

For each $g \in G$, define $\lambda_g : G \to G$ by $\lambda_g(x) = gx$ (left multiplication by $g$).

Claim 1. $\lambda_g$ is a bijection.

Proof. $\lambda_g$ is injective: $\lambda_g(x) = \lambda_g(y) \Rightarrow gx = gy \Rightarrow x = y$. It is surjective: for any $y \in G$, $\lambda_g(g^{-1}y) = g(g^{-1}y) = y$. Hence $\lambda_g \in \mathrm{Sym}(G)$. $\checkmark$

So we may define a map $\phi : G \to \mathrm{Sym}(G)$ by $\phi(g) = \lambda_g$.

Claim 2. $\phi$ is a group homomorphism.

Proof. For $g, h \in G$ and any $x \in G$: $\phi(gh)(x) = \lambda_{gh}(x) = (gh)x = g(hx) = \lambda_g(\lambda_h(x)) = (\lambda_g \circ \lambda_h)(x) = (\phi(g) \circ \phi(h))(x).$ Since $x$ is arbitrary, $\phi(gh) = \phi(g)\phi(h)$. $\checkmark$

Claim 3. $\phi$ is injective.

Proof. Suppose $\phi(g) = \phi(h)$, i.e., $\lambda_g = \lambda_h$. Evaluating at $e \in G$: $ge = \lambda_g(e) = \lambda_h(e) = he \implies g = h.$ So $\ker(\phi) = \{e\}$, which means $\phi$ is injective. $\checkmark$

Conclusion. Since $\phi : G \to \mathrm{Sym}(G)$ is an injective homomorphism, by the first isomorphism theorem $G \cong \phi(G) \le \mathrm{Sym}(G).$ When $|G| = n$, we have $|\mathrm{Sym}(G)| = n! = |S_n|$ and $\mathrm{Sym}(G) \cong S_n$, so $G$ embeds in $S_n$. $\blacksquare$

Concrete Example: $\mathbb{Z}_3 \hookrightarrow S_3$

Label elements of $\mathbb{Z}_3 = \{0, 1, 2\}$ as $1, 2, 3$.

• $\lambda_0$: $0\mapsto 0, 1\mapsto 1, 2\mapsto 2$ → identity permutation $e$.
• $\lambda_1$: $0\mapsto 1, 1\mapsto 2, 2\mapsto 0$ → cycle $(1\;2\;3)$ (using labels $1,2,3$ for $0,1,2$).
• $\lambda_2$: $0\mapsto 2, 1\mapsto 0, 2\mapsto 1$ → cycle $(1\;3\;2)$.

So $\mathbb{Z}_3 \cong \{e, (1\;2\;3), (1\;3\;2)\} \le S_3$. $\checkmark$

Question Archetypes

state-and-prove (1 question; 2017)

Recognition Cues

• “State and prove Cayley’s theorem”
• “Every group of order $n$ is isomorphic to a subgroup of $S_n$”
• 10 marks: full proof required, not just a sketch

Solution Template

1. State the theorem precisely.
2. Define $\lambda_g(x) = gx$ and $\phi(g) = \lambda_g$.
3. Prove $\lambda_g$ is a bijection (so $\phi$ maps into $\mathrm{Sym}(G)$).
4. Prove $\phi$ is a homomorphism.
5. Prove $\phi$ is injective (by evaluating at $e$).
6. Conclude $G \cong \phi(G) \le \mathrm{Sym}(G) \cong S_n$.

Worked Example

2017 Paper 2, 2017-P2-Q1a (10 marks)

State and prove Cayley’s theorem.

Solution.

Theorem. Every group $G$ is isomorphic to a subgroup of the symmetric group $\mathrm{Sym}(G)$. In particular, if $|G| = n$, then $G$ is isomorphic to a subgroup of $S_n$.

Proof.

For each $g \in G$, define the map $\lambda_g : G \to G$ by $\lambda_g(x) = gx \quad \text{for all } x \in G.$

Step 1: $\lambda_g \in \mathrm{Sym}(G)$. For injectivity, $\lambda_g(x) = \lambda_g(y) \Rightarrow gx = gy \Rightarrow x = y$ (left cancellation). For surjectivity, given $y \in G$ take $x = g^{-1}y$; then $\lambda_g(x) = g(g^{-1}y) = y$. Hence $\lambda_g$ is a bijection on $G$.

Step 2: Define $\phi : G \to \mathrm{Sym}(G)$ by $\phi(g) = \lambda_g$.

Step 3: $\phi$ is a homomorphism. For any $g, h \in G$ and $x \in G$: $\phi(gh)(x) = (gh)x = g(hx) = \lambda_g(\lambda_h(x)) = (\phi(g) \circ \phi(h))(x).$ Since this holds for all $x$, $\phi(gh) = \phi(g)\phi(h)$.

Step 4: $\phi$ is injective. If $\phi(g) = \phi(h)$ then $\lambda_g = \lambda_h$, so in particular $\lambda_g(e) = \lambda_h(e)$, giving $g = h$. Hence $\ker(\phi) = \{e\}$.

Conclusion. By the first isomorphism theorem, $G/\ker(\phi) \cong \phi(G)$, i.e., $G \cong \phi(G)$. Since $\phi(G) \subseteq \mathrm{Sym}(G)$ and is a homomorphic image of a group it is a subgroup, so $\phi(G) \le \mathrm{Sym}(G)$.

When $G$ is finite of order $n$, $\mathrm{Sym}(G) \cong S_n$, completing the proof.

$\boxed{G \cong \phi(G) \le \mathrm{Sym}(G) \cong S_n}\;\blacksquare$

Common Traps

• Confusing left and right multiplication: the right regular representation $\rho_g(x) = xg$ is also injective but one must check $\rho_{gh} = \rho_h \circ \rho_g$ (note the reversal) — it is safer to use left multiplication.
• Forgetting to prove that $\lambda_g$ is a bijection before claiming $\phi(g) \in \mathrm{Sym}(G)$.
• Stating ”$G$ embeds in $S_{|G|}$” without the isomorphism — the theorem asserts an isomorphism onto a subgroup, not just an injection of sets.
• Skipping the surjectivity half of the bijection argument.

Marks-Aware Writing

10 marks (Section A):

• Theorem statement with correct quantifiers (1–2 marks).
• $\lambda_g$ is a bijection: injectivity + surjectivity (2–3 marks).
• $\phi$ is a homomorphism (2–3 marks).
• $\phi$ is injective (2 marks).
• Conclusion (1 mark).

Every step must be shown; a “sketch” will lose marks at this level.

Practice Set

Only one historical question on this atom (shown above).