In this section, we are going to learn the way to solve linear equations using Gaussian elimination. We are also going to introduce special forms of matrix.
So what is Gaussian elimination? In short, it is an algorithm that will Always solve a linear system. If you follow the procedure, no matter how hard the linear systems are, you can solve it guaranteed.
Let’s go through a simple example:
We can write this in a matrix form:
To solve this as a high school student, you can try substitution or elimination.
Let’s use elimination! You will first make a choice of eliminating x or y. It is much easier to eliminate y, all you need is to add the first row to the second row and cancel out all the y:
then we substitute the result back to \((2)\):
So how to do the same thing in matrix form? The first step we do is to make this linear equation \(A\pmb{x} = \pmb{b}\) even easier. We will rewrite the equation to something we called Augmented matrix:
How do you “read” this notation? Well, think about the first column is the coefficients for x and the second column is the coefficients for y and the sum is given by the number after the bar.
We will see why this notation suits our purpose in a sec, now if we want to do the same thing as above, then how should we write it?
To write \( \color{red}{(1)}+ \color{red}{(2)}\), we can change the row \( \color{red}{(2)}\) to our new row \( \color{red}{(1)}+ \color{red}{(2)}\):
this change is so-called the row operation, or elementary row operation, There are in total three types of row operations. The first one is row addition, which is exactly what we did above, replacing one row to this row adding another row.
then what we did is to divide the new row by 3, in order to get $ x = 1 $. we will perform the same operation here:
And this is our next type of row operation, called row multiplication.
Now comes to the hard part, which is our “substitution”. In grade 9, these two methods: substitution and elimination were taught as different methods. But in here, we can see that both methods can be broken down into numbers of basic row operations.
What we did after we figured out the x is we plugged into the original equation \(\color{red}{(2)}\). But as you see, we don’t have the original equations anymore,, so we have to plug into the first one. How to do that? we can first remove all the x from the first equation by doing:
Next we can divide the first row by \(-1\) to get $y = $ something instead of $-y = $ something:
Basically, our job is done here. However, for simplicity, we would like to show \(x = 1\) first and then show \(y = 0\), so we can do the last type of row operation here, called the row switching:
Then, we can easily read the result just by looking at the rows.
Alright! We have learned the notation and row operation, now it is time to find out how to perform the Gaussian elimination. This method is not always the optimum one when you solve linear systems, but it is surely the one you can rely on when you have no clue how to start.
Let’s have a fairly simple example to show how this works.
As you can see, we have a system of equations with three unknowns. We started from the first row and we only care about the first number in the row. If this number is not \(1\), we will divide whatever this number is to make our first number to be \(1\).
In this case, we have that number already be \(1\) so we moved on to the next step.
The next step is to make the first number on the second row be \(0\). To do that, you will do a row addition(subtraction). The only row we will use is the first row since the first row already has the coefficient of x to be \(1\), we just need to subtract as many row 1 as we want to get the first number on the second row to be \(0\).
In this case, the first number on the second row is 1, so we need to subtract exactly one row 1 to row 2:
Now we do the similar thing as above, we check if the coefficient of the second number is \(1\) or not, if not, we will do a division to make this number be \(1\). Luckily, this time we get \(1\) again! So we don’t have to do anything.
You might already see the pattern here. The next step is to make sure that on the third row, we have \(0\) for both the first coefficient and the second one. To do that, we subtract different amounts of row 1 and row 2.
In our case, The first number for the third row is 1, which means that we need to subtract off one row 1:
Then we subtract out four row 2 since the second number of row 3 is now \(4\).
You might find that we can also divide the new row 3 by 4 and we immediately get what y is. But as I mentioned before, the Gaussian elimination is not always the easiest one, so we will follow the more general case.
we do the same thing again, now this time the leading coefficient is \(-4\), so we divide the row 3 by \(-4\):
Lovely, we are half-way there! As you can see, our matrix on the left now became a special shape with all diagonal terms to be \(1\) and the bottom left to be all zero. This type of matrix is what we called lower triangular matrix, but that is not our topic today so we won’t dig on too much.
The rest of the job is much easier than the first half, you will do the similar thing but work your way up this time. The goal is to have all diagonal terms to be \(1\) and the rest to be zero. To do that, we first subtract one row 3 to row 2 to get rid of that annoying \(1\) at the end of row 2:
Then we add one row 2 to row 1 and subtract one row 3 to row 1:
And we have our solution.
Sadly, you are not always getting a great answer like this. Just like if you are solving two linear equations, you might experience something like two parallel lines or two same lines. When you solve a linear system, a non-trivial solution is not always guaranteed.
Sometimes, you might end up with something like this:
Or this:
Don’t worry! You will see these cases in practice. We are not going to discuss these cases in detail.