<s>[INST] For $\Bbb K^{n \times n}$ matrices $A$ and $B$, $\exists p[p(A)=B] \implies \exists p[p(B)=A]$? For $\Bbb K^{n \times n}$ matrices $A$ and $B$, is it true that if there exists a matrix polynomial $p$ such that $p(A)=B$, then there exists another matrix polynomial $p$ (not necessarily the same) such that $p(B) = A$?
My attempt
Let $B = \displaystyle \sum_{k=0}^{n-1} a_k A^k$, where $a_k \in \Bbb K$.
From the Cayley-Hamilton theorem, there exists a polynomial $p$ of degree $n$ such that $p(A) = O$, so $A^m$ where $m \ge n$ can be expressed as linear combination of $\left\{ A^k \ | \ 0 \le k < n\right\}$.
So, we can express $B^m = \displaystyle \sum_{k=0}^{n-1} a_{mk} A^k$, where $a_{mk} \in \Bbb K$.
If $\{I, A, A^2, \cdots, A^{n-1}\}$ form a basis, then we can express a polynomial in $B$, $\displaystyle \sum_{k=0}^{n-1} b_k B^k$, as:
$$\begin{pmatrix}
a_{00} & a_{10} & a_{20} & \cdots & a_{(n-1)0} \\
a_{01} & a_{11} & a_{21} & \cdots & a_{(n-1)1} \\
a_{02} & a_{12} & a_{22} & \cdots & a_{(n-1)2} \\
\vdots & \vdots & \vdots & \vdots & \vdots \\
a_{0(n-1)} & a_{1(n-1)} & a_{2(n-1)} & \cdots & a_{(n-1)(n-1)} \\
\end{pmatrix}
\begin{pmatrix}
b_0 \\ b_1 \\ b_2 \\ \vdots \\ b_{n-1}
\end{pmatrix}$$
Since we want the polynomial to equal $A$, we would need to solve:
$$\begin{pmatrix}
a_{00} & a_{10} & a_{20} & \cdots & a_{(n-1)0} \\
a_{01} & a_{11} & a_{21} & \cdots & a_{(n-1)1} \\
a_{02} & a_{12} & a_{22} & \cdots & a_{(n-1)2} \\
\vdots & \vdots & \vdots & \vdots & \vdots \\
a_{0(n-1)} & a_{1(n-1)} & a_{2(n-1)} & \cdots & a_{(n-1)(n-1)} \\
\end{pmatrix}
\begin{pmatrix}
b_0 \\ b_1 \\ b_2 \\ \vdots \\ b_{n-1}
\end{pmatrix}
=
\begin{pmatrix}
0 \\ 1 \\ 0 \\ \vdots \\ 0
\end{pmatrix}$$

Until now I have transformed the problem into a problem in linear algebra, but is utterly useless. Firstly, $\{A^k \ | \ 0 \le k < n\}$ may not even be linearly independent.
 [/INST] In a word, no. Let
$A=\pmatrix{1&0\\0&-1}$ and $p(X)=X^2$.
Then
$$B=p(A)=\pmatrix{1&0\\0&1}.$$
How can there be a polynomial with $q(B)=A$?
</s>