Companion matrix

In linear algebra, the Frobenius companion matrix of the monic polynomial $p(x)=c_{0}+c_{1}x+\cdots +c_{n-1}x^{n-1}+x^{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}}.$

Some authors use the transpose of this matrix, $C(p)^{T}$ , which is more convenient for some purposes such as linear recurrence relations (see below).

$C(p)$ is defined from the coefficients of $p(x)$ , while the characteristic polynomial as well as the minimal polynomial of $C(p)$ are equal to $p(x)$ .^[1] In this sense, the matrix $C(p)$ and the polynomial $p(x)$ are "companions".

Similarity to companion matrix

Any matrix $A$ with entries in a field $F$ has characteristic polynomial $p(x)=\det(xI-A)$ , which in turn has companion matrix $C(p)$ . These matrices are related as follows.

The following statements are equivalent:

A is similar over F to $C(p)$ , i.e. A can be conjugated to its companion matrix by matrices in GL_n(F);
the characteristic polynomial $p(x)$ coincides with the minimal polynomial of A , i.e. the minimal polynomial has degree n;
the linear mapping $A:F^{n}\to F^{n}$ makes $F^{n}$ a cyclic $F[A]$ -module, having a basis of the form $\{v,Av,\ldots ,A^{n-1}v\}$ ; or equivalently $F^{n}\cong F[X]/(p(x))$ as $F[A]$ -modules.

If the above hold, one says that A is non-derogatory.

Not every square matrix is similar to a companion matrix, but every square matrix is similar to a block diagonal matrix made of companion matrices. If we also demand that the polynomial of each diagonal block divides the next one, they are uniquely determined by A, and this gives the rational canonical form of A.

Diagonalizability

The roots of the characteristic polynomial $p(x)$ are the eigenvalues of $C(p)$ . If there are n distinct eigenvalues $\lambda _{1},\ldots ,\lambda _{n}$ , then $C(p)$ is diagonalizable as $C(p)=V^{-1}\!DV$ , where D is the diagonal matrix and V is the Vandermonde matrix corresponding to the $λ$ 's: $D={\begin{bmatrix}\lambda _{1}&0&\!\!\!\cdots \!\!\!&0\\0&\lambda _{2}&\!\!\!\cdots \!\!\!&0\\0&0&\!\!\!\cdots \!\!\!&\lambda _{n}\end{bmatrix}},\qquad V={\begin{bmatrix}1&\lambda _{1}&\lambda _{1}^{2}&\!\!\!\cdots \!\!\!&\lambda _{1}^{n-1}\\1&\lambda _{2}&\lambda _{2}^{2}&\!\!\!\cdots \!\!\!&\lambda _{2}^{n-1}\\[-1em]\vdots &\vdots &\vdots &\!\!\!\ddots \!\!\!&\vdots \\1&\lambda _{n}&\lambda _{n}^{2}&\!\!\!\cdots \!\!\!&\lambda _{n}^{n-1}\end{bmatrix}}.$ Indeed, a reasonably hard computation shows that the transpose $C(p)^{T}$ has eigenvectors $v_{i}=(1,\lambda _{i},\ldots ,\lambda _{i}^{n-1})$ with $C(p)^{T}\!(v_{i})=\lambda _{i}v_{i}$ , which follows from $p(\lambda _{i})=c_{0}+c_{1}\lambda _{i}+\cdots +c_{n-1}\lambda _{i}^{n-1}+\lambda _{i}^{n}=0$ . Thus, its diagonalizing change of basis matrix is $V^{T}=[v_{1}^{T}\ldots v_{n}^{T}]$ , meaning $C(p)^{T}=V^{T}D\,(V^{T})^{-1}$ , and taking the transpose of both sides gives $C(p)=V^{-1}\!DV$ .

