# Companion Matrix for a Polynomial

## Problem 85

Consider a polynomial
$p(x)=x^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0,$ where $a_i$ are real numbers.
Define the matrix
$A=\begin{bmatrix} 0 & 0 & \dots & 0 &-a_0 \\ 1 & 0 & \dots & 0 & -a_1 \\ 0 & 1 & \dots & 0 & -a_2 \\ \vdots & & \ddots & & \vdots \\ 0 & 0 & \dots & 1 & -a_{n-1} \end{bmatrix}.$

Then prove that the characteristic polynomial $\det(xI-A)$ of $A$ is the polynomial $p(x)$.
The matrix is called the companion matrix of the polynomial $p(x)$.

## Hint.

Use the mathematical induction. The base case is clear.
For the induction step, use the cofactor expansion and apply the induction hypothesis.

## Proof.

We prove that $p(x)=\det(xI-A)$ by induction on $n$.
The base case $n=1$ is clear since $A=[-a_0]$ is a $1 \times 1$ matrix and $\det(xI-A)=\det[x+a_0]=x+a_0$.

Induction step is as follows. Suppose that we have $p(t)=\det(xI-A)$ is true for a degree $n-1$ polynomial $p(t)$ and its companion matrix $A$.

We prove the statement for a degree $n$ polynomial.
Use the cofactor expansion corresponding to the first row, we obtain
\begin{align*}
\det(xI-A)&=\begin{vmatrix}
x & 0 & \dots & 0 &a_0 \\
-1 & x & \dots & 0 & a_1 \\
0 & -1 & \dots & 0 & a_2 \\
\vdots & & \ddots & & \vdots \\
0 & 0 & \dots & -1 & x+a_{n-1}
\end{vmatrix}\8pt] &=x \begin{vmatrix} x & 0 & \dots & 0 &a_1 \\ -1 & x & \dots & 0 & a_2 \\ \vdots & & \ddots & & \vdots \\ 0 & 0 & \dots & 1 & x+a_{n-1} \end{vmatrix} +(-1)^{n+1}a_0 \begin{vmatrix} -1 & x & \dots & 0 \\ 0 & -1 & \dots & 0 \\ \vdots & & \ddots & \vdots \\ 0 & 0 & \dots & -1 \end{vmatrix}. \end{align*} Now by the induction hypothesis, the first determinant is \[x^{n-1}+a_{n-1}x^{n-2}+\cdots+a_2 x+a_1. The second determinant is $(-1)^{n-1}$ since it is an $(n-1)\times (n-1)$ triangular matrix, determinant is the product of diagonal entries.

Therefore we have
\begin{align*}
\det(xI-A)&=x(x^{n-1}+a_{n-1}x^{n-2}+\cdots+a_2x+a_1)+(-1)^{n+1}a_0(-1)^{n-1}\\
&=x^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0=p(x).
\end{align*}
Thus the statement is true for a degree $n$ polynomial. By induction, we complete the proof.

## Related Question.

Another problem about the companion matrix of a polynomial is given in the post
Condition that a matrix is similar to the companion matrix of its characteristic polynomial“.

### 2 Responses

1. 03/21/2017

[…] For a basic question about the companion matrix of a polynomial, check out the post “Companion matrix for a polynomial“. […]

2. 07/14/2017

[…] post Companion matrix for a polynomial for the definition of the companion matrix and the proof of the above […]

This site uses Akismet to reduce spam. Learn how your comment data is processed.

##### If a Power of a Matrix is the Identity, then the Matrix is Diagonalizable

Let $A$ be an $n \times n$ complex matrix such that $A^k=I$, where $I$ is the $n \times n$ identity...

Close