Showing that the minimal polynomial of an $n \times n$ matrix has degree at most $n$ without using the Cayley-Hamilton Theorem Let $A$ be an $n \times n$ matrix over a field $k$. Or, more generally, an endomorphism of an $n$-dimensional $k$-vector space. Then the minimal polynomial $p_A(t)$, of $A$, has degree at most $n$. The usual way to show this is as a corollary of Cayley-Hamilton:

If $\Phi_A(t) = \det(tI - A)$ then $\Phi_A(A) = 0$ and $\deg \Phi_A = n$. Since $p_A \mid \Phi_A$, it follows that $\deg p_A \le n$.

One can also prove this using the structure theorem:

The $k[t]$-module $V = k^n$, with action given by $t \cdot v = Av$, decomposes as a direct sum $$V \cong \bigoplus_{i = 1}^r k[t]/(q_i), $$ where $0 \ne q_1 \mid q_2 \mid \dots \mid q_r = p_A$. Taking dimensions we have $$ n = \sum_{i = 1}^r \deg q_i. $$ Therefore $\deg p_A = \deg q_r \le n$.

It is clear that we do not need the full strength of the structure theorem; all we need to do is show that there is a module-embedding $$ k[t]/(p_A) \hookrightarrow V. $$ This is shown in the course of proving the structure theorem.
Question:
Can we show that $\deg p_A \le \dim V$ without using Cayley-Hamilton or the the structure theorem? In particular, are there any easier proofs of this fact than as a corollary of Cayley-Hamilton?
 A: Let $v$ be a nonzero vector in $V=k^n$. Let $m$ be the least positive integer
with $A^mv$ linearly dependent on $v$, $Av,\ldots, A^{m-1}v$. Then there is a monic $f$ of degree $m$ with $f(A)v=0$. Therefore $f(A)A^jv=A^jf(A)v=0$ for $0\le j\le m - 1$ so that $f(A)$ has nullity $\ge m$. Let $W=f(A)V$. The dimension of $W$ is
$\le n-m$. Then $A$ acts on $W$ and inductively $g(A)W=0$ for some
monic polynomial $g$ of degree $\le n-m$. Therefore $gf$ has degree $\le n$
and annihilates $V$.
A: The most elementary way to prove this is given in the other answer, and can be summarised as follows: (1) for every vector $v$ and for the minimal monic polynomial $P$ such that $P[T](v)=0$ one has $\deg(P)\leq\dim(\ker(P[T]))$ (since that kernel contains the cyclic submodule generated by $v$), and (2) since the remaining factor $Q=\mu/P$ of the minimal polynomial$~\mu$ must annihilate precisely the image$~W$ of $P[T]$, we are reduced to showing that $\deg(Q)\leq\dim(W)$, which induction on the dimension conveniently does for us.
Just for reference I would like to mention another another possible approach, by reducing the question to one in a simplified situation, where it becomes fairly obvious. Since the minimal polynomial$~\mu$ does not change if we extend scalars to a larger field (i.e., consider the matrix of $T$ as one over a larger field), we may assume that $\mu$ factors into factors of the form $(X-\lambda)^m$ that are mutually relatively prime. The space then factors (canonically) into a direct sum of the kernels of the corresponding endomorphisms $(T-\lambda I)^m$ (the generalised eigenspaces), and it suffices to prove the result for each summand separately (as the product of the minimal polynomials of the restrictions of $T$ to the summands gives the global minimal polynomial$~\mu$). Since by definition $T'-\lambda I$ is nilpotent for such a restriction$~T'$, we are reduced to showing:

For a nilpotent operator$~N$ on a finite dimensional vectors space$~V$, its order$~m$ of nilpotency does not exceed $\dim(V)$.

This is fairly obvious, for instance because the subspaces $\ker(N^i)$ for $i=0,1,\ldots,m$ form a strictly increasing chain in $V$ (the successive images by $N$ of a vector of maximal lifetime leave these subspaces one by one). More is in fact true: the sequence of natural numbers $\dim(\ker(N^{i+1})/\ker(N^i))$ for $i=0,1,2,\ldots$ is weakly decreasing, which implies it reaches $0$ for the first time when $i=m$. To prove this, show that $T$ induces an injective linear map $\ker(N^{i+2})/\ker(N^{i+1})\to\ker(N^{i+1})/\ker(N^i)$.
