### 1 Gaussian elimination

Recall from HELM booklet  8 that the basic idea with Gaussian (or Gauss) elimination is to replace the matrix of coefficients with a matrix that is easier to deal with. Usually the nicer matrix is of upper triangular form which allows us to find the solution by back substitution . For example, suppose we have

$\begin{array}{rcll}{x}_{1}+3{x}_{2}-5{x}_{3}& =& 2& \text{}\\ 3{x}_{1}+11{x}_{2}-9{x}_{3}& =& 4& \text{}\\ -{x}_{1}+{x}_{2}+6{x}_{3}& =& 5\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}& \text{}\end{array}$

which we can abbreviate using an augmented matrix to

$\phantom{\rule{2em}{0ex}}\left[\begin{array}{cccc}\hfill 1\hfill & \hfill 3\hfill & \hfill -5\hfill & \hfill 2\hfill \\ \hfill 3\hfill & \hfill 11\hfill & \hfill -9\hfill & \hfill 4\hfill \\ \hfill -1\hfill & \hfill 1\hfill & \hfill 6\hfill & \hfill 5\hfill \end{array}\right].$

We use the boxed element to eliminate any non-zeros below it. This involves the following row operations

$\phantom{\rule{2em}{0ex}}\left[\begin{array}{cccc}\hfill 1\hfill & \hfill 3\hfill & \hfill -5\hfill & \hfill 2\hfill \\ \hfill 3\hfill & \hfill 11\hfill & \hfill -9\hfill & \hfill 4\hfill \\ \hfill -1\hfill & \hfill 1\hfill & \hfill 6\hfill & \hfill 5\hfill \end{array}\right]\begin{array}{c}\hfill \\ R2-3×R1\hfill \\ R3+R1\hfill \end{array}⇒\left[\begin{array}{cccc}\hfill 1\hfill & \hfill 3\hfill & \hfill -5\hfill & \hfill 2\hfill \\ \hfill 0\hfill & \hfill 2\hfill & \hfill 6\hfill & \hfill -2\hfill \\ \hfill 0\hfill & \hfill 4\hfill & \hfill 1\hfill & \hfill 7\hfill \end{array}\right].$

And the next step is to use the 2 to eliminate the non-zero below it . This requires the final row operation

$\phantom{\rule{2em}{0ex}}\left[\begin{array}{cccc}\hfill 1\hfill & \hfill 3\hfill & \hfill -5\hfill & \hfill 2\hfill \\ \hfill 0\hfill & \hfill 2\hfill & \hfill 6\hfill & \hfill -2\hfill \\ \hfill 0\hfill & \hfill 4\hfill & \hfill 1\hfill & \hfill 7\hfill \end{array}\right]\begin{array}{c}\hfill \\ \hfill \\ R3-2×R2\hfill \end{array}⇒\left[\begin{array}{cccc}\hfill 1\hfill & \hfill 3\hfill & \hfill -5\hfill & \hfill 2\hfill \\ \hfill 0\hfill & \hfill 2\hfill & \hfill 6\hfill & \hfill -2\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill -11\hfill & \hfill 11\hfill \end{array}\right].$

This is the augmented form for an upper triangular system, writing the system in extended form we have

$\begin{array}{rcll}{x}_{1}+3{x}_{2}-5{x}_{3}& =& 2& \text{}\\ 2{x}_{2}+6{x}_{3}& =& -2\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}& \text{}\\ -11{x}_{3}& =& 11& \text{}\end{array}$

which is easy to solve from the bottom up, by back substitution .

##### Example 5

Solve the system

$\begin{array}{rcll}{x}_{1}+3{x}_{2}-5{x}_{3}& =& 2& \text{}\\ 2{x}_{2}+6{x}_{3}& =& -2\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}& \text{}\\ -11{x}_{3}& =& 11& \text{}\end{array}$
##### Solution

The bottom equation implies that ${x}_{3}=-1$ . The middle equation then gives us that

$\phantom{\rule{2em}{0ex}}2{x}_{2}=-2-6{x}_{3}=-2+6=4\phantom{\rule{2em}{0ex}}\therefore \phantom{\rule{1em}{0ex}}{x}_{2}=2$

and finally, from the top equation,

$\phantom{\rule{2em}{0ex}}{x}_{1}=2-3{x}_{2}+5{x}_{3}=2-6-5=-9.$

Therefore the solution to the problem stated at the beginning of this Section is

$\phantom{\rule{2em}{0ex}}\left[\begin{array}{c}\hfill {x}_{1}\hfill \\ \hfill {x}_{2}\hfill \\ \hfill {x}_{3}\hfill \end{array}\right]=\left[\begin{array}{c}\hfill -9\hfill \\ \hfill 2\hfill \\ \hfill -1\hfill \end{array}\right].$

The following Task will act as useful revision of the Gaussian elimination procedure.

Carry out row operations to reduce the matrix

$\phantom{\rule{2em}{0ex}}\left[\begin{array}{ccc}\hfill 2\hfill & \hfill -1\hfill & \hfill 4\hfill \\ \hfill 4\hfill & \hfill 3\hfill & \hfill -1\hfill \\ \hfill -6\hfill & \hfill 8\hfill & \hfill -2\hfill \end{array}\right]$

into upper triangular form.

The row operations required to eliminate the non-zeros below the diagonal in the first column are as follows

$\phantom{\rule{2em}{0ex}}\left[\begin{array}{ccc}\hfill 2\hfill & \hfill -1\hfill & \hfill 4\hfill \\ \hfill 4\hfill & \hfill 3\hfill & \hfill -1\hfill \\ \hfill -6\hfill & \hfill 8\hfill & \hfill -2\hfill \end{array}\right]\begin{array}{c}\hfill \\ R2-2×R1\hfill \\ R3+3×R1\hfill \end{array}⇒\left[\begin{array}{ccc}\hfill 2\hfill & \hfill -1\hfill & \hfill 4\hfill \\ \hfill 0\hfill & \hfill 5\hfill & \hfill -9\hfill \\ \hfill 0\hfill & \hfill 5\hfill & \hfill 10\hfill \end{array}\right]$

Next we use the 5 on the diagonal to eliminate the 5 below it:

$\phantom{\rule{2em}{0ex}}\left[\begin{array}{ccc}\hfill 2\hfill & \hfill -1\hfill & \hfill 4\hfill \\ \hfill 0\hfill & \hfill 5\hfill & \hfill -9\hfill \\ \hfill 0\hfill & \hfill 5\hfill & \hfill 10\hfill \end{array}\right]\begin{array}{c}\hfill \\ \hfill \\ R3-R2\hfill \end{array}⇒\left[\begin{array}{ccc}\hfill 2\hfill & \hfill -1\hfill & \hfill 4\hfill \\ \hfill 0\hfill & \hfill 5\hfill & \hfill -9\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 19\hfill \end{array}\right]$

which is in the required upper triangular form.