# Characteristic polynomials exhaust all monic polynomials?

Let $A$ be an $n\times n$ matrix, then $\mathrm{char}_A(x):=\det(xI-A)$ is a monic polynomial of degree $n$. It is called the characteristic polynomial of $A$. My question is the converse:

Let $p(x)$ be a monic polynomial of degree $n$. Can we always find an $n\times n$ matrix such that $p(x)=\mathrm{char}_A(x)$?

-
– Qiaochu Yuan Oct 8 '11 at 1:20
This proves that finding eigenvalues is exactly equivalent to solving polynomial equations. In particular, finding eigenvalues is a very non-linear problem for which only approximation methods exist, no "formulas". – lhf Oct 8 '11 at 1:24
Well, this can even be done simultaneously for minimal polynomial, surprising... Thanks! – Syang Chen Oct 8 '11 at 1:44

In fact, the (Frobenius) companion matrix mentioned in the wiki article Qiaochu linked to is but one of a family of "congenial matrices", matrices specially constructed such that their characteristic polynomial is a given polynomial represented in "some basis".

Apart from the usual

$$c_n\det\left(x\mathbf I-\begin{pmatrix}-\frac{c_{n-1}}{c_n}&\cdots&-\frac{c_1}{c_n}&-\frac{c_0}{c_n}\\1&&&\\&\ddots&&\\&&1&\end{pmatrix}\right)=c_0+c_1 x+\cdots+c_n x^n$$

one can build a companion matrix for a polynomial represented as a Newton interpolating polynomial:

$$\begin{split}a_n\det\left(x\mathbf I-\begin{pmatrix}r_n-\frac{a_{n-1}}{a_n}&\cdots&-\frac{a_1}{a_n}&-\frac{a_0}{a_n}\\1&r_{n-1}&&\\&\ddots&\ddots&\\&&1&r_1\end{pmatrix}\right)=\\a_0+a_1(x-r_1)+\cdots+a_n(x-r_1)(x-r_2)\cdots(x-r_n)\end{split}$$

and even for a polynomial represented in terms of orthogonal polynomials ("comrade matrices"), as well as for other special representations.

In short, there is a whole family of matrices that can be constructed such that their characteristic polynomial is a given polynomial expressed in terms of some basis.

-

Not only does the companion matrix exist, but it is quite easy to motivate its construction. Fix a field $k$ and consider the action of $x$ on $k[x]/p(x)$, which (by monicity of $p$) is a $k$-vector space of dimension $n$ with basis $\{ 1, x, x^2, ... x^{n-1} \}$. The action of $x$ in this basis is the companion matrix. Moreover, by construction $p(x) = 0$ is the minimal polynomial of $x$, and it has degree $n$ so it is also the characteristic polynomial.

-
A clever proof... So I have learned a new term, a matrix whose characteristic polynimial equals its minimal polynomial is called a companion matrix, which is always similar to the canonical form you showed. – Syang Chen Oct 8 '11 at 6:09
@Xiang: Actually, the definition of "companion matrix" is "any matrix whose characteristic polynomial is the same (up to a constant factor) as a given polynomial". The "equals its minimal polynomial" portion is something you derive from that property. – J. M. Oct 8 '11 at 6:21