= Cayley's theorem
{c}
{wiki}
= Cayley theorem
{c}
{synonym}
Every <group> $G$ is <isomorphic> to a <subgroup> of the <symmetric group> on its underlying <set>. The construction uses the <left regular action>: each <group element> $g$ becomes a <permutation> of all the <group elements>, given by
$$
L_g:G\longrightarrow G,\qquad L_g(x)=gx,\qquad \lambda:G\hookrightarrow\operatorname{Sym}(G),\quad g\longmapsto L_g.
$$
For a <finite group> of <group order> $n$, labeling these elements by $1,\ldots,n$ gives a <group embedding> into $S_n$. The same construction works for an <infinite group>, with the <symmetric group> of all <bijections> of its underlying <set>.<Group Theory (v4.01) by James S. Milne>[Theorem 1.22 and Corollary 1.23, printed page 16: left multiplication embeds a group into its symmetric group]{ref}
The beauty is that the multiplication rule itself supplies a concrete model. Whatever the <group elements> originally represent, each one rearranges the entire <group> by multiplication. A product becomes <function composition>, and no distinctions between <group elements> are lost. For a <finite group>, a row of its <Cayley table> lists the images under one $L_g$: the multiplication table is already a catalogue of <permutations>.
Throughout this construction, products of <permutations> act rightmost first:
$$
(\sigma\tau)(x)=(\sigma\circ\tau)(x)=\sigma(\tau(x)),\qquad L_gL_h=L_{gh}.
$$
Thus $L_gL_h$ first multiplies by $h$, then by $g$. This is a left <group action>, not a license to reverse the multiplication order in a <nonabelian group>. Ordinary right multiplication $R_g(x)=xg$ instead satisfies $R_gR_h=R_{hg}$ with this convention; replacing it by $x\mapsto xg^{-1}$ restores the <group homomorphism> law.<Group Actions by Keith Conrad>[Example 2.10, printed page 7: left multiplication and the reversed composition law for right multiplication]{ref}
For an explicit <cyclic group> example, take $C_4=\mathbb Z/4\mathbb Z$ under addition, using <modular arithmetic>. Its <left regular action> consists of $L_k(x)=k+x\pmod4$. In <permutation cycles> on the labels $0,1,2,3$,
$$
L_0=\operatorname{id},\qquad L_1=(0\ 1\ 2\ 3),\qquad L_2=(0\ 2)(1\ 3),\qquad L_3=(0\ 3\ 2\ 1).
$$
The <function composition> $L_1L_1=L_2$ sends $0$ to $2$, $1$ to $3$, $2$ to $0$, and $3$ to $1$: squaring the four-point <permutation cycle> produces two <disjoint permutation cycles>. Also $L_1L_3=L_0$. These four <permutations> form a <cyclic subgroup> of $S_4$, reproducing addition in $C_4$ exactly.
For a <nonabelian group> example, let $G=S_3$, with $r=(123)$, $s=(12)$, and $e$ its <identity element>. The six <group elements> are $e,r,r^2,s,rs,r^2s$, where $r^3=s^2=e$ and $sr=r^2s$. Now the labels being permuted are themselves <permutations> of three points. Computing the <left regular action> gives <permutations> of these six labels:
$$
L_r=(e\ r\ r^2)(s\ rs\ r^2s),\qquad L_s=(e\ s)(r\ r^2s)(r^2\ rs).
$$
For example, $L_s(r)=sr=r^2s$; putting $rs$ here would accidentally switch to right multiplication. Noncommutativity survives in the model:
$$
(L_rL_s)(e)=rs=(13),\qquad (L_sL_r)(e)=sr=(23).
$$
These different outputs prove that $L_rL_s\ne L_sL_r$. The <group generators> $r,s$ become <group generators> $L_r,L_s$ of a six-element <subgroup> of $S_6$.
\Image[/cayley-left-translation-cycles.png]
{title=<Left regular action> as <permutation cycles> for $C_4$ and $S_3$}
{id=cayley-left-translation-cycles}
{description=Each arrow sends a label $x$ to $gx$, or to $k+x$ in the additive <cyclic group>. The top panels show the translations by $1$ and $2$ in $C_4$; the bottom panels show multiplication by $r$ and $s$ in the <symmetric group> $S_3$. Each panel depicts one <permutation>, decomposed into <disjoint permutation cycles>.}
Why does a <group action> here produce a <group embedding>? Any <group action> on a <set> $X$ gives a <group homomorphism> $\rho:G\to\operatorname{Sym}(X)$; it is a <group embedding> precisely when it is a <faithful group action>. The <group kernel> consists of the <group elements> fixing every point of $X$. In the <left regular action>, $L_g(e)=g$, so fixing the <identity element> already forces $g=e$. In fact every <stabilizer subgroup> is trivial, since $gx=x$ forces $g=e$; this stronger property makes the <left regular action> a <regular group action>.<Group Actions by Keith Conrad>[Theorem 1.2, printed pages 1-2: injectivity by evaluating at the identity; Theorem 1.7 and following paragraph, printed page 3: actions as homomorphisms and their kernels]{ref}
Compare two <group actions> of the same <cyclic group> $C_4$. Its <left regular action> on four labels distinguishes all four <group elements>. On $X=\{0,1\}$, the rule $k\cdot x=k+x\pmod2$ defines a <transitive group action>, but $0$ and $2$ both fix both points, while $1$ and $3$ both exchange them. Its <group kernel> is $\{0,2\}$, so it is not a <faithful group action>. Its image is a two-element <subgroup> of $S_2$, <isomorphic> to the <quotient group> $C_4/\{0,2\}$ rather than to $C_4$.
\Image[/cayley-faithful-and-nonfaithful-actions.png]
{title=A <faithful group action> preserves all four translations; a two-point <group action> merges them}
{id=cayley-faithful-and-nonfaithful-actions}
{description=Both panels start with the same <cyclic group> $C_4$. The arrows show the <group action> of its <group generator> $1$, and the tables show all four resulting <permutations>. On four points the <group kernel> is $\{0\}$; on two points it is $\{0,2\}$. Reachability of every point does not imply a <faithful group action>.}
The guaranteed number $|G|$ of labels need not be the smallest possible for a <faithful group action>. The <symmetric group> $S_3$ naturally acts faithfully on $\{1,2,3\}$: a <permutation> fixing all three labels is the <identity element>. Its <left regular action> uses six labels instead. Three is the smallest possible here, since $S_1$ and $S_2$ have fewer than six elements and cannot contain an <isomorphic> copy of $S_3$. Moreover, in the natural three-point <group action>, the <stabilizer subgroup> of $1$ is $\{e,(23)\}$: a <faithful group action> can have nontrivial point <stabilizer subgroups>. Cayley's construction supplies a universal model, while a smaller model can reveal particular <symmetries>.
The proof is short. Each $L_g$ is a <bijection> with inverse $L_{g^{-1}}$. <Associativity> gives
$$
L_g(L_h(x))=g(hx)=(gh)x=L_{gh}(x),
$$
so $\lambda$ is a <group homomorphism>. If $L_g=L_h$, evaluating both at the <identity element> gives $g=L_g(e)=L_h(e)=h$. Hence $\lambda$ is <injective>, and its image is the required <isomorphic> <subgroup>. No finiteness assumption entered the argument.
The historical connection is unusually close to the notation. The opening paragraph of <Arthur Cayley>'s 1854 paper already treats <permutations> as one example of operations on a collection of quantities and explicitly performs the rightmost operation first in a product. It also allows noncommutativity while insisting on <associativity>. The modern <left regular action> shows how that viewpoint reaches every abstract <group>, by choosing the <group> itself as the <set> to be acted on.<Abstract awakenings in algebra: Early group theory in the works of Lagrange, Cauchy, and Cayley by Janet Heine Barnett>[Abstract awakenings in algebra: Early group theory in the works of Lagrange, Cauchy, and Cayley by Janet Heine Barnett, Section 3.1, printed page 50: reproduced opening paragraph of Arthur Cayley's On the theory of groups, as depending on the symbolic equation theta^n = 1; reference 5, printed page 91: original publication in 1854]{ref}
Back to article page
