What is the origin of the companion matrix? I understand that every polynomial of degree $k$ has a companion matrix with a characteristic polynomial of the form $(-1)^kp(\lambda)$. I also understand the proof of this fact by induction.
My question is: what was the inspiration behind the idea of building a matrix of this form and study its properties?
$$
\begin{vmatrix}
-a_{k-1} - \lambda & -a_{k-2} & \dots & -a_{1} & -a_{0} \\
1 & -\lambda & \dots & 0 & 0 \\
0 & 1 & \ddots & 0 & 0 \\
0 & 0 & \dots & -\lambda & 0 \\
0 & 0 & \dots & 1 & -\lambda \\
\end{vmatrix}
$$
 A: The canonical matrices as representatives of similarity classes of matrices  were pretty much understood in the 1870's.
In 1870, Jordan gives his canonical form over $F_p$.
In 1878, Frobenius gives his one, over any field $K$. It is based on the notion of cyclic subspaces and vectors.
Let $A\in M_n(K)$ and $v\in K^n\setminus\{0\}$. If $\{v,Av,\cdots, A^{n-1}v\}$ is a basis of $K^n$, then, in this basis, $A$ becomes the matrix $C_p$, where $p(x)=x^n-\sum_{i=1}^{n} C_p[i,n]x^{i-1}$.
Note that Krylov will take up this idea in 1931.
My favourite polynomial (cf. the @Angina Seng ' post)  is $q(x)=x^5-x-1$; then, over $\mathbb{Q},\mathbb{R}$ or $\mathbb{C}$,
$C_q=\begin{pmatrix}0&0&0&0&1\\1&0&0&0&1\\0&1&0&0&0\\0&0&1&0&0\\0&0&0&1&0\end{pmatrix}$.  Here, $C_q$ is a cyclic matrix and $e_1$ is a cyclic vector.
Frobenius showed that every matrix has a canonical form as $diag(C_{p_1},\cdots,C_{p_k})$ where $p_i\in K[x]$ and $p_1|p_2|\cdots|p_k$, $p_k$ is the minimal polynomial of $A$ over $K$ and $p_1\cdots p_k$ its characteristic polyn.
By construction, the char. pol. of $C_p$ is $p$. Then (exercise), the set  of $A\in M_n(\mathbb{Q})$ s.t. $A^5-A-I=0_n$ are the matrices in the form $Q^{-1}diag(C_q,\cdots,C_q)Q$, where $Q\in GL_n(\mathbb{Q})$ and $n$ is a multiple of $5$.
Frobenius proved also the Cayley Hamilton theorem; indeed, Cayley showed only the cases $n=2,3$ and Hamilton the case $n=4$ (quaternions when you hold us...).
In fact, C.H. is a direct consequence of the Jordan decomposition; this was not very well understood at the time because Jordan, very busy with the study of Galois theory, remained confined to finite fields.
$\textbf{Remarks.}$ For the Frobenius form
Advantage: we obtain the invariant polynomials $p_i$ and we stay in the field $K$.
Disadvantage: we cannot calculate a closed form for $A^k$. Yet, using the remain of the division of $x^{1000}$ by $q(x)$, (in $0"015$)we obtain $C_q^{1000}=$

For the Jordan form
Advantage: the calculation of $A^n$ is easy (a priori).
Disadvantage (a hilarious one) if $A\in M_n(\mathbb{Q})$ with $n\geq 5$, we don't know how to calculate its Jordan form -because, in general (for example when $A=C_q$), the eigenvalues ​​of A cannot be written using radicals-
