After studying homomorphisms, kernels, isomorphisms, and cyclic examples, we reach one of the most important representation results in elementary group theory. The focus keyword Cayley theorem and permutation groups states that every group is structurally the same as a group of permutations. This means an abstract group can always be realized through bijections of a set. The construction is not mysterious: each group element acts on the group by left multiplication. Students often think permutation groups are special examples, but Cayley's theorem shows that they are universal models for all groups. :::definition[Permutation] Let $A$ be a non-empty set. A permutation of $A$ is a bijective function from $A$ onto $A$. ::: :::definition[Symmetric Group] Let $A$ be a non-empty set. The set of all permutations of $A$, under composition of functions, is called the symmetric group on $A$ and is denoted by $S_A$. If $A$ has $n$ elements, then $S_A$ is commonly denoted by $S_n$, and $$\begin{equation*} |S_n|=n!. \end{equation*}$$ ::: :::definition[Permutation Group] A permutation group is a subgroup of a symmetric group. Thus a permutation group is a group whose elements are bijections of some set and whose operation is composition. ::: Let $G$ be a group and fix $a\in G$. Define $L_a:G\to G$ by $L_a(x)=ax$. This map is a bijection: multiplying by $a^{-1}$ reverses it. Cayley's theorem uses these left multiplication maps to build a faithful permutation model of $G$. The group element $a$ is replaced by the permutation $L_a$, and multiplication in $G$ becomes composition of these permutations. :::theorem[Cayley Theorem] Every group is isomorphic to a permutation group. ::: :::proof Given that $G$ is a group. To prove that $G$ is isomorphic to a permutation group. For each $a\in G$, define $L_a:G\to G$ by $$\begin{equation*} L_a(x)=ax. \end{equation*}$$ First, $L_a$ is one-to-one. If $L_a(x)=L_a(y)$, then $ax=ay$. Multiplying by $a^{-1}$ on the left gives $x=y$. Next, $L_a$ is onto. Let $y\in G$. Put $x=a^{-1}y$. Then $$\begin{equation*} L_a(x)=a(a^{-1}y)=y. \end{equation*}$$ Thus $L_a$ is a permutation of $G$. Let $$\begin{equation*} L(G)=\{L_a\mid a\in G\}. \end{equation*}$$ Define $\Phi:G\to L(G)$ by $\Phi(a)=L_a$. Let $a,b\in G$. For every $x\in G$, $$\begin{align*} L_{ab}(x)&=(ab)x,\\ (L_a\circ L_b)(x)&=L_a(bx)\\ &=a(bx)\\ &=(ab)x. \end{align*}$$ Therefore $L_{ab}=L_a\circ L_b$, so $$\begin{equation*} \Phi(ab)=\Phi(a)\circ\Phi(b). \end{equation*}$$ Thus $\Phi$ is a homomorphism. If $\Phi(a)=\Phi(b)$, then $L_a=L_b$. Applying both functions to $e$ gives $$\begin{equation*} a=L_a(e)=L_b(e)=b. \end{equation*}$$ Thus $\Phi$ is one-to-one. By definition of $L(G)$, the map $\Phi$ is onto. Hence $\Phi$ is an isomorphism from $G$ onto the permutation group $L(G)$. $\square$ ::: :::corollary If $G$ is a finite group of order $n$, then $G$ is isomorphic to a subgroup of $S_n$. ::: :::proof Given that $G$ is a finite group of order $n$. To prove that $G$ is isomorphic to a subgroup of $S_n$. By Cayley's theorem, $G\cong L(G)$, where $L(G)$ is a group of permutations of the set $G$. Since $G$ has $n$ elements, the symmetric group on the set $G$ is isomorphic to $S_n$. Therefore $L(G)$ may be viewed as a subgroup of $S_n$. Hence $G$ is isomorphic to a subgroup of $S_n$. $\square$ ::: :::example[Cyclic Group of Order Four as Permutations] Let $G=\{1,i,-1,-i\}$ under multiplication. For each $a\in G$, define $L_a(x)=ax$. Then $$\begin{align*} L_1&=(1)(i)(-1)(-i),\\ L_i&=(1\ i\ -1\ -i),\\ L_{-1}&=(1\ -1)(i\ -i),\\ L_{-i}&=(1\ -i\ -1\ i). \end{align*}$$ The set $\{L_1,L_i,L_{-1},L_{-i}\}$ is a permutation group, and the map $a\mapsto L_a$ is an isomorphism from $G$ onto this permutation group. ::: :::solved-problem Let $G$ be a finite group of order $3$. Use Cayley's theorem to explain why $G$ is isomorphic to a subgroup of $S_3$. ::: :::solution Let $G$ be a finite group of order $3$. To prove that $G$ is isomorphic to a subgroup of $S_3$. For each $a\in G$, define $L_a:G\to G$ by $L_a(x)=ax$. Each $L_a$ is a permutation of the three-element set $G$. Therefore $L_a\in S_G$, where $S_G$ is the symmetric group on $G$. Let $L(G)=\{L_a\mid a\in G\}$. By Cayley's theorem, the map $a\mapsto L_a$ is an isomorphism from $G$ onto $L(G)$. Since $S_G$ is isomorphic to $S_3$, the group $L(G)$ corresponds to a subgroup of $S_3$. Hence $G$ is isomorphic to a subgroup of $S_3$. $\square$ ::: :::remark Cayley's theorem does not say that every group is equal to a subgroup of $S_n$. It says every finite group of order $n$ is isomorphic to such a subgroup. This distinction matters: the original elements of $G$ may be numbers, matrices, symmetries, or abstract symbols, while the Cayley representation uses permutations. ::: :::tip In the proof of Cayley theorem and permutation groups, the left multiplication map must be shown to be bijective before it can be called a permutation. The inverse of $L_a$ is $L_{a^{-1}}$, because $L_{a^{-1}}(L_a(x))=x$ and $L_a(L_{a^{-1}}(x))=x$. ::: :::exercise 1. For a group $G$, prove directly that $L_a\circ L_b=L_{ab}$ for all $a,b\in G$. 2. If $|G|=4$, what symmetric group contains a subgroup isomorphic to $G$ by Cayley's theorem? 3. Why is the map $a\mapsto L_a$ one-to-one? ::: :::answer 1. For $x\in G$, $(L_a\circ L_b)(x)=L_a(bx)=a(bx)=(ab)x=L_{ab}(x)$. 2. Cayley's theorem gives a subgroup of $S_4$ isomorphic to $G$. 3. If $L_a=L_b$, then applying both maps to $e$ gives $a=L_a(e)=L_b(e)=b$. ::: :::faq[Frequently Asked Questions] Q: Does Cayley's theorem apply to infinite groups? A: Yes. Every group is isomorphic to a group of permutations of its underlying set. Q: Why use left multiplication instead of right multiplication? A: Left multiplication gives $L_{ab}=L_a\circ L_b$ with the usual composition order used here. Q: What is the importance of the theorem? A: It shows that permutation groups are universal models for group structure. ::: :::call-to-action[Review Homomorphisms of Groups] subtitle: Revisit kernels, isomorphisms, cyclic homomorphisms, and Cayley representations as one connected theory. button: Return to Homomorphisms | /abstract-algebra/homomorphisms-and-isomorphisms-of-groups/homomorphisms-of-groups/homomorphism-of-groups button-ghost: Study Group Actions | /abstract-algebra/homomorphisms-and-isomorphisms-of-groups/group-actions/group-actions-and-g-sets :::