Solving linear systems using the Gauss elimination

In this topic, we will show you how to solve systems of linear equations by the Gauss method and how to use echelon reduction to solve a system of linear equations. Also, we'll give you an example of a solution.

Gaussian elimination

Earlier, you studied a method that, by using elementary row operations, reduced a matrix to an echelon matrix. The method you're going to see now is called Gaussian elimination. After constructing an augmented matrix, we reduce it to an echelon matrix.

The Gaussian elimination consists of three steps:

1. Constructing an augmented matrix by writing down the coefficients of your equations in a grid, and then adding an extra column on the right for the constants from each equation. Each row of the matrix represents one equation.

2. Reducing the augmented matrix to an echelon matrix. Perform this step in order to get an easier system of equations. Here, you can also reduce the matrix to a reduced row echelon form to make further calculations even easier.

3. Back-solving. Here, you use coefficients of the reduced augmented matrix to construct the system of linear equations and find values of the unknowns.

Now let's take a look at a step-by-step solution.

Say, you have a system:

$\left\{ \begin{array}{lr} 3x + 2y -5z= -1\\ 2x - y + 3z = 13\\ x + 2y - z = 9 \end{array} \right.$

1. Make an augmented matrix corresponding to the system: $\left( \begin{array}{ccc|c} 3 & 2 & -5 & -1\\ 2 & -1 & 3 & 13\\ 1 & 2 & -1 & 9\\ \end{array} \right)$

2. Reduce the matrix to an echelon matrix:

   Interchange the first and the third rows: $\left( \begin{array}{ccc|c} 3 & 2 & -5 & -1\\ 2 & -1 & 3 & 13\\ 1 & 2 & -1 & 9\\ \end{array} \right) \overset{r_1 \leftrightarrows r_3}{\longrightarrow} \left(\begin{array}{ccc|c} 1 & 2 & -1 & 9\\ 2 & -1 & 3 & 13\\ 3 & 2 & -5 & -1\\ \end{array}\right)$Subtract the first row multiplied by $2$ from the second one; subtract the first row multiplied by $3$ from the third one. Do this to zero all elements of the first column except for one. $\left( \begin{array}{ccc|c} 1 & 2 & -1 & 9\\ 2 & -1 & 3 & 13\\ 3 & 2 & -5 & -1\\ \end{array} \right) \overset{r_2 - 2r_1, r_3-3r_1}{\longrightarrow} \left(\begin{array}{ccc|c} 1 & 2 & -1 & 9\\ 0 & -5 & 5 & -5\\ 0 & -4 & -2 & -28\\ \end{array}\right)$Multiply the second row by $-\frac{1}{5}$ and the third one by$-\frac{1}{2 }$. $\left(\begin{array}{ccc|c} 1 & 2 & -1 & 9\\ 0 & -5 & 5 & -5\\ 0 & -4 & -2 & -28\\ \end{array}\right) \overset{r_2 \cdot( - \frac{1}{5}),r_3 \cdot( - \frac{1}{2})}{\longrightarrow} \left(\begin{array}{ccc|c} 1 & 2 & -1 & 9\\ 0 & 1 & -1 & 1\\ 0 & 2 & 1 & 14\\ \end{array}\right)$Subtract the second row multiplied by $2$ from the third one. $\left(\begin{array}{ccc|c} 1 & 2 & -1 & 9\\ 0 & 1 & -1 & 1\\ 0 & 2 & 1 & 14\\ \end{array}\right) \overset{r_3 - 2r_2}{\longrightarrow} \left(\begin{array}{ccc|c} 1 & 2 & -1 & 9\\ 0 & 1 & -1 & 1\\ 0 & 0 & 3 & 12\\ \end{array}\right)$Now multiply the last row by $\frac{1}{3}$ to get $1$ on the main diagonal. $\left(\begin{array}{ccc|c} 1 & 2 & -1 & 9\\ 0 & 1 & -1 & 1\\ 0 & 0 & 3 & 12\\ \end{array}\right) \overset{r_3\cdot\frac{1}{3}}{\longrightarrow} \left(\begin{array}{ccc|c} 1 & 2 & -1 & 9\\ 0 & 1 & -1 & 1\\ 0 & 0 & 1 & 4\\ \end{array}\right)$

   Here, you can simplify the augmented matrix even more! Zero all non-diagonal elements on the left-hand side by adding the third row to the second one and the first one; subtracting the second row multiplied by two from the first one. As a result, you get the following matrix: $\left( \begin{array}{ccc|c} 1 & 0 & 0 & 3\\ 0 & 1 & 0 & 5\\ 0 & 0 & 1 & 4\\ \end{array} \right)$

3. The next step is called back-solving. In this step, you construct the system of linear equations based on the augmented matrix obtained in the previous step. So, the system of linear equations is:$\begin{cases} x + 0\cdot y + 0\cdot z= 3\\0\cdot x+ y+ 0\cdot z = 5\\ 0\cdot x+0\cdot y+z = 4 \end{cases}$

The process is complete. Now it's clear that the solution is

$\begin{cases} x= 3\\ y = 5\\ z = 4 \end{cases}$

Linear equations system solutions

After a matrix reduction there may be several outcomes:

1. If after reduction to an echelon form the matrix is triangular, then there is a single solution. We got such a matrix in the example above. $\left(\begin{array}{ccc|c} 1 & 2 & -1 & 9\\ 0 & 1 & -1 & 1\\ 0 & 0 & 1 & 4\\ \end{array}\right)$

2. If the last row has more than one non-zero element, then the system has an infinite number of solutions. Like in the matrix below: $\left( \begin{array}{cccc|c} 3 & 2 & 6 & 4 & 4\\ 0 & 1 & 7 & 1 & 2\\ 0 & 0 & 4 & 2 & 9\\ \end{array} \right)$

3. If there are only zeros in at least one of the lower rows on the left-hand side of the augmented matrix, then there are two options. The first: the system has redundant equations. In that case, the last rows of both right-hand and left-hand sides of the augmented matrix will be zeros. Then such rows need not be considered and we obtain the number of solutions as in the previous paragraphs. For instance, take a look at the following matrix: $\left( \begin{array}{ccc|c} 3 & 2 & 6 & 4\\ 0 & 1 & 7 & 2\\ 0 & 0 & 4 & 9\\ 0 & 0 & 0 & 0\\ \end{array} \right)$

4. If one or more of the bottom rows has a zero on the left-hand side, but at least one corresponding element on the right-hand side is not zero, then the system will not have any solutions, for example:$\left( \begin{array}{ccc|c} 3 & 2 & 6 & 4\\ 0 & 1 & 7 & 2\\ 0 & 0 & 4 & 9\\ 0 & 0 & 0 & 8\\ \end{array} \right)$

Conclusion

In the end, we would like to say that knowledge and the ability to apply various methods of solving linear equation systems are important for solving a lot of mathematical problems. In this part, we've only studied the Gaussian method, which is considered a classic and rather simple method. Linear equation systems are everywhere, from different problems in mathematics and physics (a lot of difficult problems are regarded in linear approximation, which implies the transition to linear systems), to programming. Therefore, it is important to pay a lot of attention to this part.