Proof of Cayley-Hamilton using Krylov subspaces I came up with another proof of the Cayley-Hamilton Theorem.  Is this new?  The proof is by induction over the dimension of the underlying vector space.
Let $v \in \mathbb F^n \setminus \{0\}$.  Consider the Krylov subspaces
$$ K_j = \text{span} \{v, Av, \dots, A^{j-1} v\} .$$
Let $$j_0 = \min\{j \ge 1 : K_j = K_{j+1}\} .$$
Case 1: $j_0 < n$.  Then $K_{j_0}$ is an invariant subspace for $A$, so with respect to a basis whose first $j_0$ elements are in $K_{j_0}$, the matrix is a block upper triangular matrix.  Now the result follows by the inductive hypothesis on each of the diagonal blocks.
Case 2: $j_0 = n$.  Then $K_n = \mathbb F^n$, and $\{v, Av,\dots,A^{n-1}v\}$ is a basis of $\mathbb F^n$.  It follows that there exists
$a_0, a_1, \dots, a_{n-1} \in \mathbb F$ such that
$$ A^n v = -a_0 v - a_1 Av - a_2 A^2 v - \cdots - a_{n-1} A^{n-1} v .$$
That is, setting
$$p(\lambda) = \lambda^n + a_{n-1}\lambda^{n-1} + \cdots + a_0,$$ we have
$$ p(A) v = 0 .$$
For any vector $w \in \mathbb F^n$, we have that $w = q(A) v$ for some polynomial $q$.  Thus
$$ p(A) w = p(A) q(A) v = q(A) p(A) v = 0 .$$
Hence
$$ p(A) = 0 .$$
Finally with respect to the basis $\{v, Av,\dots,A^{n-1}v\}$, the matrix $A$ has the form of the companion matrix:
$$ \begin{bmatrix} 0 & 0 & 0 & \cdots & 0 & 0 & -a_0 \\
                   1 & 0 & 0 & \cdots & 0 & 0 & -a_1 \\
                   0 & 1 & 0 & \cdots & 0 & 0 & -a_2 \\
                   \vdots & \vdots & \vdots & & \vdots & \vdots & \vdots \\
                   0 & 0 & 0 & \cdots & 0 & 0 & -a_{n-3} \\
                   0 & 0 & 0 & \cdots & 1 & 0 & -a_{n-2} \\
                   0 & 0 & 0 & \cdots & 0 & 1 & -a_{n-1}
\end{bmatrix} ,$$
and it is well known that the characteristic polynomial of the companion matrix is given by $$ p(\lambda) = \lambda^n + a_{n-1}\lambda^{n-1} + \cdots + a_0. $$

For the record, I recall giving essentially the same proof in the last two paragraphs of this answer to the question about computing the minimal and characteristic polynomials of a companion matrix, explaining why it is useful to separately compute both directly, rather than to rely on Cayley-Hamilton to deduce the characteristic polynomial from the more easily computed minimal polynomial (which turns out to already have degree$~n$, the size of the companion matrix).
