Companion Matrix

The companion matrix of the polynomial of degree n ≥ 1, \[ p(\lambda ) = \lambda^n + a_{n-1} \lambda^{n-1} + a_{n-2} \lambda^{n-2} + \cdots + a_1 \lambda + a_0 \] is defined as \[ {\bf A} = \begin{bmatrix} 0& 1 & 0 & \cdots & 0&0 \\ 0&0&1& \cdots &0&0 \\ \vdots & \vdots & \vdots * \ddots & \vdots & \vdots \\ 0&0&0&\cdots & 0&1 \\ - a_0 & -a_1 & -a_2 & \cdots & a_{n-2} & -a_{n-1} \end{bmatrix} , \] in which the first superdiagonal consists entirely of one above the last row are zeroes.
The characteristic polynomial for this matrix is
\[ \chi_A (\lambda ) = \det \left( \lambda {\bf I} - {\bf A} \right) = \det \begin{bmatrix} \lambda& -1 & 0 & \cdots & 0&0 \\ 0&\lambda&-1& \cdots &0&0 \\ \vdots & \vdots & \vdots * \ddots & \vdots & \vdots \\ 0&0&0&\cdots & \lambda&-1 \\ -a_0 & a_1 & -a_2 & \cdots & a_{n-2} & \lambda + a_{n-1} \end{bmatrix} \]
If we multiply columns 2, 3, … , n by &lambda and subtract from the first column, all elements of this column will be p(λ), Since the cofactor of the last element is 1, the characteristic polynomial of A becomes
\[ \chi_A (\lambda ) = \det \left( \lambda {\bf I} - {\bf A} \right) = p(\lambda ) . \]
The companion matrix is singular if and only if 𝑎₀ = 0. The following examples give the reason for considering companion matrices.

   
Example 1: Let us consider a linear differential equation with constant coefficients \[ p \left( \texttt{D} \right) x(t) = 0 , \qquad \texttt{D} = \frac{\text d}{{\text d}t} . \]    ■
End of Example 1
   
Example 2: We consider the difference equation \[ p(E)\,x_n = 0 , \] where E is a shift operator: E&thinsplxn = xn+1. The matrix of the system in the companion matrix for the polynomial p(λ). For example, the difference equation of the third order \[ x_{n+3} + c\, x_{n+2} + b\, x_{n+1} + a\, x_n = 0 \] can be replaced by the system of the first order \begin{align*} x_{n+1} &= y_n , \\ y_{n+1} &= z_n , \\ z_{n+1} &= - a\, x_n - b\, y_n - c\, z_n . \end{align*}    ■
End of Example 2

 

Eigenvalues

The eigenvalue equation for matrix A can be written as
\begin{equation} \label{EqEigen.1} {\bf A}\,{\bf e}(\lambda ) = \lambda\,{\bf e}(\lambda ) , \end{equation}
where e(λ) is the column vector
\[ {\bf e}\left( \lambda \right) = \left[ 1,\ \lambda , \ \lambda^2 , \ \ldots , \ \lambda^{n-1} \right]^{\mathrm T} . \]
If λi, i = 1, 2, … , m ≤ n, is an eigenvalue of A, Eq.\eqref{EqEigen.1} is valid for λ = λi. Moreover, the rank of matrix λI − A is always n − 1, even when λi is a multiple zero of the polynomial p(λ); for the minor of the element (n, 1) in the last row has a determinant of value 1. The eigenvalue λi is therefore associated with just one eigenvector e = e(λi). Two eigenvectors are called equal if one is a scalar multiple of the other. We state this result as

Theorem 1: If the polynomial p(λ) of degree n has m ≤ n distinct zeroes λi, i = 1, 2, … , m, then its companion matrix has exactly m independent eigenvectors

\begin{equation} \label{EqEigen.2} {\bf e}_i = \left[ 1, \ \lambda_i , \ \lambda^2_i , \ \ldots , \ \lambda_i^{n-1} \right]^{\mathrm T} , \qquad i=1,2,\ldots , m , \end{equation}
associated with eigenvalues λi, i = 1, 2, … , m ≤ n.
These eigenvectors are linearly independent since the rank of the m × n Vandermonde matrix formed from their components is exactly m.

 

