The Regular Representation

Claim: All finite groups are necessarily subgroups of the permutation group $S_n$ for some $n$.

We shall prove this claim by explicitly constructing a map that takes each element $g\in G$ to a permutation in $n=\textrm{ord}(G)$ objects. Treat the group $G$ as the ordered set $(g_1, g_2,\ldots, g_n)$ i.e., we fix the order in which we write the $n$ elements of the group. Consider the action of an arbitrary group element $g$ on the ordered set $G$

(1)
\begin{align} g\cdot G \equiv (g\cdot g_1,\ g\cdot g_2,\ \ldots,\ g\cdot g_n)= \left(g_{p(1)},\ g_{p(2)},\ \ldots, \ g_{p(n)}\right) \ , \end{align}

where we have defined $p(i)$ via the relation $g_{p(i)} = g\cdot g_i$. Clearly, the set $g\cdot G$ is a permutation of the ordered set $G.$ We thus obtain the required map

(2)
\begin{align} g\mapsto \begin{pmatrix} 1 & 2 & \cdots & n \\ p(1) & p(2) & \cdots & p(n) \end{pmatrix}\ . \end{align}

Exercise: Verify that the map is compatible with the composition rules of the two groups.

Exercise: Show that $\mathbb{Z}_3=(e,g,g^2~|~g^3=e)$ gets mapped to the cyclic subgroup of $S_3$.

The map that we constructed above can be converted into a map from $G$ to the space of $n\times n$ matrices, called the permutation matrices, in the following manner. Treat the ordered set $G$ as a column vector and define the matrix $M(g)$ by

(3)
\begin{align} \begin{pmatrix} g\cdot g_1 \\ g\cdot g_2 \\ \vdots\\ g\cdot g_n \end{pmatrix} \equiv M(g) \cdot \begin{pmatrix} g_1 \\ g_2 \\ \vdots\\ g_n \end{pmatrix}\ . \end{align}

Verify that $M(g_1\cdot g_2) = M(g_1) M(g_2)$. This implies that the group composition rule becomes ordinary matrix multiplication under this map. Thus, one obtains a faithful representation of the group in the form of the permutation matrices — this is known as the regular representation of $G$. It is not hard to see that the identity element gets mapped to the $n\times n$ identity matrix, i.e., $M(e)=I_n$.

Note: Any map from a group to a set of matrices that maps the group composition to matrix multiplication, in a faithful manner, is called a representation of the group.

Exercise: Show that $M(g)=\left(\begin{smallmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{smallmatrix}\right)$ for the group $\mathbb{Z}_3$. Also verify that $M(g^2)=M(g)^2$ and $M(g^3)=M(g)^3=M(e)=I_3$, where $I_3$ is the $3\times 3$ identity matrix.