We can read the eigenvectors of $C(p)$ with $C(p)(w_{i})=\lambda _{i}w_{i}$ from the equation $C(p)=V^{-1}\!DV$ : they are the column vectors of the inverse Vandermonde matrix $V^{-1}=[w_{1}^{T}\cdots w_{n}^{T}]$ . This matrix is known explicitly, giving the eignevectors $w_{i}=(L_{0i},\ldots ,L_{(n-1)i})$ , with coordinates equal to the coefficients of the Lagrange polynomials $L_{i}(x)=L_{0i}+L_{1i}x+\cdots +L_{(n-1)i}x^{n-1}=\prod _{j\neq i}{\frac {x-\lambda _{j}}{\lambda _{j}-\lambda _{i}}}={\frac {p(x)}{(x-\lambda _{i})\,p'(\lambda _{i})}}.$ Alternatively, the scaled eigenvectors ${\tilde {w}}_{i}=p'\!(\lambda _{i})\,w_{i}$ have simpler coefficients.

If $p(x)$ has multiple roots, then $C(p)$ is not diagonalizable. Rather, the Jordan canonical form of $C(p)$ contains one diagonal block for each distinct root, an m × m block with $\lambda$ on the diagonal if the root $\lambda$ has multiplicity m.

Linear recursive sequences

A linear recursive sequence defined by $a_{k+n}=-c_{0}a_{k}-c_{1}a_{k+1}\cdots -c_{n-1}a_{k+n-1}$ for $k\geq 0$ has the characteristic polynomial $p(x)=c_{0}+c_{1}x+\cdots +c_{n-1}x^{n-1}+x^{n}$ , whose transpose companion matrix $C(p)^{T}$ generates the sequence: ${\begin{bmatrix}a_{k+1}\\a_{k+2}\\\vdots \\a_{k+n-1}\\a_{k+n}\end{bmatrix}}={\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}}{\begin{bmatrix}a_{k}\\a_{k+1}\\\vdots \\a_{k+n-2}\\a_{k+n-1}\end{bmatrix}}.$ The vector $v=(1,\lambda ,\lambda ^{2},\ldots ,\lambda ^{n-1})$ is an eigenvector of this matrix, where the eigenvalue $\lambda$ is a root of $p(x)$ . Setting the initial values of the sequence equal to this vector produces a geometric sequence $a_{k}=\lambda ^{k}$ which satisfies the recurrence. In the case of n distinct eigenvalues, an arbitrary solution $a_{k}$ can be written as a linear combination of such geometric solutions, and the eigenvalues of largest complex norm give an asymptotic approximation.

From linear ODE to first-order linear ODE system

Similarly to the above case of linear recursions, consider a homogeneous linear ODE of order n for the scalar function $y=y(t)$ : $y^{(n)}+c_{n-1}y^{(n-1)}+\dots +c_{1}y^{(1)}+c_{0}y=0.$ This can be equivalently described as a coupled system of homogeneous linear ODE of order 1 for the vector function $z(t)=(y(t),y'(t),\ldots ,y^{(n-1)}(t))$ : $z'=C(p)^{T}z$ where $C(p)^{T}$ is the transpose companion matrix for the characteristic polynomial $p(x)=x^{n}+c_{n-1}x^{n-1}+\cdots +c_{1}x+c_{0}.$ Here the coefficients $c_{i}=c_{i}(t)$ may be also functions, not just constants.

If $C(p)^{T}$ is diagonalizable, then a diagonalizing change of basis will transform this into a decoupled system equivalent to one scalar homogeneous first-order linear ODE in each coordinate.

An inhomogeneous equation $y^{(n)}+c_{n-1}y^{(n-1)}+\dots +c_{1}y^{(1)}+c_{0}y=f(t)$ is equivalent to the system: $z'=C(p)^{T}z+F(t)$ with the inhomogeneity term $F(t)=(0,\ldots ,0,f(t))$ .

Again, a diagonalizing change of basis will transform this into a decoupled system of scalar inhomogeneous first-order linear ODEs.

Cyclic shift matrix

In the case of $p(x)=x^{n}-1$ , when the eigenvalues are the complex roots of unity, the companion matrix and its transpose both reduce to Sylvester's cyclic shift matrix, a circulant matrix.

Multiplication map on a simple field extension

Consider a polynomial $p(x)=x^{n}+c_{n-1}x^{n-1}+\cdots +c_{1}x+c_{0}$ with coefficients in a field $F$ , and suppose $p(x)$ is irreducible in the polynomial ring $F[x]$ . Then adjoining a root $\lambda$ of $p(x)$ produces a field extension $K=F(\lambda )\cong F[x]/(p(x))$ , which is also a vector space over $F$ with standard basis $\{1,\lambda ,\lambda ^{2},\ldots ,\lambda ^{n-1}\}$ . Then the $F$ -linear multiplication mapping

m_{\lambda }:K\to K

defined by

m_{\lambda }(\alpha )=\lambda \alpha

has an n × n matrix $[m_{\lambda }]$ with respect to the standard basis. Since $m_{\lambda }(\lambda ^{i})=\lambda ^{i+1}$ and $m_{\lambda }(\lambda ^{n-1})=\lambda ^{n}=-c_{0}-\cdots -c_{n-1}\lambda ^{n-1}$ , this is the companion matrix of $p(x)$ : $[m_{\lambda }]=C(p).$ Assuming this extension is separable (for example if $F$ has characteristic zero or is a finite field), $p(x)$ has distinct roots $\lambda _{1},\ldots ,\lambda _{n}$ with $\lambda _{1}=\lambda$ , so that $p(x)=(x-\lambda _{1})\cdots (x-\lambda _{n}),$ and it has splitting field $L=F(\lambda _{1},\ldots ,\lambda _{n})$ . Now $m_{\lambda }$ is not diagonalizable over $F$ ; rather, we must extend it to an $L$ -linear map on $L^{n}\cong L\otimes _{F}K$ , a vector space over $L$ with standard basis $\{1{\otimes }1,\,1{\otimes }\lambda ,\,1{\otimes }\lambda ^{2},\ldots ,1{\otimes }\lambda ^{n-1}\}$ , containing vectors $w=(\beta _{1},\ldots ,\beta _{n})=\beta _{1}{\otimes }1+\cdots +\beta _{n}{\otimes }\lambda ^{n-1}$ . The extended mapping is defined by $m_{\lambda }(\beta \otimes \alpha )=\beta \otimes (\lambda \alpha )$ .

The matrix $[m_{\lambda }]=C(p)$ is unchanged, but as above, it can be diagonalized by matrices with entries in $L$ : $[m_{\lambda }]=C(p)=V^{-1}\!DV,$ for the diagonal matrix $D=\operatorname {diag} (\lambda _{1},\ldots ,\lambda _{n})$ and the Vandermonde matrix V corresponding to $\lambda _{1},\ldots ,\lambda _{n}\in L$ . The explicit formula for the eigenvectors (the scaled column vectors of the inverse Vandermonde matrix $V^{-1}$ ) can be written as: ${\tilde {w}}_{i}=\beta _{0i}{\otimes }1+\beta _{1i}{\otimes }\lambda +\cdots +\beta _{(n-1)i}{\otimes }\lambda ^{n-1}=\prod _{j\neq i}(1{\otimes }\lambda -\lambda _{j}{\otimes }1)$ where $\beta _{ij}\in L$ are the coefficients of the scaled Lagrange polynomial ${\frac {p(x)}{x-\lambda _{i}}}=\prod _{j\neq i}(x-\lambda _{j})=\beta _{0i}+\beta _{1i}x+\cdots +\beta _{(n-1)i}x^{n-1}.$

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.

[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.

[1]

v t e Matrix classes
Explicitly constrained entries	Alternant Anti-diagonal Anti-Hermitian Anti-symmetric Arrowhead Band Bidiagonal Bisymmetric Block-diagonal Block Block tridiagonal Boolean Cauchy Centrosymmetric Conference Complex Hadamard Copositive Diagonally dominant Diagonal Discrete Fourier Transform Elementary Equivalent Frobenius Generalized permutation Hadamard Hankel Hermitian Hessenberg Hollow Integer Logical Matrix unit Metzler Moore Nonnegative Pentadiagonal Permutation Persymmetric Polynomial Quaternionic Signature Skew-Hermitian Skew-symmetric Skyline Sparse Sylvester Symmetric Toeplitz Triangular Tridiagonal Vandermonde Walsh Z
Constant	Exchange Hilbert Identity Lehmer Of ones Pascal Pauli Redheffer Shift Zero
Conditions on eigenvalues or eigenvectors	Companion Convergent Defective Definite Diagonalizable Hurwitz-stable Positive-definite Stieltjes
Satisfying conditions on products or inverses	Congruent Idempotent or Projection Invertible Involutory Nilpotent Normal Orthogonal Unimodular Unipotent Unitary Totally unimodular Weighing
With specific applications	Adjugate Alternating sign Augmented Bézout Carleman Cartan Circulant Cofactor Commutation Confusion Coxeter Distance Duplication and elimination Euclidean distance Fundamental (linear differential equation) Generator Gram Hessian Householder Jacobian Moment Payoff Pick Random Rotation Routh-Hurwitz Seifert Shear Similarity Symplectic Totally positive Transformation
Used in statistics	Centering Correlation Covariance Design Doubly stochastic Fisher information Hat Precision Stochastic Transition
Used in graph theory	Adjacency Biadjacency Degree Edmonds Incidence Laplacian Seidel adjacency Tutte
Used in science and engineering	Cabibbo–Kobayashi–Maskawa Density Fundamental (computer vision) Fuzzy associative Gamma Gell-Mann Hamiltonian Irregular Overlap S State transition Substitution Z (chemistry)
Related terms	Jordan normal form Linear independence Matrix exponential Matrix representation of conic sections Perfect matrix Pseudoinverse Row echelon form Wronskian
Mathematics portal List of matrices Category:Matrices