For context, one of the homework problems given in my linear algebra classes is this:
Given $0 \neq A \in M_n(\mathbb{C})$, prove there is a $k \in \mathbb{N}$ and a monic polynomial $m_A$ of degree $k$ such that $m_A(A) = 0$ and if $q \neq 0$ is a polynomial and $q(A) = 0$, then the degree of $q$ is at least $k$.
They left this as a hint:
[Suggestion: Explain why the system of vectors $I, A, A^2, . . . , A^{n^2 + 1}$ is dependent in $M_n(\mathbb{C})$. Conclude the set $$S = \{m \in \mathbb{N}^+ : I, A, A^2, . . . , A^m\text{ is dependent}\}$$ is not empty and thus has a smallest element, say $k$. Proceed.]
I have barely gained any headway with this proof, since I'm already stuck at the first part of the hint. To show that the set of vectors $\{I, A, A^2, . . . , A^{n^2 + 1}\}$ is dependent in $M_n(\mathbb{C})$, I have tried constructing the following equation $$\alpha_0 I + \alpha_1 A + \alpha_2 A^2 + \ldots + \alpha_{n^2 + 1}A^{n^2 + 1} = 0$$ using scalars $\alpha_0, \ldots, \alpha_{n^2 + 1} \in \mathbb{C}$. However, I can't seem to find anything that would force any sort of properties from these scalars, let alone whether at least one of them is nonzero. I already know that the system of vectors $I, A, A^2, \ldots, A^m$ is not necessarily dependent or independent, but I can't find any convenient properties that arise from $m$ being set to $n^2 + 1$ that would make this set dependent. What is so special about $n^2 + 1$ in this case?
Also, as a final question to help guide this: proving the above would imply that $n^2 + 1 \in S$, meaning that $S$ is non-empty. However, that wouldn't make it the smallest nor the largest element in $S$, since there would have to be some other element, which I could conveniently name $k \in S$, such that $k < n^2 + 1$. However, what exactly would guarantee that such a $k$ would exist?
Edit: I should note that this homework was assigned within the same week that we were taught eigenvectors. I was tempted to try using what I learned this week about characteristic polynomials; however, I can't see how polynomials that take scalars as inputs would relate to polynomials that take in matrices as inputs.