Csdrhrt

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, jleq 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.

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},,sgeq 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 $kin{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.