1 Definition and Construction

1.1 Companion matrix for a monic polynomial

Let \[ p(x)=x^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0 \] be a monic polynomial over a field \(F\). The companion matrix \(C(p)\in F^{n\times n}\) is defined by \[ C(p)= \begin{pmatrix} 0&0&\cdots&0&-a_0\\ 1&0&\cdots&0&-a_1\\ 0&1&\cdots&0&-a_2\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&\cdots&1&-a_{n-1} \end{pmatrix}. \] Equivalently: it has ones on the subdiagonal, zeros elsewhere except in the last column, and the last column consists of \((-a_0,-a_1,\dots,-a_{n-1})^{T}\).

This construction is designed so that the polynomial \(p(x)\) appears directly as the characteristic polynomial of \(C(p)\).

1.2 Companion matrix for a general (non-monic) polynomial

For a general polynomial \[ q(x)=b_nx^n+b_{n-1}x^{n-1}+\cdots+b_0,\qquad b_n\neq 0, \] one commonly reduces to the monic case by dividing by \(b_n\): \[ p(x)=\frac{1}{b_n}q(x)=x^n+\tilde a_{n-1}x^{n-1}+\cdots+\tilde a_0. \] The companion matrix is then \(C(q):=C(p)\). With this convention, \(\chi_{C(q)}(x)=p(x)=q(x)/b_n\). In some contexts a variant is used so that \(\chi(x)=q(x)\) exactly; that choice depends on whether the leading coefficient is absorbed into the definition.

1.3 Relationship to characteristic polynomials

A key defining property is \[ \chi_{C(p)}(x)=\det(xI-C(p))=p(x) \] for monic \(p\) as above. Thus, the roots of \(p\) (counted with algebraic multiplicity) coincide with the eigenvalues of \(C(p)\), and factorization patterns of \(p\) translate into corresponding algebraic and Jordan-theoretic properties of the matrix.

1.4 Basic matrix structure and visualization

The companion matrix provides a canonical “shift plus last-column feedback” viewpoint. The subdiagonal ones implement a shift of coordinates, while the last column encodes the coefficients of the polynomial through negative signs. This sparse structure makes \(C(p)\) easy to write down and convenient for both theoretical arguments and computational routines that exploit matrix sparsity.

2 Algebraic Properties

2.1 Eigenvalues and roots of the polynomial

Because \(\chi_{C(p)}(x)=p(x)\) (for monic \(p\)), the eigenvalues of \(C(p)\) are exactly the roots of \(p\) in an algebraic closure of \(F\). If \(p\) factors as \[ p(x)=\prod_{i}(x-\lambda_i)^{m_i}, \] then each \(\lambda_i\) is an eigenvalue with algebraic multiplicity \(m_i\). The companion form therefore turns questions about roots—such as multiplicity and splitting behavior—into standard spectral questions for a matrix.

2.2 Similarity and invariance under change of basis

Companion matrices for the same monic polynomial are unique up to similarity in the following sense: any two matrices over \(F\) with the same rational canonical form are similar. The companion matrix is the canonical representative of the simplest case associated with one invariant factor, and it captures the algebra of multiplication by \(x\) on the quotient algebra \(F[x]/(p(x))\). In that quotient, changing the basis corresponds to a similarity transformation of the representing matrix.

2.3 Minimal polynomial versus characteristic polynomial

For \(C(p)\), the minimal polynomial equals the polynomial \(p\) itself when \(p\) is irreducible or, more generally, when the invariant factor structure has a single invariant factor equal to \(p\). In general, the minimal polynomial always divides the characteristic polynomial; for companion matrices, it often reflects how much of \(p\) truly governs the cyclic behavior of the matrix. When \(p\) is square-free, the minimal and characteristic polynomials coincide; when \(p\) has repeated factors, the minimal polynomial can be smaller depending on the associated Jordan structure.

2.4 Jordan form and what it implies about factorization

Over an algebraically closed field, the Jordan canonical form of \(C(p)\) organizes eigenvalues according to the powers of \((x-\lambda)\) appearing in \(p\). The algebraic multiplicities come from the factor exponents in \(p\), while the sizes and number of Jordan blocks are controlled by the ranks of \((C(p)-\lambda I)^k\). Consequently, the partition of each multiplicity into Jordan block sizes provides a refinement of the factorization data, showing how repeated roots manifest at the level of generalized eigenvectors.

2.5 Companion matrices and cyclic vectors

A central feature of companion matrices is that they typically arise from a cyclic module: there exists a vector \(v\in F^n\) such that \[ \{v,\,Cv,\,C^2v,\,\dots,\,C^{n-1}v\} \] spans \(F^n\). In standard coordinates for \(C(p)\), one can take a natural basis vector so that the induced “shift” generates the whole space. Cyclicity has consequences: it ties the minimal polynomial to the polynomial that annihilates the cyclic vector, and it ensures that the matrix is governed by a single invariant factor.

