Companion Operator

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 \mathbf{C}[X]$, which we normalise for convenience.

$$\begin{array}{r}P(X)={\alpha }_0+{\alpha }_{1}X+\cdots +{\alpha }_{n-1}{X}^{n-1}+X^n\end{array}$$

Now, as this polynomial generates an ideal in $\mathbf{C}[X]$ one can define the corresponding quotient $\mathbf{C}[X]/P$.

We denote by $$[\cdot ]:\mathbf{C}[X]\to \mathbf{C}[X]/P$$ the corresponding projection.

Let us define $$\begin{array}{r}E:=\mathbf{C}[X]/P\end{array}$$

The set $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{array}{rl}S:E& \to E\\ [Q]& \to [XQ]\end{array}$$

For instance, in the basis $$([1],[X],[X{]}^2,\dots ,[X{]}^{n-1})$$ the matrix of the shift operator $S$ is given by $$\begin{array}{r}\left[\begin{array}{cccccc}0& & & & & -{\alpha }_0\\ 1& 0& & 0& & -{\alpha }_1\\ & 1& 0& & & -{\alpha }_2\\ & & \ddots & \ddots & & ⋮\\ & 0& & 1& & -{\alpha }_{n-2}\\ & & & & 1& -{\alpha }_{n-1}\end{array}\right]\end{array}$$

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:

Indeed, if $[Q]\in E$ is an eigenvector of $S$ with eigenvalue $\lambda$, then $$\begin{array}{r}S[Q]=\lambda [Q]\end{array}$$ By definition of the quotient space $\mathbf{C}[X]/P$, this means that there exists a polynomial $R\in \mathbf{C}[X]$ such that: $$\begin{array}{r}XQ=\lambda Q+RP\end{array}$$ or: $$(X-\lambda )Q=RP$$

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

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

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

---

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\le i\le n$, an interpolation polynomial which interpolates these pairs can be written as $$\begin{array}{r}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{array}$$

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

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

$$\begin{array}{r}\left[\begin{array}{cccccc}{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 & & ⋮\\ & 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{array}\right]\end{array}$$