**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)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)**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)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.