Linear Algebra (Pt. 3): Gaussian Elimination

Reference

18.06 - Lecture 2

Do consider watching this video first for general conception. It is a good 48 minutes investment of your time (1.5x speed it should only take < 32 minutes) 🐱‍👤.

Next, watch this video from a teaching assistant after the previous as she explains it more directly.

Note that both Strang and TA discussed elimination to only obtain till the upper triangular form (u) or otherwise the Row Echelon Form (REF), while there still exists a Reduced Row Echelon Form (RREF). The latter RREF as compared to REF, is an unique expression of a system, and is thus not subjective to any algorithms used for its computation.

Gaussian Elimination

"Gauss thought of it (elimination) first only because he was born earlier... it's a natural idea... and yea he died earlier too."

Salty Gil Strang, 18.06, Lecture 2

Despite it being brutal, this method was used (did not prove it) by Chinese Mathematician in circa 179 AD 😲. Thus, there may be truth in Strang's statement that this may not be very complicated.

Carl Friedrich Gauss

As mentioned, the goal of the Gaussian Elimination is to get to REF. The "E" (Echelon) in REF means "stairs" in French, and we should eventually get a "diagonal staircase" separating to both upper and lower-triangles. We will discuss its reason at the end.

To do so, there are two steps:

1. Forward-Elimination

2. Back-Substitution

Forward Elimination

The bulk of the work of Gaussian Elimination occurs in this step. Given for example a 3x3 problem, we can easily express it in row shorthand as discussed before.

3x3 Row Shorthand

We'll firstly focus on applying the mechanics on Matrix A only to go through its logic, before performing it along with Matrix b.

The idea behind is to pivot a row at a time (which is an equation), and reduce all other elements in its columns (variables) to 0.

Step 1 :

Eliminating (2, 1)

To do so, we

1. Firstly pivot (1, 1), and thus all coefficients in the pivoted row will remain the same, while

2. We multiply row 1 by 3, in order to achieve 0 for (2, 1) after subtracting row 2 with the computed values.

After this juncture, we would supposedly proceed to eliminate (3, 1), but however the column is fortunately decorated with 0s below its pivoted element (1, 1).

Hence, after this rigorous step, we have successfully eliminated the unknown "x" (column) in all other equations (rows), but for the first equation 🎉🎊.

Step 2 :

There is actually no step 2, it is just a repeat of step 1 (LOL) 🤩.

Eliminating (3, 2)

Since row 1 is cleared, we go down the "staircase" and pivot for the element (2, 2). Let us repeat the logic once again. We

1. Would retain row 2 coefficients, for the pivoted element is (2, 2), and

2. Multiply row 2 by 2, in order to achieve 0 for (3, 2) after subtracting row 3 with the computed values.

Step... Done :

Err yea... but we are truly done with the hard work here. The reason being: there is no point pivoting (3, 3) for there are no rows below to disturb with.

You would observe for a fact that the matrix has only coefficients in a upper-triangular form (u). The upper-triangular form is essentially REF, in which equations have a reducing amount of unknowns in each of them (which makes it super easy to solve). This is also thus the technique used by computers to solve linear algebra. Hence, it is also of interest for mathematicians and data scientists to get from "A" to "u" as quickly as possible (prolly this is the next topic on algorithms).

Incorporate "b"

The reason why this was excluded out of the exercise earlier, as it was not helpful for understanding. The RHS (Matrix b) is simply dragged along the operation for each individual row.

From "A", "b" to "u", "c"

As shown in the red font, the RHS (Matrix b) coefficients simply follows the calculation as would the other columns to derive the final form of Matrix c.

Backward Substitution

This part is truly the joy of doing math in Secondary School (for it is so easy) for approximately 1 lesson before we move on to more difficult problems.

Firstly, we re-create the system of linear equations with the coefficient and result matrix in REF.

Backward Substitution (Pt. 1)

For the 3rd equation (row) has only 1 unknown (column), the equation is easy to solve (not by chance but by design 🧠).

$$5z = -10\\ z = -2$$

With this value, we can perform backward substitution by substituting this value to equation (row) 2 to find y.

$$2y-2z=6\\ 2y-2(-2) =6\\ 2y=2\\ y=1$$

We repeat the following to find x.

$$x+2y+z=2\\ x+2(1)+(-2)=2\\ x=2$$

Hence, we derive the following results.

Backward Substitution (Pt. 2)

I hope you were able to see the entire point of converting into REF. It made equation 3 and the finding of unknown z extremely easy to solve, and the subsequent unknowns were similarly solvable via the same algorithm.

Recap

Now that you are slightly exposed to the algorithm of Gaussian Elimination, doing a comparison via a table may be more helpful to crystallize that understanding.

Forward Elimination

System of Linear Equation	Augmented Matrix
$x+2y+z=2\\ 3x+8y+z=12\\ 4y+z=2$	$\left[\begin{array}{cc} 1 & 2 & 1 && 2\\ 3 & 8 & 1 && 12\\ 0 & 4 & 1 && 2 \end{array}\right]$
$x+2y+z=2\\ 2y-2z=6\\ 4y+z=2$	$\left[\begin{array}{cc} 1 & 2 & 1 && 2\\ 0 & 2 & -2 && 6\\ 0 & 4 & 1 && 2 \end{array}\right]$
$x+2y+z=2\\ 2y-2z=6\\ 5z=-10$	$\left[\begin{array}{cc} 1 & 2 & 1 && 2\\ 0 & 2 & -2 && 6\\ 0 & 0 & 5 && -10 \end{array}\right]$

Elimination Matrices

I don't know about you, but I feel like we were sorta playing cheat while performing forward elimination. I mean, can we truly subtract the multiplication of a row while keeping the other rows intact? I mean Gauss would not forbid it, but it still does not make it feel right.

However, what is we were to legally multiply a matrix to eliminate the element (2, 1) instead? Thus, what would be the matrix required to eliminate the element (2, 1)?

To do this, it may be helpful to recap what we have learnt previously in types of matrix and Matrix-Matrix Multiplication $(M^3$lol) operation.

As we are only interested in removing changing (2, 1) to 0, identity matrix is extremely helpful.

Next, we know that the output (2, 1) is a result of the multiplication between the 2nd row of the left-matrix and 1st column of the right-matrix.

Hence, to put 2 and 2 together, we would need to change some values in the 2nd row of the identity matrix.

E21

We would call this Elimination Matrix to rid of element (2, 1)$E_{\mathrm{21}}$. You may also ask how would we get to know to slot in the value -3 into the identity matrix to eliminate (2, 1). We would have done so as like how it was done previously, to "multiply row 1 by 3, and subtract row 2 with its computed values".

Now, try to test yourself what would be $E_{\mathrm{32}}$before revealing the answer 😀.

Question

What is E32?

Answer

E32

We would slot in the value -2, as we would have multiplied row 2 with 2, and subtract row 3 with its computed values.

Significance

You might think if the whole point of Elimination Matrix was to only prove Gaussian Elimination is legit, it is actually not very important 😥. It is not! By establishing the above, we have essentially established:

$$E_{\mathrm{32}} \times E_{\mathrm{21}} \times A = u$$

This is crucial as this implies that out there, there is one such matrix, such that this "one elimination matrix" is able to quickly transform Matrix A to u in one-step. This such matrix is essentially $E{\mathrm{32}} \times E{\mathrm{21}}$(you can try computing this out to practice MM, but it is not very meaningful as it is not reproducible lol).

Do also gently be reminded that the above equation still follows MM properties; despite it being associative (you can put a parentheses between any factors), it is non-commutative (positions of factors cannot be switched without changing its results).