3.1 Frobenius (rational canonical) form connection

The Frobenius, or rational canonical, form expresses a matrix as a direct sum of companion matrices corresponding to invariant factors. In this sense, the companion matrix is the building block of rational canonical form. When a matrix has invariant factors \(f_1(x)\mid f_2(x)\mid\cdots\mid f_k(x)\), the associated rational canonical form is block diagonal with companion matrices of those \(f_i\). The companion matrix for a polynomial \(p\) corresponds to the case where there is a single invariant factor equal to \(p\).

3.2 Companion matrix for reversed (reciprocal) polynomials

Given a polynomial \(p(x)\) of degree \(n\), its reciprocal (reversed) polynomial is often defined as \[ p^*(x)=x^n p(1/x) \] (up to normalization). Companion matrices for reversed polynomials relate to transformations such as reversing the order of basis vectors or considering similarity between matrices representing multiplication by \(x\) versus multiplication by \(x^{-1}\) in an appropriate localization. This connects eigenvalue behavior under inversion: roots \(\lambda\) of \(p\) correspond to roots \(1/\lambda\) of \(p^*\), with corresponding spectral transformations.

3.3 Block companion matrices and multiple polynomials

When one needs to encode several polynomial constraints simultaneously, block companion matrices generalize the idea of shift structure to larger block sizes. For example, block companion forms can represent systems where coefficients are matrices rather than scalars, or where multiple polynomials appear as part of a larger state update. These variants are used in structured linearizations and in algorithms that reduce matrix polynomial problems to generalized eigenvalue problems for block matrices.

3.4 Companion matrices over different fields/rings

The construction works over any commutative ring where the coefficients of the polynomial live and where division by the leading coefficient is handled appropriately (for the non-monic case). Over rings that are not fields, some spectral interpretations require care: eigenvalues may not exist in the ring itself, and notions like Jordan form depend on extending to an algebraic closure of a field. Still, the companion matrix remains valuable as an algebraic representation of the module \(R[x]/(p)\) and retains many structural properties.

4 Computational Aspects

4.1 Constructing the matrix from coefficients

Given coefficients \(a_0,\dots,a_{n-1}\) of a monic polynomial, construction is straightforward: place ones on the subdiagonal and set the last column to \((-a_0,-a_1,\dots,-a_{n-1})^T\). All other entries are zero. This yields a sparse matrix whose nonzero pattern is fixed regardless of coefficient values, which helps both symbolic computations and numerical implementation.

4.2 Computing characteristic polynomial and determinants

Although \(\chi_{C(p)}(x)\) equals \(p(x)\) by design, computational routines may still use determinants or polynomial evaluations to verify identities or to handle variants (e.g., generalized companion forms, block companion matrices, or nonstandard conventions). Determinant computation for structured matrices can exploit sparsity and recurrence relations to avoid generic \(O(n^3)\) methods when only certain polynomial coefficients are needed.

4.3 Efficient algorithms for powers and matrix-vector products

The companion matrix acts on vectors in a predictable way. Multiplying \(C(p)\) by a vector shifts its components and forms a linear combination using the polynomial coefficients. As a result, computing \(C(p)v\), \(C(p)^2v\), or evaluating \(p(C(p))v\) can be done efficiently with \(O(n^2)\) arithmetic for dense coefficient vectors, and with better performance when further structure or fast polynomial arithmetic is available. This efficiency is useful in simulation, Krylov subspace methods, and linear recurrence evaluation.

4.4 Numerical considerations and conditioning

In floating-point arithmetic, companion matrices can be numerically sensitive because eigenvalues and eigenvectors may be ill-conditioned, especially for polynomials with widely varying coefficient magnitudes or clustered roots. Standard eigenvalue algorithms may produce less reliable roots than methods that use polynomial-specific techniques (such as root-finding algorithms tailored to \(p\)). When used in numerical control or system identification, practitioners often favor balanced or scaled forms and apply careful conditioning checks.

5 Applications in Algebra and Beyond

5.1 Linear recurrences and state-space representations

Companion matrices provide a direct bridge between polynomials and linear recurrences. If one forms a state vector from consecutive terms of a sequence, multiplication by the companion matrix advances the state by one step. The characteristic polynomial then governs the recurrence, enabling systematic derivation of closed forms, analysis of stability (in numerical contexts), and characterization of long-term behavior through spectral information.

5.2 Polynomial remainder techniques via matrix identities

