(Obviously inspired by an answer by @hardmath the other day)
A generating element for the cyclic group $C_n$ can be represented by the matrix
$$\left[\begin{array}{ll}{\bf 0}^T&1\\{\bf I}_{n-1}&\bf 0\end{array}\right]$$
This happens to coincide with the companion matrix for the monic polynomial for the roots of unity: $$P_n(x)=x^n-1$$Is this a coincidence or can we construct representation matrices for generators for other kinds of groups using companion matrices (in some systematic way)?
One way of thinking about the construction of companion matrices is the following. Suppose $P(x)$ is a monic polynomial and we'd like to construct a matrix with $P(x)$ as characteristic polynomial. We do this by writing down the algebra
$$A = F[x]/P(x)$$
where $F$ is the underlying field. By construction, the operator
$$L_x : A \ni a \mapsto xa \in A$$
given by multiplication on the left by $x$ has minimal polynomial $P(x)$; it's not hard to show that in fact it has characteristic polynomial $P(x)$. So any matrix describing $L_x$ will have the right characteristic polynomial. To write down such a matrix we write down a basis for $A$, and a very convenient basis is $\{ 1, x, \dots, \dots x^{n-1} \}$ where $n = \deg P$. It's an exercise from here to show that you get exactly the companion matrix.
The analogous construction for finite groups, which overlaps with the above construction for cyclic groups and only for cyclic groups, is to start with a finite group $G$ and construct the group algebra
$$A = F[G].$$
Then the operators $L_g$ given by multiplication by $g \in G$ have matrix representations given by using the basis given by the elements of $G$. These matrices are always permutation matrices. This construction produces what is called the regular representation of $G$.
