When matrices commute Original title: when animals attack.
2016: The short version is that matrices that commute with a fixed matrix $A$ must all be polynomials in $A,$ if and only if the characteristic polynomial of $A$ and the minimal polynomial coincide. Put another  way, if and only if each eigenvalue occurs in just one Jordan block. Worth recording the fact that the minimal polynomial of a square matrix does not change when the field of definition is extended.
Inspired by $$ $$ https://mathoverflow.net/questions/65738/when-matrix-multiplication-commutes  $$ $$ and $$ $$ http://www.imdb.com/title/tt0293702/ $$ $$
is it true that, when $$ A \in SL_n(\mathbf Z),$$
then all integral matrices that commute with $A$ are an integral (or at least rational) polynomial in $A$? I dimly recall proving this for a specific 3 by 3 $A$ that was all 0's and 1's, so calculations were easy. The use of the unit determinant is that $A^{-1}$ is an integral polynomial in $A$ by Cayley-Hamilton. The degree of the polynomial need be no larger than $n-1,$ also by Cayley-Hamilton.
EDIT: as both David Speyer and  Tommaso Centeleghe point out in comments below, the statement is true if all eigenvalues are distinct, probably false otherwise. People are smart. And quick. The point being to diagonalize $A$ over $\mathbb C$ and continue.
EDIT TOOO: it seems reasonable to conjecture that the full set of $A$ for which the statement is true is $ A \in SL_n(\mathbf Z)$ such that, should there be any eigenvalue(s) of multiplicity larger than one, all occurrences of that eigenvalue must fit into a single Jordan block. Richard would know. 
With or without commutativity, I once made a "multiplicative" function  out of
$$ f(x_0, x_1, \ldots, x_{n-1}) = \det (x_0 I + x_1 A + x_2 A^2 + \cdots + x_{n-1} A^{n-1}),   $$
amounting to a kind of fake norm form. The guy I asked about it laughed at me but said that's what I had.
I asked Manjul Bhargava about this: take the matrix $A,$ 3 by 3, to have rows
<0,1,0; 0,0,1; 1,1,1> which I think may actually have had determinant -1, never mind. Then the prime values I got from my fake norm form were all nonresidues mod 11 and all $x^2 + 11 y^2.$ I'm not sure about 2 itself. No proof but presumably a known sort of problem.
 A: There is a little room for repeat eigenvalues, as long as we have nontrivial Jordan blocks. For the following, if an integral square matrix commutes with $A_j,$ it is a (rational) polynomial in $A_j$: 
$$ A_2 \; = \;  
 \left(  \begin{array}{rr}
  1 & 1  \\\
   0  & 1  
\end{array} 
  \right)  ,
  $$
$$ A_3 \; = \;  
 \left(  \begin{array}{rrr}
  1 & 1 & 0 \\\
  0  & 1 & 1 \\\
  0 & 0  & 1  
\end{array} 
  \right)  ,
  $$
$$ A_4 \; = \;  
 \left(  \begin{array}{cccc}
 0 & -1 & 1 & 0 \\\
 1 & 0  & 0 & 1 \\\
 0 & 0 & 0  & -1  \\\ 
 0 & 0 & 1  & 0  
\end{array} 
  \right).
  $$
EDIT : it seems reasonable to conjecture that the full set of $A \in SL_n(\mathbb Z)$ for which the statement is true is $ A \in SL_n(\mathbb Z)$ such that, should there be any eigenvalue(s) of multiplicity larger than one, all occurrences of that eigenvalue must fit into a single Jordan block. Richard would know. 
EDIT, 20 November 2011: the conjecture above is true, and does not use integers, it is just about matrices over the complex numbers. This is Corollary 1 to Theorem 2, on page 222 of The theory of matrices, Volume 1 by Feliks Ruvimovich Gantmakher. It reads:

Corollary 1 to Theorem 2: All the
  matrices that are permutable with $A$
  can be expressed as polynomials in $A$
  if and only if $n_1=n,$ i.e. if all
  the elementary divisors of $A$ are
  coprime in pairs.

SO, the following two conditions, for a square matrix $M$ with real or complex entries, are equivalent:
(I)  All matrices that commute with $M$ can be written as a polynomial in $M.$
(II) The characteristic polynomial and the minimal polynomial of $M$ are the same.
A: (1) Let $A$ be a commutative ring, and let $M$ and $N$ be $A$-modules. If the natural morphism from $A$ to $\text{End}_A(M\oplus N)$ is surjective, then the annihilators of $M$ and $N$ are comaximal. 
Indeed, this comaximality is the condition for the projectors attached the given direct sum decomposition to be in the image. 
Assume now that $A$ is a principal ideal domain. Let $(G,+)$ be the Grothendieck group of the category $C$ of finitely generated torsion $A$-modules, and let $(H,\cdot)$ be the group of (nonzero) fractional ideals of $A$. 
There is a (clearly unique) morphism from $G$ to $H$ which maps $A/\mathfrak a$ to $\mathfrak a$. 
It is easy to see that the fractional ideal attached to $M\in C$ is in fact integral. Call it the characteristic ideal of $M$. Moreover we have in view of (1): 
(2) The natural morphism from $A$ to $\text{End}_A(M)$ is surjective, if and only if the characteristic ideal of $M$ coincides with the annihilator of $M$. 
Assume now that $A=K[X]$, where $K$ is a field and $X$ an indeterminate, and that $V$ is a finite dimensional $K$-vector space equipped with an endomorphism $a$. Then the characteristic ideal of $V$ is generated by the characteristic polynomial of $a$, and (1) and (2) imply: 

The characteristic polynomial of $a$ coincides with its minimal polynomial if and only if any endomorphism of $V$ commuting with $a$ is in $K[a]$. 

