Do 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)$?

 A: 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.
There is even a symmetric tridiagonal companion matrix for polynomials whose roots are all real.
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.
A: 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.
