Companion matrix

In linear algebra, the Frobenius companion matrix of the monic polynomial

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

is the square matrix defined as

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

Some authors use the transpose of this matrix, which (dually) cycles coordinates, and is more convenient for some purposes, like linear recurrence relations.

Characterization[]

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=K[A]/(p(A))}$); one says that A is non-derogatory.

Not every square matrix is similar to a companion matrix. But every matrix is similar to a matrix made up of blocks of companion matrices.^[why?] Furthermore, these companion matrices can be chosen so that their polynomials divide each other; then they are uniquely determined by A. This is the rational canonical form of A.

Diagonalizability[]

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).

Linear recursive sequences[]

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.

See also[]

• Frobenius endomorphism
• Cayley–Hamilton theorem
• Krylov subspace

Notes[]