Gaussian elimination method for solving systems of linear algebraic equations

What do you know about solving systems of linear equations? This type of tasks is often offered to students in linear algebra homework. In one of our videos we discussed that a system of linear equations can be solved using Cramer’s rule which involves finding determinants and it might get tricky when dealing with systems of 4, 5 or more equations. Luckily, there is another method which allows to avoid massive calculations.  And it is called Gaussian elimination (or row reduction). 
Consider the system of $m$ linear equations with $n$ unknowns written in the next form:

\left\{ \begin{aligned}a_{11}x_1+a_{12}x_2+…+a_{1n}x_n =b_1\\a_{21}x_1+a_{22}x_2+…+a_{2n}x_n =b_2\\ …& & \\a_{m1}x_1+a_{m2}x_2+…+a_{mn}x_n =b_m\end{aligned}\right.
where x_1, x_2, …, x_n– unknowns,
a_{ij}- coefficients of the unknowns,
b_i- free terms (the right parts of the equations).

Here’s video version of this tutorial:

Let us think of it as of a set of conditions giving us information about unknowns. It can be spelled like… if we take, say, this much of this unknown noted as x_1 and this much of another unknown – x_2, then some amount of the next unknown and, say, sum them up – we’ll obtain this much of b_1. Of course, this information is not enough for defining all unknowns, so there are more equations. if we take that much of unknown x_1 and subtract that much of x_2, then add some other unknowns and subtract some another – we’ll obtain this much of b_2. And so on.
Ok, let’s move on. What else can we say about this system?

•  it is pretty obvious that we can swap any pair of equations in the set because the order in which we get this information is not important. The idea is to have enough information but not particularly ordered;
• another simple conclusion that comes to mind is that we can multiply both sides of any equation by any non-zero constant and that will not change the system, as well as adding to both sides of any of the equations corresponding parts of any another equation.

We can perform these elementary transformations as many times as we want. It will lead to equivalent system of equations because in fact doing so we are not producing or reducing information about the unknowns but just reorganizing it.

What we are going to do with all this? Obviously we’ll find these properties essential when solving a system of equations using Gaussian method.

Let’s consider some real life example of the system of linear equations:

\left\{ \begin{aligned}2x_1+4x_2-3x_3+2x_4 =0\\x_1-2x_2+5x_3+2x_4 =2\\2x_2-4x_3+5x_4 =-1\\2x_3+x_4 =-3 \end{aligned}\right.

It’s a good habit to form nice columns of variable first before solving any system of a kind. It should prevent us from making mistakes and we’ll proceed faster. Secondly, we’ll rearrange the system so that equations staffed with all unknowns are in the top. Now, let’s pick the first two equations from the system and eliminate the first unknown from one of them. It’s not important which equation and which unknown to choose, the only condition is that both equations must contain it :).  Let’s pick the first and the second ones and intend to eliminate the first unknown x_1. In a few steps we’ll form suitable notion of the system, you’ll see.

Ok, back to elimination. How can that be done? More than simple – first we multiply or divide one of the picked equations by some number in order to have as much of x_1 in it as in the other one but with opposite sign. Second – we add corresponding sides of these two equations and thus unknown x_1 is canceled out. It will make no difference of cause if we add the first equation to the second or vice versa.

So let’s multiply the first equation by the \frac{1}{2}, add it to the second and replace existing second equation with the new one. After performing all that we obtain a new equivalent system:

\left\{ \begin{aligned}2x_1+4x_2-3x_3+2x_4 =0\\-4x_2+\frac{13}{2} x_3+x_4 =2\\2x_2-4x_3+5x_4 =-1\\2x_3+x_4 =-3 \end{aligned}\right.

As you can see we eliminated x_1 from the second row.

Let’s now multiply it by \frac{1}{2}, add the result to the equation in the third row, and then replace existing equation with the newly obtained one.

\left\{ \begin{aligned}2x_1+4x_2-3x_3+2x_4 =0\\-4x_2+\frac{13}{2} x_3+x_4 =2\\-\frac{3}{4}x_3+\frac{11}{2}x_4 =0\\2x_3+x_4 =-3 \end{aligned}\right.

We eliminated x_2 from the third equation. Our last move will be elimination of x_3 from the forth equation.

So let’s multiply it by -\frac{3}{8}, add to the third row equation and put the result into the forth row.

Our final equivalent system looks as follows:

\left\{ \begin{aligned}2x_1+4x_2-3x_3+2x_4 =0\\-4x_2+\frac{13}{2} x_3+x_4 =2\\-\frac{3}{4}x_3+\frac{11}{2}x_4 =0\\ \frac{41}{8}x_4 =\frac{9}{8} \end{aligned}\right.

We obtained a system in upper-triangular form.

Finding the unknowns of the triangular system is called the reverse course of Gauss method. Actually, it is fairly easy to see how to proceed from this point. First, we’ll find x_4 from the forth equation. Then we’ll just back-substitute x_4 into the third equation in order to find x_3. After that we’ll plug x_4 and x_3 into the second equation to find x_2. Then, finally, knowing x_2, x_3 and x_4, we can easily find x_1 from the first equation.

So, here is the answer to our system:

\left\{ \begin{aligned}x_1 =-\frac{88}{41}\\x_2=\frac{89}{41}\\x_3=\frac{66}{41}\\ x_4 =\frac{9}{41} \end{aligned}\right.

You can check it if you like.

In general, it may occur that during transformation of the system we obtain contradictory equation of the form  0 = b, where b \neq 0. This means that the system has no solutions. Such systems are called inconsistent.

It may also happen so that you follow the method correctly but fon’t get this nice triangular form and this last equation \frac{41}{8}x_4 = \frac{9}{8} from where you can derive x_4 and solve the system. Instead you come against a case where you can only express some unknows in terms of another. It is nothing to be fear of, that’s normal 🙂 In one of the next sections we’ll pick an example showing that particular case.

Gauss elimination method is often even more usable than Cramer’s method (Cramer’s rule) which requires calculations of determinants and this operation is complicated for systems of high order. On the contrary, Gaussian elimination can be performed comparatively easy for systems of order higher than, say, 4 when calculating determinants gets complicated.

Summing up. When you want to solve a system of linear equations using Gaussian elimination, first you need to obtain your system in a triangular (or trapeziodal) form. For that you go down your system and step by step eliminate variables from the equations. After that you go up and gradually find variables (or express them through others). Don’t forget to check your answers by plugging them into the initial system, it helps to avoid mistakes and do your homework assignment correctly.