Companion matrix

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 v1, ... , vn, one has

Cv_i = C^{i}v_1 = v_{i+1}

(for i < n), and v1 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 recurrence relations.

Characterization[edit]

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 V=K^n for A, meaning that {v, Av, A2v, ..., An−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.

Diagonalizability[edit]

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

V C(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),

\mathrm{Tr}   C^m = \sum_{i=1}^{n}  \lambda_i^m ~.

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

Linear recursive sequences[edit]

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,t2, ..., tn-1) is an eigenvector of this matrix for eigenvalue t, when t is a root of the characteristic polynomial p(t).

For c0 = −1, and all other ci=0, i.e., p(t) = tn−1, this matrix reduces to Sylvester's cyclic shift matrix, or circulant matrix.

See also[edit]

Notes[edit]

  1. ^ Horn, Roger A.; Charles R. Johnson (1985). Matrix Analysis. Cambridge, UK: Cambridge University Press. pp. 146–147. ISBN 0-521-30586-1. Retrieved 2010-02-10. 
  2. ^ Bellman, Richard (1987), Introduction to Matrix Analysis, SIAM, ISBN 0898713994 .