Suppose you are given an arbitrary polynomial $P$ of degree $n$, with real coefficients. My question is: is it always possible to construct a square matrix of order $n$ s.t. $P$ is the characteristic polynomial?
It seems reasonable to me to think that it is possible, but I cannot prove it. I wonder if there is a way to obtain such a matrix for a generic polynomial. Moreover, if the answer is no, it would be even more interesting: what would prevent a polynomial from being "characteristic"? I tried to find such counterexample, but I couldn't do it, maybe there is a trivial one that I missed. Any help would be appreciated.
The answer is yes. Assume the field is $\mathbb{C}$. Given a monic polynomial $P(x)$, split it into linear factors over $\mathbb{C}$, $P(x)=\prod_{i=1}^n(x-x_i)$ (with multiplicities). Now the diagonal matrix with $x_1,\ldots,x_n$ on the diagonal satisfies what you want.
The answer is still positive over $\mathbb{R}$ (when the coefficients of the polynomial are real), but a better argument is required - in fact it is enough to show that every degree $2$ polynomial is a characteristic polynomial for some matrix. Indeed let $P(x)=x^2+ax+b$. Then the matrix: $$M_{a,b}=\begin{pmatrix}0&0\\b&-a\end{pmatrix}$$ has characteristic polynomial $x^2+ax+b$. Now given a monic polynomial, split it into linear and quadric factors, and define the block diagonal matrix where each block corresponds to some factor of the decomposition of the polynomial.
Edit: characteristic polynomials are always monic. So if you allow non-monic polynomials, they will never be a matrix characteristic polynomial.