Minimal polynomial algorithm In our textbooks we are given the following algorithm:
Let $V$ be a vector space having dimension $n$ over a field $K$ ( $\mathbb R$ or $\mathbb C$ ) and $A : V \to V$ be a linear map. In a sequence $I,A, A^2,A^3,..,A^n$,we pick a non-zero matrix element in the first member of the sequence ( $I$ ) with which we are "eliminating" corresponding matrix elements in the other members of the sequence. Now we have $A_{11},A_{12},...,A_{1n}$ , where $$A_{1k} = A^k - \beta_{1k}I ,\ k=1,...,n$$ If $A_{11}\neq 0$ , we do the same to the sequence $A_{11},A_{12},...,A_{1n}$, meaning that we again pick a non-zero matrix element in $A_{11}$ with which we are "eliminating" corresponding matrix elements in the other members of the sequence Now we have $A_{22},A_{23},...,A_{2n}$, where $$A_{2k} = A_{1k} - \beta_{2k}A_{11} ,\ k=2,...,n$$ We repeat the same process until we get $A_{jj}=0 , A_{j-1,j-1}\neq0,\ j\leq n$.As a result we get $$ I \quad A \quad A^2 \quad A^3 \quad  ... \quad A^n \\ \quad A_{11}\enspace  A_{12}\enspace A_{13} \quad... \enspace A_{1n} \\ \qquad \quad A_{22}\enspace A_{23} \quad... \enspace A_{2n} \\ \hspace{90pt}. \\ \hspace{90pt}. \\ \hspace{90pt}. \\ \hspace{90pt}A_{jj}$$ 
To get our minimal polynomial we just need to "unroll" $A_{jj}$, precisely $0=A_{jj}=A_{j-1,j}-\beta_{j-1,j}A_{j-1,j-1}=... $
Now it says that it's obvious that the sequence $ I,A_{11},A_{22},...,A_{j-1,j-1}$ is linearly independent, but I can't really see why though.Also, how do we know we can't get a monic polynomial $p(x)$ of less degree such that $p(A)=0$ ?
Thank you for your time.
 A: For convenience, we define $A_{00}=I.$ The matrices $A_{00},A_{11},A_{22},\ldots,A_{j-1,j-1}$ are linearly independent, because each matrix $A_{kk}$ has a non-zero element at a position $(a_k,b_k)$ where all matrices $A_{rs},\,s\geq r>k$ have a zero element. 
Now let us take a look at the sum
$$
S = c_0A_{00}+c_1A_{11}+\ldots+c_{j-1}A_{j-1,j-1}
$$
In order to make this sum become the zero matrix, the entry of $S$ at position $(a_0,b_0)$ must be $0.$ Therefore, $c_0=0,$ because the other addends do not change anything at this position of the matrix. The entry of $S$ at position $(a_1,b_1)$ must also be $0$. Therefore, $c_1=0.$ By induction, we can show that $c_0 = \ldots = c_{j-1} = 0,$ from which it follows that the matrices $A_{00},A_{11},A_{22},\ldots,A_{j-1,j-1}$ are linearly independent.
For each $k\in\{0,\ldots,j-1\},$ we know that the matrices $A_{00},A_{11},A_{22},\ldots,A_{kk}$ are linear combinations of the matrices $I,A,A^2,\ldots,A^{k}.$ If the minimal polynomial $p$ had a degree less than $j,$ the equation $p(A)=0$ would induce a non-trivial linear combination of $A_{00},A_{11},A_{22},\ldots,A_{kk}$ with $k<j$ which equals the zero matrix. This contradicts the fact that the matrices $A_{00},A_{11},A_{22},\ldots,A_{kk}$ are linearly independent.
