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.