One way of solving a system of linear equations is to express it in an augmented matrix. Then, we can perform elementary row operations in order to bring the matrix into RREF (reduced row echelon form), and from there, we can find the solutions of the initial system. A lot of sources take this solution set equvalence fact as granted. But why are the solutions to RREF(A) the same as the solutions to A?
I think another way of asking this is: why does row equivalence imply two matrices will have the same solution set?
Best Answer
Note that the augmented matrix (AM) is just a shorthand way of writing up the full given system, including the right hand side, in its present state. The so-called elementary operations transform the originally given system into a system whose solutions can be easily found "by inspection" and little calculation.
Now these elementary operations have been invented for the very reason that they do not change the set ${\cal L}$ of solutions in any way. This is obvious for multiplying an equation, resp., the corresponding row of AM, by a nonzero constant, and it is obvious for interchanging two equations, resp., the corresponding rows of AM. There remains adding $\lambda\>{\rm row}_i$ to ${\rm row}_j$, where $j\ne i$. Since this adding encompasses the RHS of the system as well it is easy to see that any ${\bf x}$ solving the old system also solves the new system. It remains to check that the new system contains no additional solutions. Therefore let ${\bf x}$ be any solution of the new system. Then this ${\bf x}$ will also solve the newnew system obtained by adding $-\lambda\>{\rm row}_i$ to (the new) ${\rm row}_j$. But this newnew system is again the old system; hence ${\bf x}$ is already a solution of the old system.