What is the proof for this and the intuitive explanation for why the reduced row echelon form have the same null space as the original matrix?
[Math] why does the reduced row echelon form have the same null space as the original matrix
linear algebramatrices
Best Answer
The short answer: Because you multiply nonsingular matrices from the left.
The long answer: Say you have a matrix $A$. Each Gaussian elimination step corresponds to some elementary matrix (which are nonsingular). Thus, there exists a nonsingular matrix $M$ (product of elementary matrices) such that $MA$ has reduced row echelon form.
Now, let $x$ be in the null space of $A$. Then, we have $$MAx = M(Ax) = M0 = 0.$$ That is, $x$ is also in the null space of $MA$. On other hand, let $y$ be in the null space of $MA$. Then, we also have $$Ay = M^{-1} (M A y) = M^{-1} 0 = 0.$$ Thus, the null spaces of $A$ and $MA$ are the same.