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 1, ... , v n$ , one has

Cv_{i}=C^{{i}}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 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 $V=K^{n}$ for $A$ , 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 $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:

VC(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

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 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 n -1$ , this matrix reduces to Sylvester's cyclic shift matrix, or circulant matrix.

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 .

This article is issued from Wikipedia - version of the 10/30/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Companion matrix

Characterization

Diagonalizability

Linear recursive sequences

See also

Notes