Companion matrix

From Wikipedia, the free encyclopedia

1 Definition
2 Characterization
3 Diagonalizability
4 Linear recursive sequences

[edit] Definition

In linear algebra, the companion matrix of the monic polynomial

$p(t)=c_0 + c_1 t + \dots + c_{n-1}t^{n-1} + t^n$

$C(p)=\begin{bmatrix} 0 & 0 & \dots & 0 & -c_0 \\ 1 & 0 & \dots & 0 & -c_1 \\ 0 & 1 & \dots & 0 & -c_2 \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & \dots & 1 & -c_{n-1} \\ \end{bmatrix}.$

With this convention, and writing the basis as $v_1,\dots,v_n$ , one has $C v i = C i - 1 v 1 = v i + 1$ (for $i < n$ ), and $v 1$ generates V as a $K [C]$ -module: C cycles basis vectors.

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

[edit] Characterization

The characteristic polynomial as well as the minimal polynomial of C(p) are equal to p; 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 a companion matrix over K
the characteristic polynomial of A coincides with the minimal polynomial of A
there exists a cyclic vector v in $V = K n$ for A, meaning that {v, Av, A²v,...,A^n-1v} 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 A 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 A. This is the rational canonical form of A.

[edit] Diagonalizability

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

$V C(p) V^{-1} = \mbox{diag}(\lambda_1,\dots,\lambda_n)$

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

[edit] Linear recursive sequences

Given a linear recursive sequence with characteristic polynomial

$p(t)=c_0 + c_1 t + \dots + c_{n-1}t^{n-1} + t^n$

the (transpose) companion matrix

$C(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}$