We've framed our central problem, Ax=b. We understand it from both the row and column perspectives. Now, we need a systematic, foolproof method for finding the solution vector x. That method is Gaussian Elimination.
This isn't about clever tricks or lucky guesses. This is an algorithm—a step-by-step mechanical process that will work on any system of linear equations, no matter how large. It is the computational backbone of linear algebra. The goal of Gaussian Elimination is simple: to make an intimidating system of equations progressively easier until the solution is obvious.
We do this by transforming our system into an upper triangular form. An upper triangular system is one where all the coefficients below the main diagonal are zero. Why? Because it's incredibly easy to solve.
Intimidating System
⎩⎨⎧2x+y+z=54x−6y=−2−2x+7y+2z=9
Easy (Upper Triangular) System
⎩⎨⎧2x+y+z=5−8y−2z=−12z=2
Look at that second system. You can see the solution just by looking at it! If z=2, you can plug that into the second equation to find y, and then plug both y and z into the first equation to find x. This easy, final step is called back substitution.
The Tools: Elementary Row Operations
The algorithm works by applying a set of three simple, "legal" moves called elementary row operations. These moves are guaranteed not to change the underlying solution of the system.
Swapping: You can swap any two rows. (This is like reordering your equations).
Scaling: You can multiply any row by a non-zero constant. (This is like multiplying both sides of an equation by a number).
Replacement: You can replace one row by adding to it a multiple of another row. (This is the workhorse of elimination).
The Augmented Matrix: A More Compact Notation
Writing out the x,y,z variables at every step is tedious. To make our work cleaner and more suitable for computers, we use a shorthand called an augmented matrix.
We simply take the coefficient matrix A and the result vector b and combine them, separated by a vertical line.
⎩⎨⎧2x+y+z=54x−6y=−2−2x+7y+2z=9
→
24−21−671025−29
Our goal is to use the row operations to turn the left side of this matrix into an upper triangular form.
The Algorithm in Action: Step-by-Step
Let's solve our system. Our strategy is to eliminate coefficients column by column, from top to bottom.
Our Starting Matrix:
24−21−671025−29
The first non-zero entry in the first row is called the pivot. Here, our first pivot is the `2` in the top-left corner. We will use this pivot to eliminate all the entries below it in the first column.
Step 1: Eliminate the `4` in Row 2.
Operation: R2→R2−2⋅R1.
20−21−871−225−129
Step 2: Eliminate the `-2` in Row 3.
Operation: R3→R3+R1.
2001−881−235−1214
Step 3: Eliminate the `8` in Row 3.
We have cleared the first column. Now we move to the next pivot, the `-8` in Row 2, and use it to eliminate everything below it.
Operation: R3→R3+R2.
2001−801−215−122
Our final matrix is in row echelon form. The left side is upper triangular. We have achieved our goal.
The Payoff: Back Substitution
Now we translate this matrix back into equations and solve from the bottom up:
⎩⎨⎧2x+y+z=5−8y−2z=−12z=2
We know z=2.
Plug z=2 into the second equation: −8y−2(2)=−12⇒−8y=−8⇒y=1.
Plug y=1 and z=2 into the first equation: 2x+(1)+(2)=5⇒2x=2⇒x=1.
The solution is x=1,y=1,z=2. Our solution vector is x=[1,1,2]. We have conquered the system.
Summary: The Universal Solver
Setup: Write the system as an augmented matrix.
Goal: Use row operations to transform the matrix into row echelon form (upper triangular).
Strategy: Use the pivot in each row to eliminate the entries below it, column by column.
Solve: Use back substitution on the simplified system.
This process will always work, and it lays the groundwork for understanding the deep structure of matrices, which we'll explore in the coming lessons.
Up Next: What happens when things don't go so smoothly? We will use Gaussian Elimination to analyze systems that have **no solution** or **infinitely many solutions**, and understand what these outcomes mean both algebraically and geometrically.