Let $A,B \in GL(n,\mathbb C)$ be two diagonalizable matrices such that $AB=BA$ ; then does there exist a polynomial $p(x)$ of degree at most $n$ with complex-coefficients , such that $p(A)=B$ ?
UPDATE : As is apparent from Daniel's comment ; the claim above is false ; but now it is worth while to ask the following ; is it true that atleast one of $A$ or $B$ can be expressed as a polynomial , with complex co-efficients ( of degree at most $n$ ) , of the other matrix ?
On
By the fact that $A,B$ be two diagonalizable matrices such that $AB=BA$, there exists $P\in GL(n, \mathbb{C})$ such that $PAP^{-1}=diag(\lambda_{1}, \lambda_{2}, \ldots, \lambda_{n})$, $PBP^{-1}=diag(\lambda'_{1}, \lambda'_{2}, \ldots, \lambda'_{n})$. If $p(x) \in \mathbb{C}[x]$ such that $p(A)=B$, i.e. $diag(p(\lambda_{1}), p(\lambda_{2}), \ldots, p(\lambda_{n}))=diag(\lambda'_{1}, \lambda'_{2}, \ldots, \lambda'_{n})$. That is, whether $\exists$ $a_0, a_1, \ldots, a_n$ satisfy \begin{align*} a_0 + a_1 \lambda_{i} + a_2 \lambda^{2}_{i} + \cdots + a_n \lambda^{n}_{i} = \lambda'_{i}, \end{align*} where $1 \leq i \leq n$. If $\lambda_{i} \neq \lambda_{j}$, $i\neq j$, then there exist $a_0, a_1, \ldots, a_n$ such that $p(x)=\sum_{j=0}^{n}a_{j}x^{j}$. (hit: Vandermonde determinant) I only know that these.
On
Invertibility of the matrices is completely irrelevant here - you can make a diagonalizable matrix invertible by adding an appropriate scalar matrix, and that doesn't affect which matrices are polynomials in that matrix.
The key concept is the following: For $C$ a diagonalizable matrix, let $\lambda_1, \ldots, \lambda_k$ be the eigenvalues. Then $$\pi_i := \dfrac{(C-\lambda_1 I)\cdots(C-\lambda_{i-1}I)(C-\lambda_{i+1}I)\cdots(C-\lambda_kI)}{(\lambda_i-\lambda_1)\cdots(\lambda_i-\lambda_{i-1})(\lambda_i-\lambda_{i+1})\cdots(\lambda_i-\lambda_k)}$$ defines the projection map onto the $\lambda_i$-eigenspace of $C$.
We have $\pi_i^2 = \pi_i$ for all $i$, and $\pi_i \pi_j = 0$ when $i \neq j$. It is common to abbreviate these two statements by saying $\pi_i \pi_j = \delta_{i,j} \pi_i$ for $i, j \in \{1, 2, \ldots, k\}$, where $\delta_{i,j}$ is the Kronecker delta function. From this, the fact that each $\pi_i$ is a polynomial in $C$, and the fact that $C = \lambda_1 \pi_1 + \cdots + \lambda_k \pi_k$, it follows that polynomials in $C$ form the same class of matrices as linear combinations of $\pi_1, \ldots, \pi_k$. It follows that the polynomials in $C$ are precisely the diagonalizable matrices whose eigenspaces are direct sums of eigenspaces of $C$.
Now from this perspective, you should be able to see that all bing's counterexample does is simply give a pair of matrices whose eigenspaces are not direct sums of one another.
Finally, given commuting matrices $A$ and $B$ that are both diagonalizable, we will see how to get a matrix $C$ so that both $A$ and $B$ are polynomials in $C$: let $\pi_1, \ldots, \pi_\ell$ be the projection maps onto their simultaneous eigenspaces. These can be obtained as polynomials in $A$ and $B$ in a similar manner to the above. Then for any selection of $k$ distinct scalars $\lambda_1, \ldots, \lambda_\ell$, the matrix $C := \lambda_1 \pi_1 + \cdots + \lambda_\ell \pi_\ell$ fits the bill.
On
In general, the answer is no as shown by Daniel. However, if the eigenvalues of $A$ are distinct then the answer is yes. Choosing a basis of simultaneous eigenvectors for $A$ and $B$, we have $Av_i = \lambda_i v_i$ and $Bv_i = \mu_i v_i$ where $\lambda_i \neq \lambda_j$ for $1 \leq i \leq n$. Letting $p(x)$ be an interpolation polynomial of degree that satisfies $p(\lambda_i) = \mu_i$ for $1 \leq i \leq n$ we have $p(A)v_i = p(\lambda_i) v_i = \mu_i v_i = B v_i$ so $p(A) = B$.
Similarly, even if the eigenvalues of $A$ and $B$ are not distinct, you can arbitrary choose $n$ distinct complex numbers $\sigma_i$ and define $C$ by $Cv_i = \sigma_i v_i$. Then by choosing appropriate interpolation polynomials $p,g$ you can see that $A = p(C)$ and $B = g(C)$.
No. Here is a counter-example, let $A=\begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{bmatrix}$, $B=\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \\ \end{bmatrix}$. If there exists a polynomial $p(x) \in \mathbb{C}[x]$ such that $p(A)=B$, then $p(A)=p(0)Id_3+(p(1)-p(0))A$, where $Id_3$ is the $3 \times 3$ identity matrix. (Notice $A$ is an idempotent matrix). This is a contradiction.