Gaussian elimination is an algorithm for solving systems of linear equations. Variables are eliminated one after the other using addition method. This continues until there is only one variable left in the last equation, and in every other equation always one variable more than in the one below it, like for example in the following system: $\begin{array}{cccccccccc}\mathrm I:&x_1&+&2x_2&-&x_3&+&x_4&=&-1\\\mathrm{II}:&\;&\;&x_2&+&x_3&-&x_4&=&4\\\mathrm{III}:&\;&\;&\;&\;&x_3&+&x_4&=&2\\\mathrm{IV}:&\;&\;&\;&\;&\;&\;&x_4&=&-1\end{array}$

Now $x_4$ is given by the last equation. By substituting the given value for $x_4$ in III the value for $x_3$ can be found and in the same way all other unknowns by substitution in the next higher equation.

Comment

• It is not mandatory that implicitly the last variable $x_4$ in the last equation stands alone. Variables can be swapped, as well as equations.

## Step by step

At first it seems difficult to transfor the system into a triangular matrix by sensible row switches and steps of modification because the eye for it only develops with practice.

1.Step

$\left(\begin{array}{ccc}{\mathrm a}_{11}&\cdots&{\mathrm a}_{1\mathrm n}\\\vdots&&\vdots\\{\mathrm a}_{\mathrm m1}&\cdots&{\mathrm a}_\mathrm{mn}\end{array}\left|\begin{array}{c}{\mathrm b}_1\\\vdots\\{\mathrm b}_\mathrm m\end{array}\right.\right)\begin{array}{c}\mathrm I):{\mathrm a}_{11}\\\rightarrow\\\end{array}\left(\begin{array}{ccc}1&\cdots&\frac{{\mathrm a}_{1\mathrm n}}{{\mathrm a}_{11}}\\\vdots&&\vdots\\{\mathrm a}_{\mathrm m1}&\cdots&{\mathrm a}_\mathrm{mn}\end{array}\left|\begin{array}{c}\frac{{\mathrm b}_1}{{\mathrm a}_{11}}\\\vdots\\{\mathrm b}_\mathrm m\end{array}\right.\right)$

Create the first position of the first row $\boxed1$ by dividing by the value of this position.

2.Step:

$\begin{array}{c}\\\mathrm{II})\;-{\mathrm a}_{21}\cdot(\mathrm I)\;\\\rightarrow\\\mathrm i)\;-\mathrm{ai}1\cdot(\mathrm I)\\\end{array}\left(\begin{array}{cccc}1&\frac{{\mathrm a}_{12}}{{\mathrm a}_{11}}&\dots&\frac{{\mathrm a}_{1\mathrm n}}{{\mathrm a}_{11}}\\0&{\mathrm a}_{22}&\dots&{\mathrm a}_{2\mathrm n}\\\vdots&\vdots&&\vdots\\0&{\mathrm a}_{\mathrm m2}&\cdots&{\mathrm a}_{\mathrm{mn}}\end{array}\left|\begin{array}{c}\frac{{\mathrm b}_1}{{\mathrm a}_{11}}\\{\mathrm b}_2\\\vdots\\{\mathrm b}_\mathrm m\end{array}\right.\right)$

Create in the positions $a_{21},\;…..\;,\;a_{m1}$ $\boxed0$ by substracting $a_{i1}$ times row I from row i $\in$ {2,…,m}.

$\begin{array}{c}\mathrm{II}):{\mathrm a}_{22}\\\rightarrow\\\mathrm i)-{\mathrm a}_{\mathrm i2}\cdot(\mathrm{II})\end{array}\left(\begin{array}{ccccc}1&\frac{{\mathrm a}_{12}}{{\mathrm a}_{11}}&\cdots&\cdots&\frac{{\mathrm a}_{1\mathrm n}}{{\mathrm a}_{11}}\\0&1&\frac{{\mathrm a}_{23}}{{\mathrm a}_{22}}&\cdots&\frac{{\mathrm a}_{2\mathrm n}}{{\mathrm a}_{22}}\\\vdots&0&{\mathrm a}_{33}&\cdots&{\mathrm a}_{3\mathrm n}\\\vdots&\vdots&\vdots&&\vdots\\0&0&{\mathrm a}_{\mathrm m3}&\cdots&{\mathrm a}_{\mathrm{mn}}\end{array}\left|\begin{array}{c}\frac{{\mathrm b}_1}{{\mathrm a}_{11}}\\\frac{{\mathrm b}_2}{{\mathrm a}_{22}}\\{\mathrm b}_3\\\vdots\\{\mathrm b}_\mathrm m\end{array}\right.\right)$

Repeat these two steps for row II and thus create zeros starting from the diagonal in the second column.

$\rightarrow\left(\begin{array}{cccc}1&&&\\0&1&&\\\vdots&&1&\\0&\cdots&0&1\end{array}\left|\begin{array}{c}\\\\\\\end{array}\right.\right)$

Performing this for every row an upper triangular matrix with diagonal value (leading coefficients) 1 will be produced.

Exercises