proof that every finite matrix has an annihilating polynomial I don't quite understand the proof my notes gave me.
Dimension of $n$ by $n$ matrix is $n^2$. Hence if $k \geq n^2$ then $\mathbf{ \{ I, A, A^2, ..., A^k \} }$ is linearly  dependent. So, there exist scalars $a_i$ not all zero such that
$$a_k A^k + \cdots + a_0 I = 0$$
$f(x) = a_k x^k + \cdots + a_0$ is an annihilating polynomial. 

I don't understand the bold bit. How do we know that $A, A^2, ...$ are all different? Surely there are matrices which give identity when raised to power of 2,3, etc right?
Thanks.
 A: Take the set $\{I,A,\cdots,A^k\}$ with $k\gt n^2$ if any two of those powers of $A$ are equal say $A^p=A^q$ with $p\neq q$ then $X^p-X^q$ is an annihilating polynomial of $A$. So we can assume the elements of the set all different. But in any vector space of dimension $n^2$, elements of any set of more than $n^2$ distinct elements are linearly dependent.
There is no need to invoke minimal polynomial or characteristic polynomial or Cayley-Hamilton theorem as in the comments.
A: To work with the proof given to you already, the vector space of $n \times n$ matrices has dimension $n^2$ (see if you can think of a basis!). So, if you collect more than $n^2$ matrices, then the resulting set cannot be linearly independent (if it could, then it could be extended to a basis that's larger than $n^2$). Hence, assuming that the matrices $I, A, A^2, \ldots, A^{n^2}$ are pairwise distinct, since there are $n^2 + 1$ of them, they must be a linearly dependent set, meaning there exist scalars $a_0, a_1, \ldots, a_{n^2}$, not all $0$, such that,
$$a_0 I + a_1 A + a_2 A^2 + \ldots a_{n^2} A^{n^2} = 0.$$
This is such a polynomial!
Now, notice that I assumed that all the matrix powers were different! If two of them were the same (by convention, $I = A^0$), then we would have $A^p = A^q$ for some $p, q$. But then $A^p - A^q = 0$, so the polynomial $x^p - x^q$ is one such polynomial that we are looking for.
A: Every finite matrix satisfies its CHARACTERISTIC EQUATION by Cayley - Hamilton Theorem. So atleast there is a polynomial $p(A) = 0$.
In your case according to your notes : if your matrix is $ n \times n $, it is an element of a vector space isomorphic to $\mathbb{R}^{n^2}$. So any set of elements $k > n^2$ from this vector space must be linearly dependent. Hence your proof holds.   
A: In answer to the specific questions raised at the end of this post:  (i.)  we do not in fact know that the $A^k$ are all different, and it doesn't matter; what matters is that in a vector space of dimension $m$ ($= n^2$ in the present case), any set of $l > m$ vectors must exhibit a linear dependence; this is in effect the definition of dimension; and (ii.), yes, there are always matrices such that $A^k = I$ with $k \le n^2$ and, like item (i), this is not at all in conflict with the main premise, that every $A$ has an annihilating 
polynomial of degree $\le n^2$; it merely asserts that one such polynomial will in fact be $x^k - 1$.  
Of course, Cayley-Hamilton affirms a much stronger statement, that the annihilating polynomial is indeed of degree at most $n$; but the price paid for such strength is a substantially more complex proof.  And as far as the economies of mathematical truths and proofs are concerned, I would say it is a price well paid; but the present result is well worth the bargain.
