Companion matrix

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

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

is the square matrix defined as

$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}}.$

With this convention, and on the basis v₁, ... , v_n, one has

$Cv_{i}=C^{i}v_{1}=v_{i+1}$

(for i < n), and v₁ generates Template:Mvar as a K[C]-module: Template:Mvar cycles basis vectors.

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 Template:Mvar.

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

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

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

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. Furthermore, these companion matrices can be chosen so that their polynomials divide each other; then they are uniquely determined by Template:Mvar. This is the rational canonical form of Template:Mvar.

Diagonalizability

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

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

where Template:Mvar is the Vandermonde matrix corresponding to the Template:Mvar's.

In that case, traces of powers m of Template:Mvar readily yield sums of the same powers m of all roots of p(t),

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

In general, the companion matrix may be non-diagonalizable.

Linear recursive sequences

Given a linear recursive sequence with characteristic polynomial

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

the (transpose) companion matrix

$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

$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 Template:Mvar, when Template:Mvar 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