Search for a command to run...
What is Gaussian Elimination and why is it a better choice for solving a system of linear equations (matrices). Explained with examples
I am a developer sharing the problems I solve through my blog. Just giving back to the community I learned so much from! Have an amazing day :)
No comments yet. Be the first to comment.
This series contains the fundamentals of linear algebra. Not so basic but Not so advanced!
What are Eigenvectors and Eigenvalues. Core concept explained with diagrams, graphs and examples
What are Eigenvectors and Eigenvalues. Core concept explained with diagrams, graphs and examples
What are matrix determinants and how to find them. Explained with examples and graphs
What is Linear Transformation in Matrices. An intuitive explanation with graphs and examples.
What is Matrix Inversion and how to compute them. Explained with examples: inversions for 2x2 and 3x3 matrices
Consider the following system of two simultaneous equations
$$\begin{array}{r} & 3a + b = 8 \quad...(1) \\ & a - 2b = 5 \quad...(2) \\ \end{array} $$
We can solve it by multiplying equation (1) by 2 and adding it to equation (2) as shown
$$\begin{array}{r} &6a + 2b = 16 \\ + &a-2b = 05 \\ \hline &7a = 21\\ \therefore&a = 3 \end{array}$$
Now that we have the values for "a" we can substitute it in the first equation
$$\begin{array}{r} & 3 \times 3 + b = 8 \\ \therefore& b = -1 \end{array}$$
That was pretty simple and quick but what if we need to solve for 3 simultaneous equations? Sure, we pick two equations, eliminate the common variable, and substitute the solution in the third one to find the answer. While this is doable, things get more complex as we increase the number of equations/variables to solve.
Gaussian Reduction is an efficient and less error-prone method to solve a system of linear equations. The goal here is to reach the Row Echelon form of the matrix. In this form, all the elements in the lower left triangle of a square matrix are zeros. In other words, all the elements in the upper right triangle and the diagonal are non-zero.
$$\begin{array} &\text{Row Echelon form} \\ \\ \begin{bmatrix} a & b & c & d \\ 0 & e & f & g \\ 0 & 0 & h & i \\ 0 & 0 & 0 & j \end{bmatrix} \end{array}$$
Before we solve an example, we need to look at the operations that we are allowed to be performed on the matrix.
Swapping of rows
Add non-scalar multiples of rows
Multiply rows by non-zero scalars
Consider the three equations below and find the solution using Gaussian Reduction
$$\begin{array}{r} & a + b + c = 2 \\ & 2a - b + c = -5 \\ & -a +3b + 3c = 18 \\ \end{array}$$
Now that we have established the goal and the rules, we are equipped to find the solution.
Rewrite the equations in matrix form with the coefficients of all the variables in a 3x3 matrix and constants in another 1x3 matrix as shown below.
$$\begin{bmatrix} 1 & 1 & 1 \\ 2 & -1 & 1 \\ -1 & 3 & 3 \end{bmatrix} \begin{bmatrix} 2 \\ -5 \\ 18 \end{bmatrix} \begin{array}{r} ...R_1 \\ ...R_2 \\ ...R_3 \end{array}$$
Rows have been labeled R1, R2 and R3 for convenience
Remember that we need to reach the row echelon form which means that, in our case, we need to make the first element of R2 and the first two elements of R3 as zeros. Let's start our calculations with that in mind.
We observe that adding R1 to R3 makes the first element of R3 zero and the matrix becomes...
$$= \begin{bmatrix} 1 & 1 & 1 \\ 2 & -1 & 1 \\ 0 & 4 & 4 \end{bmatrix} \begin{bmatrix} 2 \\ -5 \\ 20 \end{bmatrix} \begin{array}{l} \quad R_3 = R_3 + R_1 \ \end{array}$$
Note: You are allowed to perform any row operations at any time as you see fit. Here, operating on R3 first is entirely a personal choice
Next, we target the first element of R2 to become zero. To do so, we can multiply the R1 by 2 and subtract it from R2. The matrix then becomes...
$$= \begin{bmatrix} 1 & 1 & 1 \\ 0 & -3 & -1 \\ 0 & 4 & 4 \end{bmatrix} \begin{bmatrix} 2 \\ -9 \\ 20 \end{bmatrix} \begin{array}{l} \quad R_2 = R_2 - 2R_1 \ \end{array}$$
The only element that remains is the second element of R3. Now, it may seem tempting to just multiply R1 by 4 and subtract it from R3 but by doing so we are also reducing the third element of R3 to zero. Recall that in the row echelon form, the upper right triangle and the diagonal elements are supposed to be non-zero.
What we can do instead is add R2 with R3 which makes the two 4's as 1 and 3 respectively and then subtract R1 from R3 to make the required element zero.
However, there is a faster way to achieve this by multiplying R3 by 3 and R2 by 4 and then adding them up.
$$= \begin{bmatrix} 1 & 1 & 1 \\ 0 & -3 & -1 \\ 0 & 0 & 8 \end{bmatrix} \begin{bmatrix} 2 \\ -9 \\ 24 \end{bmatrix} \begin{array}{l} \quad R_3 = 3R_3 + 4R_2 \ \end{array}$$
And so we reach our goal of converting the matrix into the row echelon form.
But now what? Where is the answer?
The final step of the process is to reduce the row echelon matrix into an identity matrix. An identity matrix is a square matrix with all diagonal elements as 1 and the remaining elements as zeros. This is also known as the Reduced Row Echelon form.
$$\begin{array} &\text{Identity Matrix} \\ \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \end{array}$$
Note: The real goal of this method is to reduce the matrix into an identity matrix and the row echelon form is actually an important milestone in the process.
Resuming our journey, we aim to make the diagonal as 1's. Since the first element of R1 is already 1 we can simply divide R2 by -3 and R3 by 8.
$$= \begin{bmatrix} 1 & 1 & 1 \\ 0 & 1 & 1/3 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 2 \\ 3 \\ 3 \end{bmatrix} \begin{array}{l} \quad R_2 = R_2 / -3 \\ \quad R_3 = R_3 / 8 \\ \end{array}$$
To reduce the upper right triangle to zeros we can do the following steps...
$$= \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1/3 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} -1 \\ 3 \\ 3 \end{bmatrix} \begin{array}{l} \quad R_1 = R_1 - R_3 \end{array}$$
And then...
$$= \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} -3 \\ 2 \\ 3 \end{bmatrix} \begin{array}{l} \quad R_2 = R_3/3 - R_2 \\ \quad R_1 = R_1 - R_2 \end{array}$$
That's it! we have successfully reduced the original matrix into an identity matrix and the answers are in plain sight. We can convert the matrix back into its equation form like...
$$\begin{array}{l} & a + 0 + 0 = -3 \quad\therefore a = -3\\ & 0 + b + 0 = 2 \quad\quad\therefore b = 2\\ & 0 + 0 + c = 3 \quad\quad\therefore c = 3\\ \end{array}$$
It seems daunting at first to solve equations using this method as it involves writing the same matrix over and over again. But as you may have observed we can perform multiple row operations at the same time and reduce the number of substeps, as shown in step 3.
The great thing about a system of linear equations is that we can easily assess our answers by cross-checking our solution with the original equations and if they do not fit, we have made a mistake somewhere.
For a quick check, we can substitute the values in the first equation...
$$\begin{array}{r} & a + b + c = 2 \\ & -3 + 2 + 3 = 2 \\ & 2 = 2 \\ \end{array}$$
...and the math checks out!
This way we can be sure that our solution is correct
Thanks for reading! You can read the next article in the series which explains what are Eigenvectors and Eigenvalues
If this article has helped you, you can express your appreciation by reacting to this article. If you have any questions, comments, or constructive criticism please feel free to leave them in a comment below :)
Thanks again!