Gaussian Elimination

Gaussian Elimination

Around three years ago, I was at my senior year in highschool. At that time, I would study after classes for my college entrance exams. I would study how to solve math word problems, such as mixtures, age, or work problems. These seemed easy for me, especially since I knew exactly how to go about and solve them. The trick was to interpret the given, create a system of equations, then solve the system using either a substitution or elimination technique. At that time, and up until the first semester of my third year in college, using the substitution and elimination techniques were the only tools I knew to use to solve systems of linear equations. I was surprised to discover more ways to write and solve systems of linear equations, thanks to CS130.

Today I will be imparting my knowledge about Gaussian Elimination, why you should appreciate it, and how you could use it to solve your (math) problems.

I. Rewriting System of Linear Equations (SLE’s)

Before I dwell on the meat of the Gaussian Elimination, I think it’s important that we first discuss how to rewrite a system of linear equations using matrices. I will assume that the reader has some background knowledge of what a matrix is/looks like, but don’t worry since I’ll be taking this step by step :)

Suppose we have a system of equations given below:

This is a system of two variables, x and y. We can rewrite this system using matrices as follows:

1. First, we take the coefficients of the variables, then place them in one row of the first matrix.
2. Next, we take the variables, then list them down in one column of the second matrix.
3. Last, we place the constant at the right side of the equation.

Having this form, we can now “squish” everything together so we will have the final form:

For Gaussian Elimination, we’ll need to use the “Augmented Form” of the equation above. This is just a fancy way of saying “join the coefficients with the answers.” Basically, take the matrix at the right of the equals sign, augment it to our coefficient matrix, then add a line to separate them. Easy.

We should now have this as our final, augmented form:

Voila! You can now express a system of linear equations using matrices!

Note: In this example, our system was in terms of two variables x and y. But, we can extend this to three or more variables, where we’d just have more rows and columns in our matrices.

II. Elementary Row Operations (ERO’s)

We are getting close to the Gaussian Elimination, but before that we need to know the Elementary Row Operations, or ERO’s. There are three of them, and trust me when I say that you should get to know and memorize them (these things will keep popping up in future CS130 lessons as well!). Fortunately, they aren’t too difficult to memorize either. The ERO’s are:

R here represents a row in our augmented matrix.

• The first ERO is the switching of rows.
• The second ERO is the multiplication of a row by a scalar.
• The third ERO is the elimination of a row entry. (We’ll be using this a lot)

Finally, it is important to take note of the following theorem:

“Any ERO performed on the augmented matrix form of a System of Linear Equation will give an equivalent System of Linear Equation.”

Basically this tells us that no matter how many ERO’s we perform on an augmented matrix, we will still end up with an equivalent solution to our system of linear equations. Awesome!

III. Row Echelon Form (REF)

We are almost at the Gaussian Elimination! This is the final thing we need to know to be able to use the GE technique.

The Row Echelon Form is simply a special kind of form of a matrix. It’s properties are as follows:

1. The leading non zero entry from the left for each row is a “1.”
2. Each leading 1 of a row is to the right of the leading 1 of the row above
3. All zero rows are at the bottom

And there you have it, we are finally ready to do the Gaussian Elimination!

IV. The Gaussian Elimination

After learning all of the prerequisites, the Gaussian Elimination is actually quite simple.

The main idea is:

1. Write the system of linear equations in an Augmented Matrix Form
2. Perform ERO’s on the matrix until it is in Row Echelon Form
3. Perform Backsubstitution to get the values of the unknowns
4. Done!

Easy, right? For me, the best way to learn is through practice, so we’ll be tackling some basic examples in the next part :)

V. Applications/Examples

Suppose we have a system of linear equations with 3 variables: x , y, and z.

Let’s subdue our instinct to use the substitution method for solving this system, and instead try to use our newly learned Gaussian Elimination!

The first thing we will do is express the system using matrices.

After doing so, we can now get the Augmented Form.

Now, we will start using our EROs to turn our augmented matrix into the Row Echelon Form (REF).

The first thing we do is swap row 1 and row 2, so that we can conveniently have the leading 1 at row 1.

Next, we are going to use ERO 3 to “eliminate” the values under that leading 1. This is needed so we can get the REF.

Next, we will use ERO 2 on row 3 to cancel out the negative sign, then we will use ERO 1 to swap it to row 2.

We gotta eliminate that -5 over there, so we will use ERO 3 again.

Finally, we will turn that 8 to 1 using ERO 2.

Awesome! We now have the REF! Now all we have to do is perform the easiest part: Back-substitution.

Using the REF, we can get the following equations. It is called “backsubstitution” because we have the value for z, now we will substitute that value back upwards to get y and x.

After performing the necessary algebraic substitutions, we now have our values!

VI. Conclusion

The Gaussian Elimination is a cool way to solve systems of linear equations using matrices. Admittedly, the Gaussian Elimination is only one of the many methods one can use to solve SLEs. In our CS130 class, we tackled 5 methods, namely the Gaussian Elimination, Gauss-Jordan Elimination, Triangular Factorization, Cramer’s Rule, and by using Inverse Matrices. Each method has its pros and cons. For me the pros and cons of Gaussian Elimination are as follows:

Pros: Easiest to learn, Easiest to do by hand, Intuitive

Cons: Slow for a computer (LU Factorization is faster), Gets complex the more variables in the system of equations.

At the end of the day, the Gaussian Elimination still has a special place in my CS130 memory, it being the first cool thing I learned in that class. :)

by Manolo Hernandez and Ken Tabagan