gaussian elimination

… a process with which we solve systems of equations.

---

The familliar basic process:
e.g.:

$$\begin{array}{rl}x+2y+z& =2\\ 3x+8y+z& =12\\ 4y+z& =2\end{array}$$

We can solve it using gaussian elimination by hand, by eliminating variables, until only one is left:
$II-III$

$$\begin{array}{rl}3x-8y+z-4y-z& =12-2\\ 3x-4y& =10\end{array}$$

$I-III$

$$\begin{array}{rl}x-2y+z-4y-z& =2-2\\ x-2y& =0\end{array}$$

Now we can solve for $x$:

$$\begin{array}{rl}3x-4y-2x+4y& =10\\ x& =10\end{array}$$

For $y$:

$$\begin{array}{rl}10-2y& =0\\ y& =5\end{array}$$

And for $z$:

$$\begin{array}{rl}4\cdot 5+z& =2\\ z& =-18\end{array}$$

Gaussian elimination with matrices

Representing systems of equations as matrices is how every computer solves them.

e.g. continuing with the example from the introduction, we can pull out the coefficients into a matrix:

$$\underset{A}{\underbrace{\left[\begin{array}{ccc}1& 2& 1\\ 3& 8& 1\\ 0& 4& 1\end{array}\right]}}\left[\begin{array}{c}x\\ y\\ z\end{array}\right]=\underset{b}{\underbrace{\left[\begin{array}{c}2\\ 12\\ 2\end{array}\right]}}$$

Now again, we want to eliminate variables from the equation.
$a_{1,1}$ is our first so called pivot. We want to knock out $x$ from the second equation / row by subtracting $3$ times the first row:

$$\to \left[\begin{array}{cccc}1& 2& 1& 2\\ 0& 2& -2& 6\\ 0& 4& 1& 2\end{array}\right]$$

We apply the same operations to the vector $b$, which we carry along with us in the augmented matrix.
Step $a_{2,1}$ is done and there’s nothing to do in step $a_{3,1}$ as $x$ is already $0$.
Now clearing out $a_{3,2}$ (subtracting $2$ times the newly obtained second from the third row):

$$\to \left[\begin{array}{cccc}\boxed{1}& 2& 1& 2\\ 0& \boxed{2}& -2& 12\\ 0& 0& \boxed{5}& -10\end{array}\right]$$

We now have an upper triangular matrix $U$, with three pivot columns along the main diagonal. And we have a new vector $c$ after the elimination.
The determinant of this matrix would be the product of the main diagonal.

Now we do “back-substitution” of the values into a system of equations:

$$\begin{array}{rl}x+2y+z& =1\\ y-2z& =12\\ 5z& =-10\end{array}$$

And solve the S.O.E. in reverse order:
$z=-2,y=1,x=2$

The steps we took can be expressed as multiplying $A$ with some elimination matrix $E$:

$$\begin{array}{r}\underset{E_{2,1}}{\underbrace{\left[\begin{array}{ccc}1& 0& 0\\ -3& 1& 0\\ 0& 0& 1\end{array}\right]}}\left[\begin{array}{ccc}1& 2& 1\\ 3& 8& 1\\ 0& 4& 1\end{array}\right]=\left[\begin{array}{ccc}1& 2& 1\\ 0& 2& -2\\ 0& 4& 1\end{array}\right]\\ \underset{E_{3,2}}{\underbrace{\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& -2& 1\end{array}\right]}}\left[\begin{array}{ccc}1& 2& 1\\ 0& 2& -2\\ 0& 4& 1\end{array}\right]=\left[\begin{array}{ccc}1& 2& 1\\ 0& 2& -2\\ 0& 0& 5\end{array}\right]\end{array}$$ $$\begin{array}{r}{E}_{2,1}(E_{3,2}A)=U\\ (E_{2,1}{E}_{3,2})A=U\\ EA=I\end{array}$$

References

Gilbert Strang OCW lecture Lecture 2: Elimination with matrices

mathematics