# Proof of Gaussian elimination/Why does it work

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?

• Gaussian Elimination doesn't solve the system, it only makes the solution easier, because it eliminates unnecessary/superfluous things from the system. Dec 13 '20 at 12:02

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),$$

• This isn't a proof. Jul 1 '18 at 3:41
• The question asked for a proof, but this is not a proof. Feb 19 '19 at 11:23
• @orient, what is a proof, and how in particular does my answer fall short? Feb 20 '19 at 2:38
• Hi. What is missing here is an indication that you can subtract the LHS of equation A from the LHS of equation B and the RHS of equation A from the RHS of equation B because the LHS of A is equal to the RHS of A and you can simultaneously subtract equal quantities from both sides of equation B without affecting the truth of such equation. This is probably that what you want to say below the equations. That is the thing that, in my opinion, one needs to spell out. It is the pivot (in the sense of Leron) of the reasoning. Feb 22 '19 at 11:21
• @orient Did you miss my reference to Euclid's common notions? The link I provided goes into significant detail. Thank you for responding. Feb 24 '19 at 3:25

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.

• Perhaps expand on how elementary row operations are realized as matrices. That's likely to be confusing to most people asking this question. May 3 '18 at 12:59

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.

This is the best I can find online: https://www.youtube.com/watch?v=bnC848ie16Q&ab_channel=MyWhyU

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 !

Gaussian elimination is based on 3 elementary row operations:

1. row switching (row within the matrix can be switched with another row)
2. row multiplication (each element in a row can be multiplied by a non-zero constant)
3. row addition (our row can be replaced by the sum of our row and a multiple of another row)

If first two operations are rather intuitive, 3rd one may be not so obvious.

5x + 3y = 200 could be superseded with a = 200,
2x + y = 100 with b = 100.
What is a - b? It's 200 - 100.
What is a - k * b? It's 200 - k * 100.
Therefore, (5x + 3y) - k * (2x + y) = 200 - k * 100.
It has nothing to do with there being x and y in both equations.
It's just a happy coincidence that this addition will help us to eliminate xs or ys.