Basics of the companion matrix同伴行列どうはんぎょうれつ

1Introduction

The companion matrix同伴行列どうはんぎょうれつ of a monic polynomial is a matrix built so that the polynomial becomes its characteristic polynomial. It turns a polynomial root problem into an eigenvalue problem.

Do not confuse the companion matrix with the adjugate matrix随伴行列ずいはんぎょうれつ from cofactors; they are different concepts.

2Terms and definitions

For a monic polynomial

define its companion matrix同伴行列どうはんぎょうれつ by

Some books use the transpose convention. The characteristic polynomial is unchanged by transpose, so the essential construction is the same.

3Plan

We prove three facts: roots of $p$p are eigenvalues of $C_p$C_p, eigenvalues of $C_p$C_p are roots of $p$p, and the characteristic polynomial of $C_p$C_p is $p\left(t\right)$p(t). The last row encodes the relation

4Intuitive explanation

The companion matrix records multiplication by $t$t while using the relation $p\left(t\right)=0$p(t)=0 to rewrite $t^n$t^n in terms of lower powers. If $p\left(\lambda \right)=0$p(\lambda)=0, then

becomes an eigenvector of $C_p$C_p with eigenvalue $\lambda$\lambda.

5Precise explanation

5.11. Roots give eigenvectors

If $p\left(\lambda \right)=0$p(\lambda)=0, set

The first $n-1$n-1 components of $C_{p}v\left(\lambda \right)$C_pv(\lambda) are $\lambda ,{\lambda }^2,\dots ,{\lambda }^{n-1}$\lambda,\lambda^2,\ldots,\lambda^{n-1}. The last component is

because $p\left(\lambda \right)=0$p(\lambda)=0. Hence $C_{p}v\left(\lambda \right)=\lambda v\left(\lambda \right)$C_pv(\lambda)=\lambda v(\lambda).

5.22. Eigenvalues give roots

Conversely, if $C_{p}x=\lambda x$C_px=\lambda x with $x\ne 0$x\ne0, the first $n-1$n-1 rows force

The vector would be zero if $x_1=0$x_1=0, so $x_1\ne 0$x_1\ne0. The last row then gives $p\left(\lambda \right)=0$p(\lambda)=0.

5.33. Why the characteristic polynomial is $p\left(t\right)$p(t)

Let $M=C_{p^T}$M=C_p^T. Transpose preserves the characteristic polynomial. The matrix $M$M satisfies

and

Thus $p\left(M\right)=0$p(M)=0. Since $e_1,M{e}_1,\dots ,M^{n-1}{e}_1$e_1,Me_1,\ldots,M^{n-1}e_1 is a basis, no nonzero polynomial of degree less than $n$n can annihilate $M$M. Hence the minimal polynomial of $M$M is $p\left(t\right)$p(t). The minimal polynomial divides the characteristic polynomial, and both are monic of degree $n$n, so the characteristic polynomial is $p\left(t\right)$p(t). Therefore ${\chi }_{C_p}\left(t\right)=p\left(t\right)$\chi_{C_p}(t)=p(t).

6Worked example

For

the companion matrix is

Since $p\left(t\right)=(t-1)(t-2)(t-3)$p(t)=(t-1)(t-2)(t-3), the eigenvalues are $1,2,3$1,2,3. For $\lambda =2$\lambda=2,

7Another viewpoint: cyclic bases

A companion matrix is also the matrix representation in a cyclic basis巡回基底じゅんかいきてい. If

is a basis, then $T$T shifts each basis vector to the next one, and the last vector is rewritten using the polynomial relation. This viewpoint connects companion matrices to minimal polynomials and later canonical forms.

8How to recognize when to use this

Use a companion matrix when turning a polynomial root problem into an eigenvalue problem, or when constructing a matrix with a prescribed characteristic polynomial. The adjugate matrix from cofactors is a different object.

9Scope

This lecture treats monic polynomials. A polynomial with nonzero leading coefficient can first be divided by that coefficient. The companion matrix can be defined even when the roots are not in the base field; to see all eigenvalues, one may extend the field.

10Final forms

11In one sentence

• A companion matrix accompanies a polynomial by making it the characteristic polynomial.
• The roots of the polynomial are the eigenvalues of the companion matrix.

12Exercise links

13Related links