Companion matrix

In linear algebra, the Frobenius companion matrix of the monic polynomial
:$p(t)=c_0 + c_1 t + \cdots + c_t^ + t^n ~,$
is the square matrix defined as

:$C(p)=\begin 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_ \end$.

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 are equal to .

In this sense, the matrix is the "companion" of the polynomial .

If is an ''n''-by-''n'' matrix with entries from some field , then the following statements are equivalent:
* is similar to the companion matrix over of its characteristic polynomial
* the characteristic polynomial of coincides with the minimal polynomial of , equivalently the minimal polynomial has degree
* there exists a cyclic vector in $V=K^n$ for , meaning that is a basis of ''V''. Equivalently, such that ''V'' is cyclic as a K /math>-module (and V \cong K (p(x))); one says that is ''non-derogatory''.

Not every square matrix is similar to a companion matrix. But every square matrix 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 . For details, see rational canonical form.

Diagonalizability

If has distinct roots (the eigenvalues of ''C''(''p'')), then ''C''(''p'') is diagonalizable as follows:
:$V C(p) V^ = \operatorname(\lambda_1,\dots,\lambda_n)$
where is the Vandermonde matrix corresponding to the 's.

In that case, Bellman, Richard (1987), ''Introduction to Matrix Analysis'', SIAM, . traces of powers ''m'' of readily yield sums of the same powers ''m'' of all roots of ''p''(''t''),
:$\operatorname C^m = \sum_^n \lambda_i^m ~.$

If 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
:$p(t)=c_0 + c_1 t + \cdots + c_t^ + t^n \,$
the (transpose) companion matrix
:$C^T(p)=\begin 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_ \end$
generates the sequence, in the sense that
:$C^T\begina_k\\ a_\\ \vdots \\ a_ \end = \begina_\\ a_\\ \vdots \\ a_ \end.$
increments the series by 1.

The vector is an eigenvector of this matrix for eigenvalue , when is a root of the characteristic polynomial .

For , and all other , i.e., , this matrix reduces to Sylvester's cyclic shift matrix, or circulant matrix.

See also

*Frobenius endomorphism
*Cayley–Hamilton theorem
*Krylov subspace

Notes

{{DEFAULTSORT:Companion Matrix
Matrices
Matrix theory