Proving that $\dim(\mathrm{span}({I_n,A,A^2,...})) \leq n$ Let $A$ be an $n\times n$ matrix. Prove that $\dim(\mathrm{span}({I_n,A,A^2,...})) ≤ n$
I'm at a total loss here...
Can someone help me get started?

The following observations suffice to prove the statement:


*

*A power $A^k$ is in the span of lower powers $A^0,\ldots,A^{k-1}$ if and only if there exists a (monic) polynomial$~P$ of degree$~k$ with $P[A]=0$.

*If this happens for some $k=m$, it also happens for all $k>m$, so that by an immediate induction argument, $\operatorname{span}(A^0,\ldots,A^{m-1})$ contains all powers of$~A$ (and of course it has dimension${}\leq m$).

*There exists a monic polynomial$~P$ of degree${}\leq n$ with $P[A]=0$.


Point 1. is fairly obvious; it suffices to consider an equation expressing $A^k$ as linear combination of $A^0,\ldots,A^{k-1}$, and to bring all its terms to the same side of the equation as$~A^k$. Point 2. is also easy, since it suffices to multiply the polynomial $P$ by a power$~X^d$ to raise is degree; the result still annihilates$~A$, since $(X^dP)[A]=A^d\circ (P[A])=0$ by linearity of$~A$. (Alternatively one could argue for the remainder $R$ of $X^k$ after division by$~P$ that $A^k=R[A]\in\operatorname{span}(A^0,\ldots,A^{m-1})$, since $\deg R<m$.) For point 3. the Cayley-Hamilton theorem says the characteristic polynomial $P=\chi_A$, which has degree $n$, can be chosen.
Added.
When using Cayley-Hamilton, I always wonder if one could also do it by more elementary means (because the proof of C-H is somewhat subtle). For point 3. this is is in fact the case.
One can use strong induction on the dimension. The inductive hypothesis takes the following concrete form: for any  $A$-stable subspace $V$, there exists a monic polynomial $P\in K[X]$ with $\deg P\leq\dim V$ such that $V\subseteq\ker(P[A])$. By expressing the restriction of $A$ to$~V$ on a basis, this is just point 3. for that restriction. So assume this result holds for any proper subspace. If $n=0$ one can take $P=1$, so also assume $n>0$ and choose a nonzero vector $v\in K^n$. The $n+1$ vectors $v,Av,A^2v,\ldots,A^nv$ are certainly linearly dependent, so one can take $d$ minimal such that  $v,Av,A^2v,\ldots,A^dv$ are linearly dependent. Then $A^dv$ is a linear combination of the preceding vectors, and this gives a polynomial $R$ of degree$~d$ such that $R[A]v=0$. But $\ker(R[A])$ is $A$-stable so $v,Av,A^2v,\ldots,A^{d-1}v\in\ker(R[A])$, and since these vectors are linearly independent, one obtains $\dim\ker(R[A])\geq d$. Putting $V=\operatorname{Im}(R[A])$ the rank-nuullity theorem gives $\dim V\leq n-d$, and since $V$ is $A$-stable, the induction hypothesis gives a polynomial $Q$ with $\deg Q\leq n-d$ such that $V\subseteq\ker(Q[A])$. The latter means that $0=Q[A]\circ R[A]=(QR)[A]$; then taking $P=QR$ works, since one gets $\deg P=\deg Q+\deg R\leq(n-d)+d=n$.
