Q:

Can commuting matrices $X,Y$ always be written as polynomials of some matrix $A$?

Consider square matrices over a field $K$. I don't think additional assumptions about $K$ like algebraically closed or characteristic $0$ are pertinent, but feel free to make them for comfort. For any such matrix $A$, the set $K[A]$ of polynomials in $A$ is a commutative subalgebra of $M_n(K)$; the question is whether for any pair of commuting matrices $X,Y$ at least one such commutative subalgebra can be found that contains both $X$ and $Y$.
I was asking myself this in connection with frequently recurring requests to completely characterise commuting pairs of matrices, like this one. While providing a useful characterisation seems impossible, a positive anwer to the current question would at least provide some answer.
Note that in many rather likely situations one can in fact take $A$ to be one of the matrices $X,Y$, for instance when one of the matrices has distinct eigenvalues, or more generally if its minimal polynomial has degree $n$ (so coincides with the characteristic polynomial). However this is not always possible, as can be easily seen for instance for diagonal matrices $X=\operatorname{diag}(0,0,1)$ and $Y=\operatorname{diag}(0,1,1)$. However in that case both will be polynomials in $A=\operatorname{diag}(x,y,z)$ for any distinct values $x,y,z$ (then $K[A]$ consists of all diagonal matrices); although in the example in this answer the matrices are not both diagonalisable, an appropriate $A$ can be found there as well. 
I thought for some time that any maximal commutative subalgebra of $M_n(K)$ was of the form $K[A]$ (which would imply a positive answer) for some $A$ with minimal polynomial of degree$~n$, and that a positive answer to my question was in fact instrumental in proving this. However I was wrong on both counts: there exist (for $n\geq 4$) commutative subalgebras of dimension${}>n$ (whereas $\dim_KK[A]\leq n$ for all $A\in M_n(K)$) as shown in this MathOverflow answer, and I was forced to correct an anwer I gave here in the light of this; however it seems (at least in the cases I looked at) that many (all?) pairs of matrices $X,Y$ in such a subalgebra still admit a matrix $A$ (which in general is not in the subalgebra) such that $X,Y\in K[A]$. This indicates that a positive answer to my question would not contradict the existence of such large commutative subalgebras: it would just mean that to obtain a maximal dimensional subalgebra containing $X,Y$ one should in general avoid throwing in an $A$ with $X,Y\in K[A]$. I do think these large subalgebras easily show that my question but for three commuting matrices has a negative answer.
Finally I note that this other answer to the cited MO question mentions a result by Gerstenhaber that the dimension of the subalgebra generated two commuting matrices in $M_n(K)$ cannot exceed$~n$. This unfortunately does not settle my question (if $X,Y$ would generate a subalgebra of dimension${}>n$, it would have proved a negative answer); it just might be that the mentioned result is true because of the existence of $A$ (I don't have access to a proof right now, but given the formulation it seems unlikely that it was done this way).
OK, I've tried to build up the suspense. Honesty demands that I say that I do know the answer to my question, since a colleague of mine provided a convincing one. I will however not give this answer right away, but post it once there has been some time for gathering answers here; who knows somebody will prove a different answer than the one I have (heaven forbid), or at least give the same answer with a different justification.

A:

As promised I will answer my own question. The answer is negative, it can happen that $X$ and $Y$ cannot be written as polynomials of any one matrix $A\in M_n(K)$.
Following the comment by Martin Brandenburg, this can even happen when $X$ and $Y$ are both diagonal, if the field $K$ is too small. Indeed if $K$ is a finite field of $q$ elements then for any diagonalisable matrix $A$ one has $\dim K[A]\leq q$ because $q$ limits the degree of split polynomials without multiple roots, and the minimal polynomial of $A$ must be of this kind. This means that when $n>q$ the dimension $n$ of the subalgebra $D$ of all diagonal matrices is too large for it to be of the form $K[A]$ for one of its members. And as long as $n\leq q^2$ one can find diagonal matrices $X,Y$ that generate all of $D$, while ensuring that all matrices$~A$ commuting with both $X$ and $Y$ must be diagonal; this excludes finding such $A$ with $X,Y\in K[A]$. Indeed one can arbitrarily label each of the $n$ standard basis vectors with distinct elements of $K\times K$, and define $X,Y$ so that each such basis vector is a common eigenvector, with respective eigenvalues given by the two components of the label; one then easily realises each projection on the $1$-dimensional space generated by one of the standard basis vectors as a polynomial in $X,Y$, forcing any matrix commuting with both $X$ and $Y$ (and therefore with these projections) to be diagonal.
But for examples valid in arbitrary field, it is better to focus attention on nilpotent matrices, avoiding the "regular" ones with minimal polynomial $X^n$ (and hence with a single Jordan block). The counterexample that I had in mind was the pair of $4\times4$ matrices each of Jordan type $(2,2)$:
$$
  X=\begin{pmatrix}0&1&0&0\\0&0&0&0\\0&0&0&1\\0&0&0&0\end{pmatrix}
,\qquad
  Y=\begin{pmatrix}0&0&1&0\\0&0&0&1\\0&0&0&0\\0&0&0&0\end{pmatrix}
,\qquad \text{which have }
 XY=YX=\begin{pmatrix}0&0&0&1\\0&0&0&0\\0&0&0&0\\0&0&0&0\end{pmatrix}
$$
while $X^2=Y^2=0$. Then the algebra $K[X,Y]$ has dimension $4$, and is contained in the subalgebra of upper triangular matrices $A$ with identical diagonal entries and also $A_{2,3}=0$. For any $A$ in this subalgebra, and therefore in particular for $A\in K[X,Y]$, one has $\dim K[A]\leq3$, since $(A-\lambda I)^3=0$ where $\lambda$ is the common diagonal entry of $A$; in particular $K[A]\not\supseteq K[X,Y]$ for such$~A$. But one also has $\dim K[A]\leq4$ for any $A\in M_4(K)$, and this shows that one cannot have $K[A]\supseteq K[X,Y]$ unless $A\in K[X,Y]$, and one therefore cannot have it at all.
The answer in the MO thread indicated in the other answer indicates that there are counterexamples even for $n=3$; indeed it suffices to strip either the first row and column or the last row and column off the matrices $X,Y$ given above. The argument is similar but even simpler for them. The resulting matrices generate the full subalgebra of matrices of the form
$$
  \begin{pmatrix}\lambda&a&b\\0&\lambda&0\\0&0&\lambda \end{pmatrix}
\quad \text{respectively of those of form}\quad
 \begin{pmatrix}\lambda&0&b\\0&\lambda&a\\0&0&\lambda \end{pmatrix};
$$
having dimension $3$ it can only be contained in $K[A]$ if $A$ is in the subalgebra, but then the minimal polynomial of $A$ has degree at most $2$ so the algebra it generates cannot be all of that subalgebra.
These two subalgebras are analogues of the commutative subalgebra of dimension${}>n$ that I mentioned in the question, but for the case $n=3$ where its dimension is only equal to $n$. If had bothered to look at this more modest case rather than go directly for the "excessive" subalgebra for $n\geq4$ right away, then I might have found this example myself; I guess one should never neglect the small cases.

A:

The answer is given in the accepted answer of MO/34314. Don't klick when you want to keep the suspense.

