# 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?

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$.
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)$$.