Gaussian Elimination

The Master Algorithm

We've framed our central problem, Ax=bAx = b. We understand it from both the row and column perspectives. Now, we need a systematic, foolproof method for finding the solution vector xx. 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\begin{cases} 2x + y + z = 5 \\ 4x - 6y = -2 \\ -2x + 7y + 2z = 9 \end{cases}
Easy (Upper Triangular) System
{2x+y+z=5−8y−2z=−12z=2\begin{cases} 2x + y + z = 5 \\ \quad -8y - 2z = -12 \\ \quad \quad \quad z = 2 \end{cases}

Look at that second system. You can see the solution just by looking at it! If z=2z=2, you can plug that into the second equation to find yy, and then plug both yy and zz into the first equation to find xx. 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.
  1. Swapping: You can swap any two rows. (This is like reordering your equations).
  2. Scaling: You can multiply any row by a non-zero constant. (This is like multiplying both sides of an equation by a number).
  3. Replacement: You can replace one row by adding to it a multiple of another row. (This is the workhorse of elimination).
The Algorithm in Action: Step-by-Step
We'll solve our system using an augmented matrix to keep our work clean. The goal is to get the left side into an upper triangular form, called row echelon form.

Step 1: Start with the Augmented Matrix

The first non-zero entry in the first row is our pivot. We will use this pivot (the 2) to eliminate all the entries below it.

[21154−60−2−2729]\left[\begin{array}{ccc|c} \mathbf{2} & 1 & 1 & 5 \\ 4 & -6 & 0 & -2 \\ -2 & 7 & 2 & 9 \end{array}\right]

Step 2: Eliminate below the first pivot

Operation 1: R2→R2−2⋅R1R_2 \rightarrow R_2 - 2 \cdot R_1.

Operation 2: R3→R3+R1R_3 \rightarrow R_3 + R_1.

[21150−8−2−1208314]\left[\begin{array}{ccc|c} 2 & 1 & 1 & 5 \\ 0 & \mathbf{-8} & -2 & -12 \\ 0 & 8 & 3 & 14 \end{array}\right]

Step 3: Eliminate below the second pivot

We move to the next pivot (the -8) and eliminate everything below it.

Operation: R3→R3+R2R_3 \rightarrow R_3 + R_2.

[21150−8−2−120012]\left[\begin{array}{ccc|c} 2 & 1 & 1 & 5 \\ 0 & -8 & -2 & -12 \\ 0 & 0 & \mathbf{1} & 2 \end{array}\right]

We have achieved row echelon form!

Step 4: 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\begin{cases} 2x + y + z = 5 \\ \quad -8y - 2z = -12 \\ \quad \quad \quad z = 2 \end{cases}
  1. We know z=2z = 2.
  2. Plug into row 2: −8y−2(2)=−12⇒y=1-8y - 2(2) = -12 \Rightarrow y = 1.
  3. Plug into row 1: 2x+(1)+(2)=5⇒x=12x + (1) + (2) = 5 \Rightarrow x = 1.

The solution is x=1,y=1,z=2x=1, y=1, z=2. Our solution vector is x=[1,1,2]x = [1, 1, 2].

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.
Previous
Lesson 2.1: Framing the Problem: Ax=b
Next
Lesson 2.3: The Solutions to Ax=b