Polynomials and matrices. Given a polynomial $p(x)\in\Bbb R[x]$ of degree $n$ how many different matrices $A_1,\dots,A_k\in \Bbb R^{n\times n}$ can we have such that $$p(A_1)=\dots= p(A_k)=0$$ on the condition the if the $$\operatorname{vec}(A_1),\dots,\operatorname{vec}(A_k)$$ are independent in $\Bbb R^{n^2}$ ($0\leq k\leq n^2$ holds)?
 A: Ignore the trivial cases $n=1$ or $p=0$. Suppose $n\ge2$ and $p$ is a monic non-constant polynomial (actually, it doesn't matter whether the degree of $p$ is $n$ or not). The answer is then $n^2-1$ when all roots of $p(x)=0$ are purely imaginary (including zero roots), or $n^2$ when $p(x)=0$ has a root with nonzero real part.
Let us first consider the following four possibilities:


*

*$p(x)=0$ has only one real (and repeated) root $\lambda$. Then $p(A)=0$ whenever $A$ is similar to $A_0=\pmatrix{\lambda&1\\ 0&\lambda}\oplus (\lambda I_{n-2})$ (there may be other matrices annihilated by $p$, but they are irrelevant here).

*$p(x)=0$ has at least two different real roots $\lambda_1$ and $\lambda_2$. Then $p(A)=0$ whenever $A$ is similar to $A_0=\pmatrix{\lambda_1&1\\ 0&\lambda_2}\oplus (\lambda_2 I_{n-2})$.

*$p(x)=0$ has a conjugate pair of complex roots $\cos\theta\pm i\sin\theta$ and $n$ is even. Then $p(A)=0$ whenever $A$ is similar to $A_0=R\oplus\cdots\oplus R$, where $R=\pmatrix{\cos\theta&-\sin\theta\\ \sin\theta&\cos\theta}$.

*$p(x)=0$ has a conjugate pair of complex roots $\cos\theta\pm i\sin\theta$ and a real root $\lambda$. Then $p(A)=0$ whenever $A$ is similar to $A_0=R\oplus (\lambda I_{n-2})$.


Note that in each of the above four cases, the real linear span of the similarity orbit of $A_0$ is the whole matrix space $\mathbb R^{n\times n}$. In fact, as $a_{12}\ne a_{21}$, when $\epsilon>0$ is small and $D_\epsilon=\operatorname{diag}(\epsilon,1,\ldots,1)$, the difference $D_\epsilon^{-1}A_0D_\epsilon-A_0$ is the direct sum of a nonzero anti-diagonal $2\times2$ matrix (with unequal anti-diagonal entries) and a zero sub-block. Therefore, one can obtain $J=\pmatrix{0&1\\ 0&0}\oplus0$ as some linear combination of the form $p(D_\epsilon^{-1}A_0D_\epsilon-A_0)+q(D_\delta^{-1}A_0D_\delta-A_0)$. It follows that the linear span of the similarity orbit of $J$ is the $(n^2-1)$-dimensional subspace of all traceless matrices. This means there are at least $n^2-1$ linearly independent matrices in the similarity orbit of $A_0$.
Now, if all roots of $p(x)=0$ are purely imaginary, all real matrices annihilated by $p$ must be traceless. Hence $n^2-1$ is the answer in this case. However, if $p(x)=0$ has a root with nonzero real part, we can always find a real matrix $A_1$ such that $p(A_1)=0$ but the trace of $A_1$ is nonzero. Hence the answer is $n^2$ in this case.
