Suppose $\{v,Av,\cdots,A^{n-1}v\}$ is linearly independent. Prove that if $B$ is any matrix which commutes with $A$, then $B$ is a polynomial in $A$. Question: Let $A$ be an $n\times n$ square matrix and $v$ a column vector.  Suppose $\{v,Av,\cdots,A^{n-1}v\}$ is linearly independent.  Prove that if $B$ is any matrix which commutes with $A$, then $B$ is a polynomial in $A$.
Thoughts: Let $A$ be $n\times n$.  Wouldn't the matricies that commute with $A$ be a subspace of $\{v,Av,\cdots,A^{n-1}v\}$ (not sure how to formally prove this)?  And since $\{v,Av,\cdots,A^{n-1}v\}$ is linearly independent, then if $B$ were a polynomial in $A$, it would have degree $\leq n-1$, but I am a bit lost in seeing the details of the proof.  Any help is greatly appreciated!  Also, this is not a homework problem of mine, I have just been recently going over some old linear algebra stuff, and I just want to make sure I am seeing the details to better understand some of this stuff :)
 A: I'm admittedly slightly rusty (so do shout if this is wrong!) but I think it should go something like this, noting that $\lbrace v, Av,\ldots, A^{n-1}v\rbrace$ is a basis of what I'm going to take to be $\mathbb{R}^{n}$:
Clearly for any $x\in\mathbb{R}^{n}$ one can express $x$ in the basis $\lbrace v, Av,\ldots, A^{n-1}v\rbrace$ as
$$ x = \lambda_{0}v + \lambda_{1}Av + \cdots + \lambda_{n-1}A^{n-1}v $$
for some $\lambda_{j}\in \mathbb{R}$.
Now,
$$Bx = B(\lambda_{0}v + \lambda_{1}Av + \cdots + \lambda_{n-1}A^{n-1}v)= (\lambda_{0} + \lambda_{1}A + \cdots + \lambda_{n-1}A^{n-1})Bv$$
since $B$ commutes with $A$.
But $Bv$ is expressible as
$$ Bv = \mu_{0}v + \mu_{1}Av + \cdots + \mu_{n-1}A^{n-1}v $$
in the basis $\lbrace v, Av,\ldots, A^{n-1}v\rbrace$ for some $\mu_{j}\in \mathbb{R}$ and so one has that
$$Bx = (\lambda_{0} + \lambda_{1}A + \cdots + \lambda_{n-1}A^{n-1})(\mu_{0} + \mu_{1}A + \cdots + \mu_{n-1}A^{n-1})v$$
Noting that $A$ commutes with itself
$$Bx = (\mu_{0} + \mu_{1}A + \cdots + \mu_{n-1}A^{n-1})(\lambda_{0} + \lambda_{1}A + \cdots + \lambda_{n-1}A^{n-1})v = (\mu_{0} + \mu_{1}A + \cdots + \mu_{n-1}A^{n-1})x$$
And hence $B=\mu_{0} + \mu_{1}A + \cdots + \mu_{n-1}A^{n-1}$, and hence is a polynomial in $A$.
Of course you are right about the degree of $B$ being $\leq n-1$ as $A^{n}$ is expressible as a polynomial in $A$ of degree $\leq n-1$, and so on for $A^{n+k}$.
A: Here is another approach that uses the following fact.
Let $A,B\in\mathbb{R}^{n\times n}$ and $\{u_1,...,u_n\}$ a linearly independent set $\mathbb{R}^n$. If $Au_j=Bu_j$  for all $j$, then $A=B$.
The proof of above fact is quite simple; just show $Ax=Bx$ for an arbitrary $x\in \mathbb{R}^n$ by writing $x$ as a linear combination of the vectors in the provided basis.
To prove your statement, first note $\{v,Av,...,A^{n-1}v\}$ forms a basis for $\mathbb{R}^n$ so we can write $$Bv=c_0+c_1Av+\dots + c_{n-1}A^{n-1}v$$ for some $c_0,\ldots,c_{n-1}\in \mathbb{R}$. Define $P\in \mathbb{R}^{n\times n}$ by $$P=c_0I+c_1A+\dots +c_{n-1}A^{n-1}$$
Obviously $Bv=Pv$ by construction of $P$. Because $A,B$ commute, we have for any $j=1,...,n-1$ that $$\begin{eqnarray*}B(A^jv) &=& A^j(Bv) \\ &=& A^j\Big[c_0v+c_1Av+\dots + c_{n-1}A^{n-1}v\Big] \\ &=& c_0 A^j v + c_1 A^{j+1}v + \ldots + c_{n-1}A^{n+j-1}v \\&=& \Big[c_0I+c_1A+\dots +c_{n-1}A^{n-1}\Big](A^jv) \\ &=&P(A^jv) \end{eqnarray*}$$ Hence $B=P$.
