Definition 8.1. Groups of Permutation.
We say that \(H\) is a group of permutations if there exists a set \(X\) such that \(H\) is isomorphic to a subgroup of \(S_X\text{,}\) the Symmetric Group on \(X\text{.}\)
Chapter 8 Groups of Permutations
Section 8.1 Definitions
Section 8.2 Cayley’s Theorem
Theorem 8.2. Cayley’s Theorem.
Every group is isomorphic to a group of permutations.
Proof.
Let \(G\) be a group. We prove that \(G\) is isomorphic to a subgroup of \(S_G\text{.}\) For each \(g \in G\text{,}\) define the function
\begin{align*}
\Phi(g) \colon G \amp\to G\\
x \amp \mapsto gx
\end{align*}
This is a bijection because for all \(x \in G\text{,}\)
\begin{equation*}
\Phi(g) \circ \Phi\left(g^{-1}\right)(x) = \Phi(g)\left(g^{-1}x\right) = gg^{-1}x = x
\end{equation*}
and
\begin{equation*}
\Phi\left(g^{-1}\right) \circ \Phi(g)(x) = \Phi\left(g^{-1}\right)\left(gx\right) = g^{-1}gx = x\text{.}
\end{equation*}
This defines a morphism of sets
\begin{align*}
\Phi \colon G \amp\to S_G\\
g \amp\mapsto \Phi(g)
\end{align*}
that is surjective onto its image.
To see that \(\Phi\) is injective, suppose there exist \(g_1,g_2 \in G\) such that \(\Phi(g_1) = \Phi(g_2)\text{.}\) By definition, for every \(x \in G\text{,}\) \(\Phi(g_1)(x) = \Phi(g_2)(x)\text{.}\) Taking \(x = 1\) yields
\begin{equation*}
g_1 = \Phi(g_1)(1) = \Phi(g_2)(1) = g_2\text{.}
\end{equation*}
Hence \(\Phi\) is injective.
Finally, let \(g_1, g_2 \in G\) be given. Since multiplication is associative on \(G\text{,}\) we observe that for all \(x \in G\text{,}\)
\begin{align*}
\Phi(g_1 g_2)(x) \amp= \left(g_1g_2\right)x\\
\amp= g_1\left(g_2x\right)\\
\amp= \Phi(g_1)\left(g_2x\right)\\
\amp= \Phi(g_1)\left(\Phi(g_2)(x)\right)\\
\amp= \left(\Phi(g_1) \circ \Phi(g_2)\right)(x)\text{.}
\end{align*}
Hence \(\Phi(g_1 g_2) = \Phi(g_1) \circ \Phi(g_2)\text{.}\) Therefore \(\Phi\) is an isomorphism between \(G\) and its image,
\begin{equation*}
\Phi(G) = \left\{\Phi(g) \;\middle\vert\; g \in G\right\} \subseteq S_G\text{.}
\end{equation*}
Definition 8.3. Left Regular Representation.
The morphism of groups \(\Phi \colon G \to S_G\) is called the left regular representation of \(G\)
Remark 8.4.
The choice to use multiplication on the left in Cayley’s Theorem is artificial. We could just as well have attempted to define multiplication on the left. For a fixed element \(g \in G\text{,}\) this would define a function \(x \mapsto xg\text{.}\) Unfortunately, this doesn’t actually define a homomorphism (see the exercises). To remedy this problem, we define \(\Psi(g)(x) = xg^{-1}\text{.}\) This gives rise to an anlogous theory and the isomorphism is known as the right regular representation.
Definition 8.5. Right Regular Representation.
The morphism of groups
\begin{align*}
\Psi \colon G \amp\to S_G\\
g \amp\mapsto \Psi(g)
\end{align*}
is called the right regular representation of \(G\)
Exercises 8.3 Exercises for Undergrads & Grads
1.
Prove that for every \(g \in G\text{,}\) the function
\begin{align*}
\Omega(g) \colon G \amp\to G\\
g \amp \mapsto xg
\end{align*}
is a bijection and the function
\begin{align*}
\Omega \colon G \amp\mapsto S_G\\
g \amp \mapsto \Omega(g)
\end{align*}
is an injection, but that \(\Omega\) is not a homomorphism.
Solution.
This is a bijection because for all \(x \in G\text{,}\)
\begin{equation*}
\Omega(g) \circ \Omega\left(g^{-1}\right)(x) = \Omega(g)\left(xg^{-1}\right) = xg^{-1}g = x
\end{equation*}
and
\begin{equation*}
\Omega\left(g^{-1}\right) \circ \Omega(g)(x) = \Omega\left(g^{-1}\right)\left(xg\right) = xgg^{-1} = x\text{.}
\end{equation*}
To see that \(\Omega\) is an injection, suppose \(a,b \in G\) and \(\Omega(a) = \Omega(b)\text{.}\) Then
\begin{equation*}
a = 1a = \Omega(a)(1) = \Omega(b)(1) = 1b = b\text{.}
\end{equation*}
However, this is not a morphism of groups because, in general,
\begin{equation*}
\Omega(a) \circ \Omega(b)(x) = \Omega(a)(xb) = (xb)a= x(ba) \neq x(ab) = \Omega(ab)(x)\text{.}
\end{equation*}
2.
Prove that the Right Regular Representation gives yet another isomorphism with a subgroup of \(S_G\text{.}\)
Solution.
Let \(G\) be a group. We prove that \(G\) is isomorphic to a subgroup of \(S_G\text{.}\) For each \(g \in G\text{,}\) define the function
\begin{align*}
\Psi(g) \colon G \amp\to G\\
x \amp \mapsto xg^{-1}
\end{align*}
This is a bijection because for all \(x \in G\text{,}\)
\begin{equation*}
\Psi(g) \circ \Psi\left(g^{-1}\right)(x) = \Psi(g)\left(xg\right) = xgg^{-1} = x
\end{equation*}
and
\begin{equation*}
\Psi\left(g^{-1}\right) \circ \Psi(g)(x) = \Psi\left(g^{-1}\right)\left(xg^{-1}\right) = xg^{-1}g = x\text{.}
\end{equation*}
This defines a morphism of sets
\begin{align*}
\Psi \colon G \amp\to S_G\\
g \amp\mapsto \Psi(g)
\end{align*}
that is surjective onto its image.
To see that \(\Psi\) is injective, suppose there exist \(g_1,g_2 \in G\) such that \(\Psi(g_1) = \Psi(g_2)\text{.}\) By definition, for every \(x \in G\text{,}\) \(\Psi(g_1)(x) = \Psi(g_2)(x)\text{.}\) Taking \(x = 1\) yields
\begin{equation*}
g_1^{-1} = \Psi(g_1)(1) = \Psi(g_2)(1) = g_2^{-1}\text{,}
\end{equation*}
and thus \(g_1 = g_2\text{.}\) Hence \(\Psi\) is injective.
Finally, let \(g_1, g_2 \in G\) be given. Since multiplication is associative on \(G\text{,}\) we observe that for all \(x \in G\text{,}\)
\begin{align*}
\Psi(g_1 g_2)(x) \amp= x\left(g_1g_2\right)^{-1}\\
\amp= \left(xg_2^{-1}\right)g_1^{-1}\\
\amp= \Psi(g_1)\left(xg_2^{-1}\right)\\
\amp= \Psi(g_1) \circ \Psi(g_2)(x)\\
\amp= \left(\Psi(g_1) \circ \Psi(g_2)\right)(x)\text{.}
\end{align*}
Hence \(\Psi(g_1 g_2) = \Psi(g_1) \circ \Psi(g_2)\text{.}\) Therefore \(\Psi\) is an isomorphism between \(G\) and its image,
\begin{equation*}
\Psi(G) = \left\{\Psi(g) \;\middle\vert\; g \in G\right\} \subseteq S_G\text{.}
\end{equation*}
3.
Prove that if \(G\) is abelian, then the image of \(G\) under the left regular representation and the image of \(G\) under the right regular representation are the same subgroup.
Solution.
Assume \(G\) is abelian. The images of \(G\) are the subgroups
\begin{equation*}
\Phi(G) = \left\{\Phi(g) \;\middle\vert\; g \in G\right\}
\quad\text{and}\quad
\Psi(G) = \left\{\Psi(g) \;\middle\vert\; g \in G \right\}
\end{equation*}
We prove that \(\Phi(G) \subseteq \Psi(G)\) and \(\Psi(G) \subseteq \Phi(G)\text{.}\)
For the first inclusion, let \(g \in G\) be given. Since \(G\) is abelian and \(\left(g^{-1}\right)^{-1} = g\text{,}\) for all \(x \in G\)
\begin{equation*}
\Phi(g)(x) = gx = xg = x\left(g^{-1}\right)^{-1} = \Psi\left(g^{-1}\right)(x)\text{.}
\end{equation*}
Hence \(\Phi(g) = \Psi\left(g^{-1}\right)\in \Psi(G)\) and thus \(\Phi(G) \subseteq \Psi(G)\text{.}\)
The reverse inclusion is effectively the same. Given \(g \in G\) and \(x \in G\text{,}\)
\begin{equation*}
\Psi(g)(x) = xg^{-1} = g^{-1}x = \Phi\left(g^{-1}\right)(x)
\end{equation*}
implies \(\Psi(g) = \Phi\left(g^{-1}\right) \in \Phi(G)\text{.}\) Therefore \(\Phi(G) = \Psi(G)\text{.}\)
