Companion matrix

The characteristic polynomial as well as the minimal polynomial of C(p) are equal to p.[1]

In this sense, the matrix C(p) is the "companion" of the polynomial p.

If A is an n-by-n matrix with entries from some field K, then the following statements are equivalent:

• A is similar to the companion matrix over K of its characteristic polynomial
• the characteristic polynomial of A coincides with the minimal polynomial of A, equivalently the minimal polynomial has degree n
• there exists a cyclic vector v in ${\displaystyle V=K^{n}}$ for A, meaning that {v, Av, A²v, ..., Aⁿ⁻¹v} is a basis of V. Equivalently, such that V is cyclic as a ${\displaystyle K[A]}$-module (and ${\displaystyle V\cong K[X]/(p(x))}$); one says that A is non-derogatory.

Not every square matrix is similar to a companion matrix. But every square matrix A is similar to a matrix made up of blocks of companion matrices. If we also demand that these polynomials divide each other, they are uniquely determined by A. For details, see rational canonical form.

If p(t) has distinct roots λ₁, ..., λ_n (the eigenvalues of C(p)), then C(p) is diagonalizable as follows:

${\displaystyle VC(p)V^{-1}=\operatorname {diag} (\lambda _{1},\dots ,\lambda _{n})}$

where V is the Vandermonde matrix corresponding to the λ's.

In that case,[2] traces of powers m of C readily yield sums of the same powers m of all roots of p(t),

${\displaystyle \operatorname {Tr} C^{m}=\sum _{i=1}^{n}\lambda _{i}^{m}~.}$

If p(t) has a non-simple root, then C(p) isn't diagonalizable (its Jordan canonical form contains one block for each distinct root).

Given a linear recursive sequence with characteristic polynomial

${\displaystyle p(t)=c_{0}+c_{1}t+\cdots +c_{n-1}t^{n-1}+t^{n}\,}$

the (transpose) companion matrix

${\displaystyle C^{T}(p)={\begin{bmatrix}0&1&0&\cdots &0\\0&0&1&\cdots &0\\\vdots &\vdots &\vdots &\ddots &\vdots \\0&0&0&\cdots &1\\-c_{0}&-c_{1}&-c_{2}&\cdots &-c_{n-1}\end{bmatrix}}}$

generates the sequence, in the sense that

${\displaystyle C^{T}{\begin{bmatrix}a_{k}\\a_{k+1}\\\vdots \\a_{k+n-1}\end{bmatrix}}={\begin{bmatrix}a_{k+1}\\a_{k+2}\\\vdots \\a_{k+n}\end{bmatrix}}.}$

increments the series by 1.

The vector (1,t,t², ..., t^n-1) is an eigenvector of this matrix for eigenvalue t, when t is a root of the characteristic polynomial p(t).

For c₀ = −1, and all other c_i=0, i.e., p(t) = tⁿ−1, this matrix reduces to Sylvester's cyclic shift matrix, or circulant matrix.

Consider first a homogeneous system in normal form.

A linear ODE of order n for the scalar function y

${\displaystyle y^{(n)}+c_{n-1}y^{(n-1)}+\dots +c_{1}y^{(1)}+c_{0}y=0}$

can be equivalently described as a coupled linear ODE system of order 1 for the vector function z = (y, y⁽¹⁾, ..., y^(n-1))^T

${\displaystyle z^{(1)}=C(p)^{T}z}$

where C(p)^T is the transpose of the companion matrix for the monic polynomial p(t) = c₀ + c₁ t + ... + c_n-1t^n-1 + tⁿ.

In the ODE setting the coefficients {c_i}_i=0^n-1 may be also functions of the independent variable as well and not just scalar values.

The system is in general coupled because z⁽¹⁾_n depends not only on z_n. If C(p) is invertible then it is possible to decouple it by making a coordinate transformation as described in the section on Diagonalizability.

For inhomogeneous case

${\displaystyle y^{(n)}+c_{n-1}y^{(n-1)}+\dots +c_{1}y^{(1)}+c_{0}y=f(x)}$

the inhomogenity term will be become a vector function of the form F(x)= (0, ..., 0, f(x))^T

${\displaystyle z^{(1)}=C(p)^{T}z+F(x)}$.

• Frobenius endomorphism
• Cayley–Hamilton theorem
• Krylov subspace