# Companion matrix

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

is the square matrix defined as

With this convention, and on the basis *v*_{1}, ... , *v*_{n}, one has

(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 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 for A, meaning that {**v**,*A***v**,*A*^{2}**v**, ...,*A*^{n−1}**v**} is a basis of*V*. Equivalently, such that*V*is cyclic as a -module (and ); 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

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

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*),

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

## Linear recursive sequences

Given a linear recursive sequence with characteristic polynomial

the (transpose) companion matrix

generates the sequence, in the sense that

increments the series by 1.

The vector (1,*t*,*t*^{2}, ..., *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*_{0} = −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.

^{n}## See also

## Notes

- ↑ 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. - ↑ Bellman, Richard (1987),
*Introduction to Matrix Analysis*, SIAM, ISBN 0898713994 .