A companion matrix is an upper Hessenberg matrix of the form

Alternatively, can be transposed and permuted so that the coefficients appear in the first or last column or the last row. By expanding the determinant about the first row it can be seen that

so the coefficients in the first row of are the coefficients of its characteristic polynomial. (Alternatively, in add times the th column to the last column for , to obtain as the new last column, and expand the determinant about the last column.) MacDuffee (1946) introduced the term “companion matrix” as a translation from the German “Begleitmatrix”.

Setting in gives , so is nonsingular if and only if . The inverse is

Note that is in companion form, where is the reverse identity matrix, and the coefficients are those of the polynomial , whose roots are the reciprocals of those of .

A companion matrix has some low rank structure. It can be expressed as a unitary matrix plus a rank- matrix:

Also, differs from in just the first and last columns, so , where is a rank- matrix.

If is an eigenvalue of then is a corresponding eigenvector. The last rows of are clearly linearly independent for any , which implies that is nonderogatory, that is, no two Jordan blocks in the Jordan canonical form contain the same eigenvalue. In other words, the characteristic polynomial is the same as the minimal polynomial.

The MATLAB function `compan`

takes as input a vector of the coefficients of a polynomial, , and returns the companion matrix with , …, .

Perhaps surprisingly, the singular values of have simple representations, found by Kenney and Laub (1988):

where . These formulae generalize to block companion matrices, as shown by Higham and Tisseur (2003).

## Applications

Companion matrices arise naturally when we convert a high order difference equation or differential equation to first order. For example, consider the Fibonacci numbers , , , , , , which satisfy the recurrence for , with . We can write

where is a companion matrix. This expression can be used to compute in operations by computing the matrix power using binary powering.

As another example, consider the differential equation

Define new variables

Then

or

so the third order scalar equation has been converted into a first order system with a companion matrix as coefficient matrix.

## Computing Polynomial Roots

The MATLAB function `roots`

takes as input a vector of the coefficients of a polynomial and returns the roots of the polynomial. It computes the eigenvalues of the companion matrix associated with the polynomial using the `eig`

function. As Moler (1991) explained, MATLAB used this approach starting from the first version of MATLAB, but it does not take advantage of the structure of the companion matrix, requiring flops and storage instead of the flops and storage that should be possible given the structure of . Since the early 2000s much research has aimed at deriving methods that achieve this objective, but numerically stable methods proved elusive. Finally, a backward stable algorithm requiring flops and storage was developed by Aurentz, Mach, Vandebril, and Watkins (2015). It uses the QR algorithm and exploits the unitary plus low rank structure shown in (1). Here, backward stability means that the computed roots are the eigenvalues of for some with . It is not necessarily the case that the computed roots are the exact roots of a polynomial with coefficients with for all .

## Rational Canonical Form

It is an interesting observation that

Multiplying by the inverse of the matrix on the left we express the companion matrix as the product of two symmetric matrices. The obvious generalization of this factorization to matrices shows that we can write

We need the rational canonical form of a matrix, described in the next theorem, which Halmos (1991) calls “the deepest theorem of linear algebra”. Let denote the field or .

Theorem 1(rational canonical form).If then where is nonsingular and , with each a companion matrix.

The theorem says that every matrix is similar over the underlying field to a block diagonal matrix composed of companion matrices. Since we do not need it, we have omitted from the statement of the theorem the description of the in terms of the irreducible factors of the characteristic polynomial. Combining the factorization (2) and Theorem 1 we obtain

Since is nonsingular, and since can alternatively be taken nonsingular by considering the factorization of , this proves a theorem of Frobenius.

Theorem 2(Frobenius, 1910).For any there exist symmetric , either one of which can be taken nonsingular, such that .

Note that if with the symmetric then , so is symmetric. Likewise, is symmetric.

## Factorization

Fiedler (2003) noted that a companion matrix can be factorized into the product of simpler factors, of them being the identity matrix with a block placed on the diagonal, and he used this factorization to determine a matrix similar to . For it is

In general, Fielder’s construction yields an pentadiagonal matrix that is not simply a permutation similarity of . The fact that has block diagonal factors opens the possibility of obtaining new methods for finding the eigenvalues of . This line of research has been extensively pursued in the context of polynomial eigenvalue problems (see Mackey, 2013).

## Generalizations

The companion matrix is associated with the monomial basis representation of the characteristic polynomial. Other polynomial bases can be used, notably orthogonal polynomials, and this leads to generalizations of the companion matrix having coefficients on the main diagonal and the subdiagonal and superdiagonal. Good (1961) calls the matrix resulting from the Chebyshev basis a *colleague matrix*. Barnett (1981) calls the matrices corresponding to orthogonal polynomials *comrade matrices*, and for a general polynomial basis he uses the term *confederate matrices*. Generalizations of the properties of companion matrices can be derived for these classes of matrices.

## Bounds for Polynomial Roots

Since the roots of a polynomial are the eigenvalues of the associated companion matrix, or a Fiedler matrix similar to it, or indeed the associated comrade matrix or confederate matrix, one can obtain bounds on the roots by applying any available bounds for matrix eigenvalues. For example, since any eigenvalue of matrix satisfies , by taking the -norm and the -norm of the companion matrix we find that any root of the polynomial satisfies

either of which can be the smaller. A rich variety of such bounds is available, and these techniques extend to matrix polynomials and the corresponding block companion matrices.

## References

This is a minimal set of references, which contain further useful references within.

- Jared L. Aurentz, Thomas Mach, Raf Vandebril, and David S. Watkins, Fast and Backward Stable Computation of Roots of Polynomials, SIAM J. Matrix Anal. Appl. 36(3), 942–973, 2015.
- Stephen Barnett, Congenial Matrices, Linear Algebra Appl. 41, 277–298, 1981.
- Fernando De Terán and Froilán M. Dopico and Javier Pérez, New Bounds for Roots of Polynomials Based on Fiedler Companion Matrices, Linear Algebra Appl. 451, 197–230, 2014.
- Miroslav Fiedler, A Note on Companion Matrices, Linear Algebra Appl. 372, 325–331, 2003.
- Nicholas J. Higham and Françoise Tisseur, Bounds for Eigenvalues of Matrix Polynomials, Linear Algebra Appl. 358, 5–22, 2003
- Charles S. Kenney and Alan J. Laub, Controllability and Stability Radii for Companion Form Systems, Math. Control Signals Systems 1, 239–256, 1988.
- Cyrus Colton MacDuffee, The Theory of Matrices, Chelsea, New York, 1946.
- D. Steven Mackey, The Continuing Influence of Fiedler’s Work on Companion Matrices, Linear Algebra Appl. 439, 810–817, 2013.
- Cleve Moler, ROOTS—of Polynomials, That Is, The MathWorks Newsletter 5(1), 1991.
- Olga Taussky, The Role of Symmetric Matrices in the Study of General Matrices, Linear Algebra Appl. 5, 147–154, 1972.

## Related Blog Posts

This article is part of the “What Is” series, available from https://nhigham.com/category/what-is and in PDF form from the GitHub repository https://github.com/higham/what-is.