why does the reduced row echelon form have the same null space as the original matrix?

Solution 1:

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.

Solution 2:

This is because, interpreting the rows of the matrix as a system of linear equations, the original matrix and its row-reduced form correspond to logically equivalent systems. Indeed we can go back to the original matrix (the original system of equations) by means of the inverse transformations on rows.

Solution 3:

The operations (elementary row operations) that occur in Gauss-Jordan elimination for the purposes of row reduction are mathematically equivalent to left multiplication by invertible matrices known as elementary matrices; these in fact generate the general linear group of $n\times n$ invertible real matrices.

Because elementary matrices are invertible, it follows that left multiplication does not change the kernel (also known as the null space). In other words, $$\ker EA=\ker A$$ where $E$ is an elementary matrix for all suitable matrices $A$.

Since no single elementary matrix changes the kernel, it follows that a product of any finite number of elementary matrices will not change the kernel, either.