In my previous article on understanding system of linear equations, I explained the basic meaning of system of linear equations. I also mentioned an example where the amount of resources needed to be calculated to produce products without waste. Because the example was trivial, the solution was easy to calculate. However, most of the times, this is not the case. Without any systematic approach, solving linear equations would take eternity.
Fortunately, there exists a logical approach to solve them: Gaussian Elimination method. Gaussian elimination is a technique where you reduce a system of equations and transform it into its simplified form. Putting the explanation in theory could be a bit confusing so let us directly dive into an example and analyze every step we perform.
Solving a system of linear equations using Gaussian elimination method
\(\begin{align*} & x – y + z = 8 \\ & 2x + 3y – z = -2 \\ & 3x – 2y – 9z = 9 \end{align*}\)
Gaussian elimination starts by writing the system of linear equations in the form of an augmented matrix. An augmented matrix consists only the coefficients of the variables. The constants on the write side of the equation are separated by a vertical line.
\(\left[\begin{array}{ccc|c}
1 & -1 & 1 & 8 \\
2 & 3 & -1 & -2 \\
3 & -2 & -9 & 9
\end{array}\right]
\)
The main aim in Gauss elimination is to reduce the equation to a row echelon form. A matrix is said to be in row echelon form if:
- the first non-zero coefficient in a row is 1 (also called leading coefficient),
- leading coefficient of a row (called pivot) is to the left of that in the next row,
- number of zeros of some row is always more than that in the row above. This makes the row with maximum number of zeros the last row in the matrix.
Moreover, the column carrying the pivot is called pivot column.You can read about row echelon form here. We will perform different operations to convert the matrix into row echelon form. As it is a good practice to go from bottom to top, we will start with the third row.
\(
\begin{equation} R_3 – 3*R_1 = R_3 \end{equation}
\)
The subscripts denote the number of row. This step will give us the following matrix.
\(
\left[
\begin{array}{ccc|c}
1 & -1 & 1 & 8 \\
2 & 3 & -1 & -2 \\
0 & 1 & -12 & -15
\end{array}
\right]
\)
Now that we have the first term as 0, we can proceed to do the same for the second row.
\(
\begin{equation} R_2 – 2*R_1 = R_2 \end{equation} \Rightarrow
\left[
\begin{array}{ccc|c}
1 & -1 & 1 & 8 \\
0 & 5 & -3 & -18 \\
0 & 1 & -12 & -15
\end{array}
\right]
\)
The third row already has 1 as the leading coefficient. For the matrix to be in row echelon form, this form is required in the second row. Hence, we will interchange the second and the third row with each other.
\(
\begin{equation} R_2 \leftrightarrow R_3 \end{equation} \Rightarrow
\left[
\begin{array}{ccc|c}
1 & -1 & 1 & 8 \\
0 & 1 & -12 & -15 \\
0 & 5 & -3 & -18
\end{array}
\right]
\)
Then,
\(
\begin{equation} R_3 – 5*R_2 = R_3 \end{equation}\Rightarrow
\left[
\begin{array}{ccc|c}
1 & -1 & 1 & 8 \\
0 & 1 & -12 & -15 \\
0 & 0 & 57 & 57
\end{array}
\right]
\)
Finally, dividing by 57 will lead us to row echelon form of the matrix.
\(
\frac{R_3}{57} = R_3 \Rightarrow
\left[
\begin{array}{ccc|c}
1 & -1 & 1 & 8 \\
0 & 1 & -12 & -15 \\
0 & 0 & 1 & 1
\end{array}
\right]
\)
The solution
The row echelon matrix above depicts the system of linear equations in simplified form. Thus, the new and simplified equations are:
\(
\begin{equation}
x-y+z=8\\
y-12z=-15\\
z=1
\end{equation}
\)
Solving these equations will give us \(x\) as 4, \(y\) as -3 and \(z\) as 1.