Welcome back! In our previous lesson, we established the fundamental tools for manipulating linear systems: elementary row operations. We saw how to swap, scale, and combine rows of an augmented matrix without altering the system's solution. However, applying these operations without a clear plan can be chaotic.
This lesson introduces the strategy you've been waiting for: Gaussian elimination. This is a powerful and systematic algorithm that uses elementary row operations to transform any matrix into a much simpler, standardized form known as row echelon form (REF). By the end of this lesson, you will be able to perform this procedure, turning a complex system of equations into an organized structure from which a solution can be easily extracted.
The Goal: Row Echelon Form
Before we learn the steps of the algorithm, we need to understand our destination. What is this "row echelon form" we're trying to reach? The name "echelon" comes from a French word for a step-like formation, and that's exactly what it looks like.
The following short video provides an excellent visual intuition for the "staircase" structure that defines row echelon form.
Row reduction, row-echelon form and reduced row-echelon form
In "Row reduction, row-echelon form and reduced row-echelon form," Lorenzo Sadun explains the concept.
Watch the segment from the beginning until the description of the staircase. Focus on the two key ideas: The first non-zero entry in any row, called a pivot, must be to the right of the pivots in the rows above it. Any rows that consist entirely of zeros must be at the bottom of the matrix.
Now that you have the visual idea, let's look at the formal definition. A matrix is in row echelon form if it satisfies three conditions.
1.3: Elementary Row Operations and Gaussian Elimination
This reading from Fundamentals of Matrix Algebra formally defines the properties of a matrix in row echelon form. Note that it's part of a larger definition for "reduced row echelon form," which we will cover in the next lesson. For now, we only need the first three conditions.
In the section under the heading "Definition: Reduced Row Echelon Form," please read the first three numbered conditions. These are the rules for a matrix to be in row echelon form.
To summarize, a matrix is in row echelon form (REF) if:
- The first nonzero entry in each non-zero row is a 1. This is called a leading 1.
- Each leading 1 is in a column to the right of the leading 1s in the rows above it (the "staircase" pattern).
- All rows consisting entirely of zeros are at the bottom of the matrix.
For example, this matrix is in row echelon form:
Notice the staircase of leading 1s. This structure is our goal.
The Algorithm: Gaussian Elimination (Forward Steps)
Gaussian elimination is the step-by-step process for getting any matrix into row echelon form. The part of the process that achieves REF is often called the forward steps or forward elimination. The core idea is to work from left to right, column by column, creating the leading 1s and then using them to create zeros below them.
Here is the general procedure:
- Find the Pivot: Start with the first column. Find the first row from the top with a non-zero entry in this column. This will be your pivot row. If you need to, swap this row with the top row.
- Create a Leading 1: Scale the pivot row so that its leading entry becomes a 1.
- Eliminate Below: Use the replacement operation to add multiples of the pivot row to all rows below it, creating zeros in the column underneath the leading 1.
- Repeat: Move down one row and to the right one column, and repeat the process. Ignore any rows you've already used as pivot rows. Continue until the entire matrix is in row echelon form.
This process is best understood through demonstration. The following video walks through a complete example, applying the row operations systematically to achieve row echelon form.
Gaussian Elimination & Row Echelon Form
The video "Gaussian Elimination & Row Echelon Form" by The Organic Chemistry Tutor provides a clear, step-by-step walkthrough.
Watch from the beginning to the end of the first example. Pay close attention to the strategy: First, use Row 1 to get zeros in the first column of Row 2 and Row 3. Next, use the new Row 2 to get a zero in the second column of Row 3. Finally, scale the rows to create the leading 1s.
This procedure ensures that you are always making progress toward the "staircase" shape without accidentally undoing the zeros you've already created.
A Worked Example
Let's solidify this by working through another example in text form. The logic is identical. We will take a system of equations, write its augmented matrix, and apply the forward steps of Gaussian elimination.
1.3: Elementary Row Operations and Gaussian Elimination
This resource provides another detailed example. It continues on to "reduced" row echelon form, but we will focus on the first part of the process.
Read through Example 1.3.2. Follow each row operation and see how it contributes to the overall goal. Specifically, notice the sequence: Create a leading 1 in row 1. Use it to create a zero below it. Move to the second row/column, create a leading 1 there. The zero below it is already there. Move to the third row/column and create the final leading 1. The matrix at the end of these "forward steps" is in row echelon form.
The process you just followed converts a system of equations into an augmented matrix and then systematically transforms it into row echelon form. The image below provides a great summary of this entire pipeline.
The Payoff: Solving by Back Substitution
Why is row echelon form so useful? Once a system's matrix is in REF, the solution is within easy reach. The last non-zero row gives you the value of one variable directly. You can then work your way back up the matrix, substituting this known value into the rows above to solve for the other variables. This process is called back substitution.
Let's see how this works with the final matrix from an example.
1.3: Elementary Row Operations and Gaussian Elimination
This reading demonstrates the power of row echelon form. After performing the forward steps, the author pauses to show how easily the system can now be solved.
Read the section for Example 1.3.5, starting from where the text says "Let's take a break here". This shows how converting the REF matrix back into equations allows you to solve for x_3, then x_2, then x_1.
As you can see, Gaussian elimination does the hard work of organizing the system, and back substitution is the simple process of reading the solution from that organized result.
Conclusion
In this lesson, we formalized our approach to solving linear systems by introducing a powerful, step-by-step algorithm. You now have a reliable method for tackling any system of linear equations.
Here are the key takeaways:
- Row Echelon Form (REF) is a "staircase" matrix form where leading entries are 1s, each leading 1 is to the right of the ones above it, and zero-rows are at the bottom.
- Gaussian elimination is the algorithm used to get a matrix into REF. It involves a sequence of "forward steps": working column-by-column to create leading 1s and then using them to create zeros below.
- Once a matrix is in REF, the corresponding system of equations can be solved efficiently using back substitution.
We have focused on the "forward steps" to reach row echelon form. In the next lesson, we will introduce the "backward steps." This will take us from row echelon form to an even simpler configuration called reduced row echelon form (RREF), where the solution can be read off directly without any back substitution at all.