# 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, 2020 at 12:02

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, 2018 at 12:59

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, 2018 at 3:41
• The question asked for a proof, but this is not a proof. Feb 19, 2019 at 11:23
• @orient, what is a proof, and how in particular does my answer fall short? Feb 20, 2019 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, 2019 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, 2019 at 3:25

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 !

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).

Consider the system of linear equations $$\mathbf{A}\mathbf{x}=\mathbf{b}$$. For each row $$i$$, we have:

$$\mathbf{A}_{i\cdot}\mathbf{x}=b_{i}$$

In Gaussian elimination, we perform a sequence of transformation steps. Each step consists of adding or subtracting a multiple of one row to another row of both $$\mathbf{A}$$ and $$\mathbf{b}$$:

\begin{aligned} \mathbf{A}_{i\cdot}^{k+1} &\leftarrow \mathbf{A}_{i\cdot}^{k}+\alpha_{ij}^{k}\cdot\mathbf{A}_{j\cdot}^{k} \\ b_{i}^{k+1}&\leftarrow b_{i}^{k}+\alpha_{ij}^{k}\cdot b_{j}^{k} \end{aligned}

Now it's easy to show that

\begin{aligned} b_{i}^{k+1} &= b_{i}^{k}+\alpha_{ij}^{k}\cdot b_{j}^{k} \\ &=\mathbf{A}_{i\cdot}^{k}\mathbf{x}+\alpha_{ij}^{k}\cdot \mathbf{A}_{j\cdot}^{k}\mathbf{x}\\ &=\left(\mathbf{A}_{i\cdot}^{k}+\alpha_{ij}^{k}\cdot\mathbf{A}_{j\cdot}^{k}\right)\mathbf{x}\\ &=\mathbf{A}_{i}^{k+1}\mathbf{x} \end{aligned}

We have seen that the transformation step does not change the solution $$\mathbf{x}$$, i.e., the solution $$\mathbf{x}$$ is an invariant with respect to the Gaussian elimination step. When solving a system of linear equations, the scalars $$\alpha_{ij}^{k}$$ are chosen such that the matrix $$\mathbf{A}$$ becomes an upper triangular matrix, which makes the equation much easier to solve e.g. using backward substitution.

More Generally

Premultiplying the equation with an invertible matrix $$\mathbf{T}$$ does not change the solution $$\mathbf{x}$$:

$$\mathbf{A}\mathbf{x}=\mathbf{b} \implies \mathbf{T}\mathbf{A}\mathbf{x}=\mathbf{T}\mathbf{b}$$

Defining $$\mathbf{A}'=\mathbf{T}\mathbf{A}$$ and $$\mathbf{b}'=\mathbf{T}\mathbf{b}$$, we have a new equation

$$\mathbf{A}'\mathbf{x}=\mathbf{b}'$$

If you can find $$\mathbf{T}$$ that makes the new equation much easier to solve, then you can create your own algorithm to solve a system of linear equations!