# 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?

• This has become a hot question and it's most certainly a duplicate of a VERY common homework question for first years. Those coming from elsewhere keep in mind upvotes are for well researched answers, or at least ATTEMPTS at trying to solve a question. – Alec Teal Jul 31 '15 at 1:15

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.

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.

• hmm, a follow up question: what about finding the basis for the column space? How come the linearly independent columns in the reduced row echelon form match up with the columns in the original matrix? I can see how the rows are maintained, but how are the columns? – beginner Jul 31 '15 at 0:42
• Your question isn't quite clear to me, but finding a basis for the column space of a matrix is done through elementary column operations, not row operations. So it is a distinct (though linked) problem: with row operations, you can find a basis for the kernel; with column oerations, you find a basis for the image of the matrix (more precisely the associated linear map). – Bernard Jul 31 '15 at 0:50
• @beginner left multiplication of elementary matrices does not preserve the column space; right multiplication, however, does -- though then this does not preserve the null space. – oldrinb Jul 31 '15 at 1:02
• @oldrinb To my understanding, you find the basis for the column space by finding the linearly independent columns in the matrix, and you find the linearly independent columns by finding the pivot columns in the reduced row echelon form. the reason is the pivot columns must be linearly independent, but i am not sure why that would mean that the corresponding matrix columns are also linearly independent. (i hope this is not too off topic, the answer just highlighted a point of confusion I had) – beginner Jul 31 '15 at 1:45
• ah, I got it. it comes from solving for the span of the null space $Ax = 0$, and $Ax$ can be written as a linear combination of the column vectors of $A$. By the definition of linear independence, $x$ can only have one solution (the 0 vector). Otherwise, we can use the solutions of $x$ from the null space to show that the pivot variable columns can represent all the free variable columns, thus finding the basis of the column space. – beginner Jul 31 '15 at 3:29

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.

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}$