A companion matrix is a matrix with a prescribed characteristic polynomial. I would like to show them from a broader perspective: companion matrices are the matrix version of a shift operator.

Pick a polynomial $P \in \CC[X]$, which we normalise for convenience.

\begin{align}P(X) = α_0 + α_1X + \cdots + α_{n-1}X^{n-1} + X^n \end{align}

Now, as this polynomial generates an ideal in $\CC[X]$ one can define the corresponding quotient $E$.

\begin{align}E := \CC[X] / P \end{align}

$E$ is now a vector space of the same dimension as the degree of the polynomial $P$.

Let us define the shift operator by: \begin{align} S\colon E &\rightarrow E \\ [Q] &\rightarrow [X Q] \end{align}

For instance, in the basis $([1], [X], [X]^2, \ldots, [X]^{n-1})$ the matrix of the shift operator $S$ is given by \begin{align} \begin{bmatrix} 0 & & & & &-α_0\\ 1 & 0 & & 0 & &-α_1\\ & 1 & 0 & & &-α_2\\ & & \ddots & \ddots & &\vdots \\ & 0 & & 1 & &-α_{n-2}\\ & & & & 1& -α_{n-1} \end{bmatrix}\end{align}

This is the matrix called companion matrix. It is well known that the spectrum of that matrix consists of the roots of the polynomial $P$. But let us look at the operator $S$ independently of the choice of basis. This gives us a slick proof of that well-known fact.

So we set out to prove:

The spectrum of $S$ consists of the roots of $P$.

Indeed, if $[Q]\in E$ is an eigenvector of $S$ with eigenvalue $λ$, then \begin{align} S [Q] = λ [Q] \end{align} This means that there exists a polynomial $R\in\CC[X]$ such that: \begin{align} XQ = λQ + RP \end{align} or: $(X-λ)Q = RP$

Now, $(X-λ)$ is an irreducible polynomial so it divides either $R$ or $P$.

Suppose first that it divides $R$. Then by dividing by $(X-λ)$ we obtain: $Q = \frac{R}{X-λ} P$, which implies $[Q] = 0$, but this is impossible since $[Q]$ was supposed to be an eigenvector, thus nonzero. We conclude that $(X-λ)$ divides $P$, so $λ$ is a root of $P$.

On the other hand, if $λ$ is a root of $P$, then $P = (X-λ)Q$, and $[Q]$ is then an eigenvector with eigenvalue $λ$.

What is this good for?

Well, we can now define companion matrices in other bases, and we know that their spectrum will still be given by the roots of $P$.

Consider the example of Newton polynomials. Given $n+1$ pairs of numbers $(x_i,y_i)$ for $0≤i≤n$, an interpolation polynomial which interpolates these pairs can be written as \begin{align} P(x)=c_{0,0}+c_{0,1} (x-x_0)+c_{0,2} (x-x_0)(x-x_1) + \cdots + c_{0,n} (x-x_0) \cdots (x-x_{n-1}) . \end{align}

One can compute the coefficients $c_{0,j}$ using the following recursion formulae: $c_{i,0}=y_i$ and \begin{align} c_{i,j}=\frac{c_{i+1,j-1}-c_{i,j-1}}{x_{i+j}-x_i} . \end{align}

The companion matrix of that polynomial in the basis $\big\{\prod_{0≤j≤k}(x-x_j)\big\}_{0≤k≤n-1}$ may now be written as:

\begin{align} \begin{bmatrix} x_0 & & & & &-c_{0,0}/c_{0,n}\\ 1 & x_1 & & & 0 &-c_{0,1}/c_{0,n}\\ & 1 & x_2 & & &-c_{0,2}/c_{0,n}\\ & & \ddots & \ddots & &\vdots \\ & 0 & & 1 & x_{n-2}& -c_{0,n-2}/c_{0,n}\\ & & & & 1& \phantom{M}x_{n-1}- c_{0,n-1}/c_{0,n} \end{bmatrix} \end{align}