Eigenstructure of a matrix polynomial Given a square matrix A and a polynomial p(x), what is the eigenstructure of p(A)?
I can show that


*

*if $\{ \lambda_i \}_{i=1,2,...n}$ is the spectrum of $A$,
then $\{ p(\lambda_i \}_{i=1,2,...n}$ is the spectrum of $p(A)$.

*the geometric multiplicity of an eigenvalue $\lambda$ of $A$ is
less than or equal to the geometric multiplicity of $p(\lambda)$
of $p(A)$.
What I do not know is what happens to the algebraic multiplicites.
Any pointers? 
 A: Suppose $A$ is an $n$-by-$n$ matrix (or equivalently, assume that $A$ is a linear operator from a vector space of dimension $n$ to itself). If $\lambda$ is a scalar, then the geometric multiplicity of $\lambda$ for $A$ equals
$$
\dim \text{null}\ (A - \lambda I)
$$
and the algebraic multiplicity of $\lambda$ for $A$ equals
$$
\dim \text{null}\ (A - \lambda I)^n,
$$
where $\text{null}\ B$ denotes the subspace of vectors $v$ such that $Bv = 0$. [This definition of the algebraic multiplicity is cleaner than the definition via determinants and the characteristic polynomial, and it shows that the algebraic multiplicity also has geometric meaning. To see that this definition of algebraic multiplicity is equivalent to the other definition, see Linear Algebra Done Right.]
Thus to prove the desired results, we need only show that
\begin{equation}\text{null}\ (A - \lambda I)^k \subset \text{null}\
        (p(A) - p(\lambda) I)^k \tag{$*$}
\end{equation}
for every polynomial $p$ and every positive integer $k$. To prove this, fix a polynomial $p$ and a positive integer $k$. We can write
$$
p(z) - p(\lambda) = a_1 (z - \lambda) + \dots + a_m (z - \lambda)^m
$$
for some constants $a_1, \dots, a_m$. Thus
$$
\bigl(p(A) - p(\lambda) I\bigr)^k = \sum_{j = k}^{km} c_j (A - \lambda I)^j
$$
for some constants $\{c_j\}$. If $v$ is a vector such that $(A - \lambda I)^k v = 0$, then the equation above clearly implies that $\bigl(p(A) - p(\lambda) I\bigr)^k v = 0$,
completing the proof of ($*$) and thus the proof that the algebraic multiplicity of $\lambda$ for $A$ is less than or equal to the algebraic multiplicity of $p(\lambda)$ for $p(A)$.
A: Let us work first over the complex numbers (or any algebraically closed field). Then, the characteristic polynomial of $A \in M_n(\mathbb{C})$ splits as
$$ \chi_A(x) = (x - \lambda_1)^{d_1} \dots (x - \lambda_k)^{d_k} $$
where $d_i$ are the algebraic multiplicities, $\sum_{i=1}^k d_i = n$ and the $\lambda_i$ are the distinct eigenvalues of $A$. Since we are over the complex numbers, $A$ is similar to an upper triangular matrix $U$ where on the diagonal of $U$ the eigenvalue $\lambda_i$ appears $d_i$ times. Then $p(A)$ is similar to $p(U)$ where on the diagonal of $p(U)$ the eigenvalue $p(\lambda_i)$ also appears $d_i$ times. However, note that it is possible that $p(\lambda_i) = p(\lambda_j)$ for $i \neq j$. Thus, each $p(\lambda_i)$ is an eigenvalue of $p(A)$ with algebraic multiplicity
$$ d'_i = \sum_{1 \leq j \leq k, p(\lambda_j) = p(\lambda_i)} d_i. $$
To give you a concrete example, if $A = \operatorname{diag}(-1,1)$ and $p(x) = x^2$ then $p(A) = \operatorname{diag}(1,1)$ has only $1$ as an eigenvalue of multiplicity two. Each on $-1,1$ had algebraic multiplicity one but $p(-1)$ (or $p(1)$) has multiplicity $1 + 1 = 2$.
The above argument works over any field as long as the characteristic polynomial of $A$ splits into linear factors. If not, then this becomes more complicated. For example, consider
$$ A = \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix} \in M_2(\mathbb{R}). $$
The matrix $A$ has no eigenvalues over $\mathbb{R}$ but $A^2 = -I$ has the eigenvalue $-1$ of multiplicity two. This can also be analyzed but I'm not sure if it's worth the hustle to write down a general result.
A: Hints: 
You might want to consider something like the Jordan normal form $A = Q' J Q$ of $A$, for $p(A) = Q' p(J) Q$. 
Also: look at 
$$
A = \begin{bmatrix}
0 & 1 \\
1 & 0
\end{bmatrix}
$$
and the polynomial $p(x) = x^2$. 
The eigenstructures of $A$ and $I$ are very different, but those of $p(A)$ and $p(I)$ are identical, because $p(A) = p(I)$. So there may not be an obvious relationship when there are non-real eigevalues around. 
