6.4: Cayley's Theorem

One might wonder how “common” permutation groups are in math. They are, it turns out, ubiquitous in abstract algebra: in fact, every group can be thought of as a group of permutations! We will prove this, but we first need the following lemma. (We will not use the maps \(\rho_a\) or \(c_a\text{,}\) defined below, in our theorem, but define them here for potential future use.)

Lemma \(\PageIndex{1}\)

Let \(G\) be a group and \(a\in G\text{.}\) Then the following functions are permutations on \(G\text{,}\) and hence are elements of \(S_G\text{:}\)

• \(\lambda_a\,:\,G\to G\) defined by \(\lambda_a(x)=ax\text{;}\)
• \(\rho_a\,:\,G\to G\) defined by \(\rho_a(x)=xa\text{;}\)
• \(c_a\,:\,G\to G\) defined by \(c_a(x)=axa^{-1}\text{.}\)

Proof

To show that \(λ_a\) is a bijection, first assume \(x_1,x_2∈G\) with \(λ_a(x_1)=λ_a(x_2)\). Then \(ax_1=ax_2\); so, by left cancellation, \(x_1=x_2\). Thus, \(λ_a\) is one-to-one. Further, each \(y∈G\) equals \(λ_a(a^{−1}y)\) for \(a^{−1}y∈G\), so \(λ_a\) is onto. Thus, \(λ_a\) is a bijection from \(G\) to \(G\): that is, it's a permutation on \(G\). The proofs that \(ρ_a\) and \(c_a\) are bijections are similar.

Definition: Left Multiplication, Right Multiplication, and Conjugation

We say that \(\lambda_a\text{,}\) \(\rho_a\text{,}\) and \(c_a\) perform on \(G\text{,}\) respectively, left multiplication by \(a\), right multiplication by \(a\), and conjugation by \(a\). (Note: Sometimes when people talk about conjugation by \(a\) they instead are referring to the permutation of \(G\) that sends each \(x\) to \(a^{-1}xa\text{.}\))

To show that \(\lambda_a\) is a bijection, first assume \(x_1,x_2 \in G\) with \(\lambda_a(x_1)=\lambda_a(x_2)\text{.}\) Then \(ax_1=ax_2\text{;}\) so, by left cancellation, \(x_1=x_2\text{.}\) Thus, \(\lambda_a\) is one-to-one. Further, each \(y\in G\) equals \(\lambda_a(a^{-1}y)\) for \(a^{-1}y\in G\text{,}\) so \(\lambda_a\) is onto. Thus, \(\lambda_a\) is a bijection from \(G\) to \(G\text{:}\) that is, it's a permutation on \(G\text{.}\) The proofs that \(\rho_a\) and \(c_a\) are bijections are similar.

Now we are ready for our theorem:

Theorem \(\PageIndex{1}\): Cayley's Theorem

Let \(G\) be a group. Then \(G\) is isomorphic to a subgroup of \(S_G\text{.}\) Thus, every group can be thought of as a group of permutations.

Proof

For each \(a∈G\), let \(λ_a\) be defined, as above, by \(λ_a(x)=ax\) for each \(x∈G\); recall that each \(λ_a\) is in \(S_G\). Now define \(\phi:G→S_G\) by \(\phi(a)=λ_a\), for each \(a∈G\).

We claim that \(\phi\) is both a homomorphism and one-to-one. Indeed, let \(a,b∈G\). Now, \(\phi(a)\phi(b)\) and \(\phi(ab)\) are both functions with domain \(G\), so we need to show \((\phi(a)\phi(b))(x)=(\phi(ab))(x)\) for each \(x∈G\). Well, let \(x∈G\). Then

\(\begin{array}& (\phi(a)\phi(b))(x)&=(λ_aλ_b)(x)\\ &=λ_a(λ_b(x)) &(\text{since the operation on \(S_G\) is composition})\\ & =λ_a(bx)&\\ &=a(bx)&\\ &=(ab)x&\\ &=λ_{ab}(x)&\\ &=(\phi(ab))(x).& \end{array}\)

So \(\phi\) is a homomorphism. Further, if \(a,b∈G\) with \(\phi(a)=\phi(b)\), then \(λ_a=λ_b\). In particular, \(λ_a(e)=λ_b(e)\). But \(λ_a(e)=ae=a\) and \(λ_b(e)=be=b\), so \(a=b\). Thus, \(\phi\) is one-to-one.

Since by definition \(\phi(G)\) we have that \(\phi\) maps \(G\) onto \(\phi(G)\), we conclude that \(\phi\) provides an isomorphism from \(G\) to the subgroup \(\phi(G)\) of \(S_G\).

Remark

In general, \(\phi(G) \neq S_G\text{,}\) so we cannot conclude that \(G\) is isomorphic to \(S_G\) itself; rather, we may only conclude that it is is isomorphic to some subgroup of \(S_G\text{.}\)

Remark

While we chose to use the maps \(\lambda_a\) to prove the above theorem, we could just as well have used the maps \(\rho_a\) or \(c_a\text{,}\) instead.