How to prove "eigenvalues of polynomial of matrix $A$ = polynomial of eigenvalues of matrix $A$ " Title looks a little bit twisted. What I want to say is the following:
$A\in\mathbb{R}^{n\times n}$, polynomial of matrix $A$: $P(A)=\displaystyle \sum_{k=0}^{n} c_k A^k$. $\lambda(A)$ is the set of eigenvalues of $A$. 
So, we want to prove $\lambda(P(A))=P(\lambda(A))$
So far, I can prove it when $A$ is diagonalisable, but when $A$ is not diagonalisable, it seems we can't just simply use Jordan normal form to prove it. (Or this statement won't hold when it's not diagonalisable?)
Can anyone suggest me something and help me out? Thanks!
 A: As mentioned by Matemáticos Chibchas, the statement is not true if the underlying field is not algebraically closed.
As mentioned by loup blanc, when the underlying field is algebraically closed, the statement can be easily proved by triangularising $A$.
Without using triangularisation, the statement can be proved in two steps as follows (see Graham (2018), Matrix Theory and Applications for Scientists and Engineers, theorems 7.6 and 7.7):
Theorem 1. Let $A\in M_n(F)$ where $F$ is algebraically closed. If the spectrum of $A$ (as a multiset) is $\{\lambda_1,\lambda_2,\ldots,\lambda_n\}$ and $p\in F[x]$ is a polynomial with coefficients in $F$, then
$$
\det\left(p(A)\right)=\prod_{i=1}^np(\lambda_i).
$$
Proof. By assumption, we have $\det(A-xI)=\prod_{i=1}^n(\lambda_i-x)$.
Let $p(x)=c\prod_{k=1}^r(x-c_k)$. Then
\begin{aligned}
\det(p(A))
&=\det\left(c\prod_{k=1}^r(A-c_kI)\right)\\
&=c^n\prod_{k=1}^r\det(A-c_kI)\\
&=c^n\prod_{k=1}^r\prod_{i=1}^n(c_k-\lambda_i)\\
&=\prod_{i=1}^n\left[c\prod_{k=1}^r(c_k-\lambda_i)\right]\\
&=\prod_{i=1}^np(\lambda_i).
\end{aligned}
Theorem 2. Let $A\in M_n(F)$ where $F$ is algebraically closed. If the spectrum of $A$ (as a multiset) is $\{\lambda_1,\lambda_2,\ldots,\lambda_n\}$ and $p\in F[x]$ is a polynomial with coefficients in $F$, then the spectrum of $p(A)$ is $\{p(\lambda_1),p(\lambda_2),\ldots,p(\lambda_n)\}$.
Proof. Let $y$ be an indeterminate independent of $x$ and $K$ be the algebraic closure of $F[y]$. Then $f(x)=y-p(x)$ is a polynomial with coefficients in $K$. By theorem 1,
$$
\det(yI-p(A))
=\det(f(A))
=\prod_{i=1}^nf(\lambda_i)
=\prod_{i=1}^n\left(y-p(\lambda_i)\right)
$$
over $K$. Therefore, as polynomials in $y$ over $F$, we have $\det(yI-p(A))=\prod_{i=1}^n\left(y-p(\lambda_i)\right)$ too. Hence $\{p(\lambda_1),p(\lambda_2),\ldots,p(\lambda_n)\}$ is the spectrum of $p(A)$.
A: The result is true only if you allow complex eigenvalues.
If $\lambda$ is a eigenvalue of $A$ then $Av=\lambda v$ for a nonzero column vector $v\in\mathbb R^n$. It is easy to show that in this case $p(A)v=p(\lambda)v$ for any nonconstant polynomial $p$, which shows that $p\bigl(\lambda(A)\bigr)\subseteq\lambda\bigl(p(A)\bigr)$. For the converse, let $\mu\in\lambda\bigl(p(A)\bigr)$, where $p$ is a nonconstant polynomial. You can factor $p(X)-\mu$ on the complex numbers, obtaining
$$p(X)-\mu=a\prod_{i=1}^m(X-a_i)\,,$$
where $a,a_i\in\mathbb C$. Thus, we have $p(A)-\mu I=a\prod_{i=1}^m(A-a_iI)$. Since the matrix $p(A)-\mu I$ is not invertible, then some matrix $A-a_iI$ is not invertible. This shows that $\mu=p(a_i)$, where $a_i$ is a complex eigenvalue of $A$, that is, for some nonzero column vector $w\in\mathbb C^n$ you have $Aw=a_iw$.
For the necessity of the inclusion of complex eigenvalues, consider the matrix $A=\binom{0\ -1}{1\ \ \ 0}$, which has not real eigenvalues (check it). However $A^2=-I$ do has $-1$ as eigenvalue. What happens in this case is that $i$ and $-i$ are the complex eigenvalues of $A$, so in particular $\lambda(A^2)=\{(\pm i)^2\}=\{-1\}$.
A: I am very surprised that @user1551 did not scream when he read this question (4 years ago). Of course, the answer is correct; yet, that is interesting, it is not the set of the eigenvalues but the MULTISET of the eigenvalues -we take into account the multiplicities-. Indeed, when using this result, in 99% of cases, we need the multiset version.
It is well-known that the multiset version proof is a direct consequence of the fact that any complex matrix is triangularizable.
