Determining a matrix from its characteristic polynomial

Any two similar matrices $B = P A P^{-1}$ will have the same characteristic polynomial. Also $A$ and $A^T$ have the same characteristic polynomial.

While the matrix $A$ which has a given characteristic polynomial is not unique, it is often convenient to choose an upper Hessenberg matrix called the (Frobenius) companion matrix or its (lower Hessenberg) transpose.

That is, the $n\times n$ matrix:

$$ \begin{bmatrix} 0 & 0 & \ldots & 0 & -c_0 \\ 1 & 0 & \ldots & 0 & -c_1 \\ 0 & 1 & \ldots & 0 & -c_2 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \ldots & 1 & -c_{n-1} \end{bmatrix} $$

has characteristic polynomial $p(x) = x^n + c_{n-1}x^{n-1} + \ldots + c_1 x + c_0$.

One approach to finding the roots of a polynomial is to apply eigenvalue solvers to the companion matrix for the polynomial.

If $A$ and $S$ are $n\times n$ matrices, with $S$ invertible, then $A$ and $SAS^{-1}$ have the same characteristic polynomial. But even non similar matrices can have the same characteristic polynomial: consider $$ \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix},\qquad \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix},\qquad \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{bmatrix} $$ So you cannot find the matrix having a given characteristic polynomial.

There is no way you can determine the matrix from its characteristic polynomial because the characteristic polynomial is determined by $n$ numbers and the matrix by $n^2$ numbers.