Matrix identities involving \(p(C(p))\) simplify polynomial computations. In the quotient algebra interpretation, evaluating polynomials at the companion matrix corresponds to reducing polynomials modulo \(p\). This viewpoint underlies remainder and reduction techniques: computations that would require polynomial long division can be translated into algebraic operations with matrices acting on vectors or with structured transformations that mimic reduction mod \(p\).

5.3 Control-theoretic realizations overview-level

In control theory, companion-like matrices appear as canonical “controller/observer” realizations and in linear time-invariant state-space models. The point of contact is that the transfer function denominator often determines a state update matrix with a characteristic polynomial matching a given polynomial. Companion structures thus offer a convenient parameterization and facilitate the design of realizations with prescribed polynomial dynamics.

5.4 Dynamical systems interpretation of companion form

Interpreting \(C(p)\) as a state transition operator gives an intuitive dynamical systems picture. The shift structure moves information forward through the state coordinates, while the last column injects the influence of the polynomial coefficients. This structure makes the companion form a natural “minimal wiring diagram” for systems whose evolution is described by a single characteristic polynomial.

6 Examples and Worked Problems

6.1 Low-degree examples (quadratic and cubic)

For \(p(x)=x^2+a_1x+a_0\), the companion matrix is \[ C(p)=\begin{pmatrix} 0&-a_0\\ 1&-a_1 \end{pmatrix}. \] For \(p(x)=x^3+a_2x^2+a_1x+a_0\), \[ C(p)=\begin{pmatrix} 0&0&-a_0\\ 1&0&-a_1\\ 0&1&-a_2 \end{pmatrix}. \] In each case, direct computation of \(\det(xI-C(p))\) reproduces \(p(x)\).

6.2 Example: matching characteristic polynomial

Suppose \[ p(x)=x^3-4x^2+5x-2. \] Then \(a_2=-4\), \(a_1=5\), \(a_0=-2\), and \[ C(p)=\begin{pmatrix} 0&0&2\\ 1&0&-5\\ 0&1&4 \end{pmatrix}. \] The characteristic polynomial of this matrix equals \(x^3-4x^2+5x-2\), so the eigenvalues are the roots of that cubic.

6.3 Example: from factorization to Jordan structure

Let \[ p(x)=(x-1)^2(x+2). \] Over an algebraically closed field, eigenvalues are \(1\) (algebraic multiplicity 2) and \(-2\) (multiplicity 1). The factor \((x-1)^2\) indicates that the Jordan form has either one Jordan block of size 2 for eigenvalue \(1\) or two blocks of size 1 (which would require additional conditions yielding diagonalizability). The companion matrix’s cyclic nature typically produces the largest Jordan block consistent with the invariant factor data, so repeated factors often correspond to nontrivial generalized eigenvectors.

6.4 Example: deriving a recurrence from matrix powers

Given \(p(x)=x^3+a_2x^2+a_1x+a_0\) and its companion matrix \(C(p)\), one can show that the sequence \[ s_k = e_1^T C(p)^k e_1 \] (obtained by probing powers with a fixed vector, such as the first basis vector \(e_1\)) satisfies the same recurrence as encoded by \(p\). Since \(p(C(p))=0\), multiplying by \(C(p)^k\) yields \(C(p)^{k+3}\) as a linear combination of lower powers, and projecting with \(e_1^T\) converts that relation into a scalar recurrence.

7 Common Pitfalls and Notes

7.1 Monic vs non-monic normalization

A frequent source of confusion is whether the leading coefficient is included or normalized away. If \(q(x)\) is not monic and one divides by its leading coefficient to form \(p(x)=q(x)/b_n\), then \(\chi_{C(q)}(x)=p(x)\), not \(q(x)\) itself, under the standard monic convention. Clear bookkeeping prevents mismatched characteristic polynomials.

7.2 Field assumptions (coefficients, roots, extensions)

Statements about eigenvalues and Jordan form typically require working over a field where the polynomial splits or where the relevant canonical forms exist. Over a general field, eigenvalues may not lie in the field, and Jordan decomposition may require extension to an algebraic closure. Companion matrices remain defined, but spectral interpretations depend on the chosen field.

7.3 Confusing different companion conventions

Several variants exist in the literature regarding sign placement and whether coefficients appear reversed or not. These conventions produce matrices that may be similar or may correspond to related polynomials (such as reciprocals or sign-changes). When comparing results across references, checking the exact definition of \(C(p)\) is essential.

7.4 Interpretations that depend on the choice of polynomial form

The polynomial itself is not unique as an expression: factoring, scaling, or using reciprocal forms changes the associated companion matrix under certain conventions. Likewise, expressing dynamics via companion form depends on which variable and which normalization are used in the polynomial. Interpretations—such as which recurrence coefficients appear with which signs—should always be tied back to the exact polynomial-to-matrix rule employed.