Proof of Gaussian elimination/Why does it work
Matthew Martinez 
I have just had a class on linear algebra and the professor explained how to solve matrixes. While he could explain how to solve them by using Gaussian's elimination, he failed to explain how does that work.
Why does matrix before doing any operations have the same solutions as the matrix after "changing" a row with Gaussian elimination?
Where can I read the proof?
$\endgroup$ 15 Answers
$\begingroup$First notice that any combination of elementary row operation(s) is invertible.
Let $Ax=b$ a system of $m$ linear equations in $n$ unknowns, and let $C$ be an invertible $m\times m$ matrix, then $Ax=b$ is equivalent to $CAx=Cb.$ (equivalent means they have the same solution set.)
Proof:
Let $K$ be the solution set of $Ax=b$, and $K'$ of $CAx=Cb$.
$\Longrightarrow:$ Given $k\in K$, $Ak = b$, then multiply $C$ at left on both side we get $CAk=Cb$, so $k\in K'$. So $K\subseteq K'$.
$\Longleftarrow:$ Given $k'\in K'$, $CAk'=Cb$, but since $C$ is invertible, $(C^{-1}C)Ak'=(C^{-1}C)b\implies Ak'=b,$ so $k'\in K$. So $K'\subseteq K,$
which complete the proof.
$\endgroup$ 1 $\begingroup$Any matrix equation is just a system of equations. Consider the example below,
$$ \left( \begin{array} & 0 &0 & 1\\ 1 &1 & 1\\ 0 &1 & 1\\ \end{array}\right) \left( \begin{array} & x\\ y\\ z\\ \end{array}\right) = \left( \begin{array} & 1\\ 2\\ 3\\ \end{array}\right), $$
which is the same as,
$$z=1$$ $$x+y+z=2$$ $$y+z=3.$$
You are probably familiar with the fact that when working with a system of equations you can add multiples of the equations together without affecting the solution. The truth of this statement is related to Euclid's common notions which are in fact axioms. This is why adding and subtracting the rows of a matrix do not affect the solution.
Furthermore you can exchange the rows of the matrix and the constant vector without affecting the solution because they yield the same equations for $x,y,$ and $z$.
The matrix equation below has the same solutions as the original matrix equation because it induces the same system of equations for the variables $x,y,z$. $$ \left( \begin{array} & 1 &1 & 1\\ 0 &1 & 1\\ 0 &0 & 1\\ \end{array}\right) \left( \begin{array} & x\\ y\\ z\\ \end{array}\right) = \left( \begin{array} & 2\\ 3\\ 1\\ \end{array}\right), $$
The matrix equation below has the same solutions as the original matrix because it induces equations which are linear combinations of the equations induced by the original matrix. $$ \left( \begin{array} & 1 &1 & 2\\ 1 &3 & 3\\ 0 &1 & 1\\ \end{array}\right) \left( \begin{array} & x\\ y\\ z\\ \end{array}\right) = \left( \begin{array} & 3\\ 8\\ 1\\ \end{array}\right), $$
$\endgroup$ 5 $\begingroup$One step in Gaussian elimination is an elementary operation, performed by left-multiplying both sides of the equality with an Elementary Matrix.
Since you are left-multiplying by invertible matrices at each step, the solution remains unchanged.
$\endgroup$ $\begingroup$This is the best I can find online:
Essentially, the elimination creates a new plane with the same liner solution as the old plane (before the subtraction) - i.e.: the two planes still intersect, but when you eliminate the "x", "y" or "z" dimension, that plane reorients (twists) to maintain the solution parallel to the axis on which the dimension was collapsed.
This makes sense if you think about subtracting two linear equations that intersect - the pivot point will remain the same.
Enjoy !
$\endgroup$ $\begingroup$Row addition had me stumped for a minute, too. Then I realized that we're simple adding/subtracting 'the same value' to/from both sides of an equation. Using lakesare's example. equation (a) 5X + 3Y = 200 equation (b) 2X + Y = 100 (b) is the equation to be 'changed'. Since it is 'legal' to add, subtract, multiply, divide anything we want to/from/by one side of an equation as long as we do the exact same to the other side we can have: (b) 2X + Y + (200) = 100 + (200), but since 200 = 5X + 3Y,in this system, then we can express (b) as, 2X + Y + (5X + 3Y) = 100 + 200, or 7X + 4Y = 300. The solutions to both equations [2X + Y = 100, and 7X + 4Y = 300] are the same. So both equations are equivalent. This is all we're doing when we substitute one equation in a system with a combination of itself (+) a scalar multiple of another equation in the same system. In my example the scalar was just (1).
$\endgroup$
