When is an algebra of commuting matrices (contained in one) generated by a single matrix?

Consider the subalgebra of $M_{2n}(k)$ spanned by the matrices of the form $\left(\begin{smallmatrix}0&A\\0&0\end{smallmatrix}\right)$ (all blocks are $n\times n$) together with the identity, which is commutative. Its dimension is larger than $2n$ when $n$ is sufficiently large, so it is not generated by a single matrix.

For symmetric matrices over the reals, the answer is yes: if $A$ and $B$ commute, then they can be simultaneously diagonalized. That is to say, there exists an orthogonal matrix $U$ ($U^TU = I$) such that $U^TAU$ and $U^TBU$ are both diagonal. It follows that for any diagonal matrix $D$ with distinct diagonal entries, both $A$ and $B$ are polynomials in $C = UDU^T$.

In general it is instructive, and loses no generality, to assume that $A$ is in a normal (Jordan, Smith, etc.) form. Over a field, for example, the dimension of the space of polynomials in $A$ is the same as the degree of the minimal polynomial of $A$, which is the sum, over all eigenvalues $\lambda$, of the size of the largest Jordan block for $\lambda$ in the Jordan normal form of $A$ over the algebraic closure of the field. It's not too hard to verify that every matrix commuting with $A$ is a polynomial in $A$ if and only if the minimal polynomial is the characteristic polynomial, that is if every eigenvalue has a single Jordan block (as happens automatically for example if there are $n$ distinct eigenvalues).

I can't remember the precise statement of something that surprised me, some unsolved problem related to the dimension of a commuting set in terms of Jordan block sizes. Someone please comment if you are familiar with this open problem and can state it precisely.

The open problem that surprised me was on the lower bound of dimensions of maximal commutative subalgebras of $M_n(\mathbf C)$. A maximal commutative sublagebra of $M_n(\mathbf C)$ can have dimension strictly lass than $n$. See for example Courter's article, where he gives a 13 dimensional maximal commutative subalgebra of $M_{14}(\mathbf C)$. I think, In general the problem of finding lower bound for the dimension of maximal commutative subalgebras in $M_n(\mathbf C)$ is still open.