There is a unique polynomial $q_A(x)$ with a leading $1$ and degree $k$ such that $q_A(A)=0$ Suppose $A_{n\times n}$. Show there is a $k\in \mathbb{N}$ and a polynomial $q_A(x)$ with a leading $1$ coefficient and least degree $k$ such that $q_A(A)=0$.
If I recall correctly, this is the minimal polynomial of $A$, and the result follows my showing there exists a $k$ such that $I, A, A^2,...,A^k$ are linearly dependent. Can anyone offer a simple explanation of a proof of this problem?
 A: Wealll, let $\Bbb F$ be any field and let $M_n(\Bbb F)$ be the vector space of $n \times n$ matrices over $\Bbb F$.  I claim the dimension of $M_n(\Bbb F)$ over $\Bbb F$ is precisely $n^2$.  This is easy to see:  indeed, the $n^2$ matrices $E_{ij}$ form a basis for $M_n(\Bbb F)$, where $E_{ij}$ is matrix whose $ij$ entry is $1$  and whose other entries are $0$.  The set $\mathcal E = \{ E_{ij} \mid 1 \le i, j \le n \}$ clearly spans $M_n(\Bbb F)$, since for any $A = [A_{ij}] \in M_n(\Bbb F)$ we may write
$A = \sum_{i, j = 1}^n A_
{ij} E_{ij}; \tag{1}$
the same formula shows the $E_{ij}$ are linearly independent since
$\sum_{i,j = 1}^n A_{ij} E_{ij} = 0 \tag{2}$
if and only if the matrix $A = 0$, i.e., $A_{ij} = 0$ for all $i, j$; we have thus  shown that  $\mathcal E$ is a basis for $M_n(\Bbb F)$, and thus that
$\dim M_n(\Bbb F) = n^2 < \infty. \tag{3}$
Returning to the powers $A^i$ of the matrix $A$, we see from (3) that the sequence $I$, $A$, $A^2$, $\ldots$, $A^{n^2}$ of matrices, consisting as it does of $n^2 + 1$ elements of $M_n(\Bbb F)$, must be linearly dependent; that is, there is a sequence of $n^2 + 1$ elements $c_i \in \Bbb F$, $1 \le i \le n^2$, such that
$\sum_0^{n^2} c_i A^i = 0; \tag{4}$
(4) shows that $A$ satisfies the polynomial
$p(x) = \sum_0^{n^2} c_i x^i \in \Bbb F[x]. \tag{5}$
Having established that $A$ satisfies some polynomial in $\Bbb F[x]$, we conlude there is a polynomial $q_A(x) \in \Bbb[x]$ of minimal degree $k \le n^2$ with
$q_A(A) = \sum_0^k q_i A^i = 0; \tag{6}$
since $\Bbb F$ is a field, we may if necessary divide $q_A(x)$ through by $q_k \ne 0$ (since $\deg q = k$) and thus take $q_A(x)$ to be monic.  The uniqueness of such $q_A(x)$ may then be seen as follows:  if $p(x) \in \Bbb F[x]$ is monic of degree $k$ and $p(A) = 0$, we may by the Euclidean algorithm, which holds in $F[x]$ for any field $\Bbb F$, write
$p(x) = d(x) q_A(x) + r(x), \tag{7}$
$d(x), r(x) \in \Bbb F[x]$, where if $r(x) \ne 0$ we have $\deg r <  \deg q_A = k$.  But then
$r(A) = p(A) - d(A)q_A(A) = 0, \tag{8}$
and since $\deg r < k$ the minimality of $k$ forces $r(x) = 0$.  Since $p(x)$ and $q_A(x)$ are both monic of degree $k$ we must then have $d(x) = 1$ and hence $p(x) = q_A(x)$; the minimal polynomial $q_A(x)$ of $A$ is thus unique.  And this over any field $\Bbb F$.  QED.
Hope this helps.  Cheers!
And as ever,
Fiat Lux!!!
᤾