When the companion matrix has an eigenvalue λi of multiplicity k, λi satisfies the equations
\[ p(\lambda_i ) = 0, \quad p' (\lambda_i ) = 0, \quad p'' (\lambda_i ) = 0, \quad \cdots , \ p^{k-1}(\lambda_i ) = 0. \]
The first of these equations is equivalent to the matrix equation \eqref{EqEigen.1}; the others are equivalent to matrix equations obtained from \eqref{EqEigen.1}; by k − 1 successive differentiations with respect to λ:
\[ {\bf A}\,{\bf e}^{(j)} (\lambda ) = \lambda\,{\bf e}^{(j)} (\lambda ) + j\,{\bf e}^{(j-1)} (\lambda ) , \qquad j=1,2,\ldots , k-1 . \]
Here we assume that e(0) = e(λ). These are equivalent to the system
\begin{equation} \label{EqEigen.3} {\bf A}\, \frac{{\bf e}^{(j)} (\lambda )}{j!} = \lambda \,\frac{{\bf e}^{(j)} (\lambda )}{j!} + \frac{{\bf e}^{(j-1)} (\lambda )}{(j-1)!} , \qquad j=1,2,\ldots , k-1. \end{equation}
Thus, when λ = λi is a k-tuple zero of p(λ), we have the k equations
\begin{align*} {\bf A}\,{\bf e}_1 &= \lambda_1 {\bf e}_1 , \\ {\bf A}\,{\bf e}_2 &= \lambda_1 {\bf e}_2 + {\bf e}_1 , \\ {\bf A}\,{\bf e}_3 &= \lambda_1 {\bf e}_3 + {\bf e}_2 , \\ \cdots & \ \cdots \\ {\bf A}\,{\bf e}_k &= \lambda_1 {\bf e}_k + {\bf e}_{k-1} , \end{align*}
where e₁ = e(λ ₁) is the eigenvector and
\begin{equation} \label{EqEigen.4} {\bf e}_{j+1} = \frac{1}{j!}\, {\bf e}^{(j)} \left( \lambda_1 \right) , \qquad j=1,2,\ldots , k-1 , \end{equation}
are, by definition, k - 1 generalized eigenvectors associated with λ ₁. Thus with every k-tuple eigenvalue we associate k eigenvectors of which k -1 are generalized. We note that the way in which equations \eqref{EqEigen.3} are derived guarantees their consistency. Moreover the k vectors
\begin{align*} {\bf e}_1 &= \left[ 1, \ \lambda_1 , \ \lambda_1^2 , \ \ldots , \ \lambda_1^{k-1} \right]^{\mathrm T} , \\ {\bf e}_2 &= \left[ 0, \ 1, \ 2\, \lambda_1 , \ 3\,\lambda_1^2 , \ \ldots , \ \left( n-1 \right) \lambda_1^{n-2} \right]^{\mathrm T} , \\ {\bf e}_3 &= \left[ 0, \ 0, \ 1, \ 3\, \lambda_1 , \ , \ \ldots , \ \binom{n-1}{2} \, \lambda_1^{n-3} \right]^{\mathrm T} , \\ \cdots & \quad \cdots \\ {\bf e}_k &= \left[ 0, \ 0, \ \cdots , \ \binom{n-1}{k} \, \lambda_1^{n-k} \right]^{\mathrm T} , \end{align*}
are linearly independent since the rank of the k × n matrix formed components is k; for the k × k determinant on the left has the value 1. The entire set of n eigenvalues of A, simple and multiple, are now with n eigenvectors; m of these, given by \eqref{EqEigen.2}, are the eigenvectors associated with the m distinct eigenvalues, whereas the n - m remaining are generalized eigenvectors of the type \eqref{EqEigen.4}. The entire set is linearly independent and may be used to reduce A to its Jordan normal form.    
Example 3:    ■
End of Example 3

 



  1. Brand, L., The Complement Matrix and its Properties, The American Mathematical Monthly, Vol. 71, No. 6, 1964, pp. 629-634. https://www.jstor.org/stable/2312322
  2. Conrad, Keith, The minimal polynomial and some applications