why does the reduced row echelon form have the same null space as the original matrix? 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?
 A: 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.
A: Say we have an $n$x$n$ matrix, $A$, and are going to row reduce it. Every time we do a row operation, it is the same as multiplying on the left side by an invertible matrix corresponding to the operation. So at the end of the process, we can conclude something like $B = L_1L_2...L_kA$, where $B$ is the row reduced matrix, and the $L_i$ are the matrices corresponding to the row operations. 
The null space of $A$ is the set $\left\{\vec{x} \in \mathbb{R}^n |\space A\vec{x} = 0\right\}$, so for any $\vec{x}$ in this set:
$B\vec{x} = L_1L_2...L_kA\vec{x} = L_1L_2...L_k\vec{0} = \vec{0}$. 
Conversely, if $x$ is in the null space of $B$ ($B\vec{x} = \vec{0}$) then
$A\vec{x} = L_k^{-1}...L_2^{-1}L_1^{-1}L_1L_2...L_kA\vec{x} = L_k^{-1}...L_2^{-1}L_1^{-1}B\vec{x} = L_k^{-1}...L_2^{-1}L_1^{-1}\vec{0} = \vec{0}$
A: 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.
A: 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.
