Companion matrix

Any matrix with entries in a field 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 GLn(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}\!D V, 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\\ \vdots & \vdots & \!\!\!\ddots\!\!\! &\vdots \\ 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}\!D V. We can read the eigenvectors of C(p) with C(p)(w_i) = \lambda_i w_i from the equation C(p) = V^{-1}\!D V: 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 eigenvectors 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 Jordan block for each distinct root; if the multiplicity of the root is m, then the block is an m × m matrix with \lambda on the diagonal and 1 in the entries just above the diagonal. In this case, V becomes a confluent Vandermonde matrix. ==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 {{ block indent | em = 1.5 | text = 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}\! D V, 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}. ==Theoretical complexity: calculation by fast matrix multiplication==

It is possible to calculate the companion matrix in a fast way with the use of fast matrix multiplication algorithms in the time O({n^\omega }) for ~2.37\le\omega. Respective algorithms is given by ==See also==