Let $EA = R_A$, where $R_A$ is the row echelon form of $A$ and $E$ is the product of elementary row operations that reduce $A$ to $R_A$. I've come across the statement that any row of $E$ that corresponds to a row of $R_A$ filled with zeroes forms a basis for the null space, and I'm trying to prove this.
The one significant relationship I've noticed is the following: any row of $\vec E_j$ of $E$ that corresponds with a row of zeroes $\vec r_0$ of $R_A$ implies that, since matrix multiplication dots the rows of $E$ with the columns of $A$, the dot product of the row $\vec E_j$ with $\vec r_0$ is $0$, and therefore, any such row of $E$ must be orthogonal to any column vector of $A$. Since we know that the null space of $A^T$ is orthogonal to the column space of $A$, this means that $\vec E_j$ is in the null space of $A^T$, i.e., the left null space of $A$.
But now, why would the set of all such $\vec E_j$ be linearly independent and span $A^T$? Any tips or reading suggestions are appreciated!
Best Answer
It is essentially just about counting the dimensions. Say that $A$ is $m\times n$ matrix, and the first $k$ rows of $R_A$ are non-zero and the remaining $l=m-k$ rows are zero. We observe two facts about $R_A$:
$\mathrm{rank}(R_A)=k$; This holds because $R_A$ is in row echelon form, and so its non-zero rows are linearly independent. And they obviously generate the row-space.
$\mathrm{null}(R_A)=l$, where $\mathrm{null}(R_A)$ is the dimension of the left null-space of $R_A$. This is true because the null space is $l$-dimensional space consisting of exactly those vectors that are zero in the first $k$ coordinates.
Now the key fact is that multiplying by $E$ does not change the dimensions of the row space and the null-space -- this needs a bit of thought, but it essentially boils down to the fact that $v\mapsto v\cdot E$ is surjective, and injective, respectively. In particular, we have $\mathrm{null}(A)=l$.
The last $l$ rows of $E$ are all in the left null-space of $A$, because $E_i\cdot A=(R_A)_i=0$ for $i=r+1,\dots, r+l$. On the other hand, those rows are linearly independent, because $E$ is invertible. So for dimensional reasons, $(E_{r+1},\dots,E_{r+l})$ must be a basis of the null space.
Remark: I didn't use the rank-nullity theorem, because the question essentially leads to the proof of it, so I felt like it might be a circular argument that way.