01 / 20

Gaussian
Elimination

Master the systematic method for solving systems of linear equations by transforming matrices into row echelon form.

Linear Algebra

What Is a System of Linear Equations?

A system of linear equations is a collection of two or more equations that share the same set of unknowns. For example:

$$ \begin{cases} 2x + y = 5 \\ x - 3y = -1 \end{cases} $$

The Augmented Matrix

Instead of writing equations repeatedly, we encode the system as an augmented matrix: coefficients on the left, constants on the right, separated by a vertical bar.

$$ \begin{cases} 2x + y = 5 \\ x - 3y = -1 \end{cases} \;\;\longrightarrow\;\; \left[\begin{array}{cc|c} 2 & 1 & 5 \\ 1 & -3 & -1 \end{array}\right] $$

Why Does This Matter?

Scalability
Works for systems with 2, 3, or even hundreds of equations: the same algorithm every time.
Foundational
Powers everything from computer graphics to machine learning to engineering simulations.
Diagnostic
Reveals whether a system has one solution, infinitely many, or no solution at all.

The Three Row Operations

These are the only moves you need. Each one transforms the matrix without changing the solution set:

1
Swap two rows: \( R_i \leftrightarrow R_j \)
2
Scale a row by a nonzero constant: \( R_i \to c \cdot R_i \), where \( c \neq 0 \)
3
Replace a row with itself plus a multiple of another: \( R_i \to R_i + c \cdot R_j \)

Row Echelon Form (REF)

The goal of forward elimination is to reach Row Echelon Form: a staircase of pivots descending left-to-right, with all zeros below each pivot.

$$ \left[\begin{array}{ccc|c} \color{#818cf8}{\boxed{2}} & 1 & -1 & 8 \\ 0 & \color{#818cf8}{\boxed{3}} & 2 & 1 \\ 0 & 0 & \color{#818cf8}{\boxed{-1}} & 3 \end{array}\right] $$
1
The leading entry (pivot) of each row is to the right of the pivot in the row above.
2
All entries below each pivot are zero.
3
Any all-zero rows sit at the bottom of the matrix.

REF vs RREF: Key Distinction

Row Echelon Form (REF) Reduced REF (RREF)
Zeros below pivot ✓ Yes ✓ Yes
Zeros above pivot ✕ Not required ✓ Yes
Pivots equal 1 ✕ Not required ✓ Yes
Solution method Back substitution Read directly
Named method Gaussian elimination Gauss-Jordan elimination

The Algorithm: Step by Step

1
Write the augmented matrix for the system.
2
Identify the pivot in column 1 (swap rows if the top-left entry is zero).
3
Eliminate below: use row replacement \( R_i \to R_i - \frac{a_{i1}}{a_{11}} R_1 \) to make all entries below the pivot zero.
4
Move to the next column and repeat for the sub-matrix below the current pivot.
5
Back substitute: starting from the last equation, solve upward for each variable.

The Process at a Glance

Write Augmented Matrix Find Pivot (Swap if needed) Eliminate Below Pivot REF Reached? Next column or done Repeat for next column Back Substitution Solve from bottom up Done Solution!

Example 1: A \(2 \times 2\) System

Solve the system: \(\begin{cases} x + 2y = 5 \\ 3x + 5y = 14 \end{cases}\)

$$ \left[\begin{array}{cc|c} 1 & 2 & 5 \\ 3 & 5 & 14 \end{array}\right] \xrightarrow{R_2 \to R_2 - 3R_1} \left[\begin{array}{cc|c} 1 & 2 & 5 \\ 0 & -1 & -1 \end{array}\right] $$

Example 2: A \(3 \times 3\) System

Solve: \(\begin{cases} 2x + y - z = 8 \\ -3x - y + 2z = -11 \\ -2x + y + 2z = -3 \end{cases}\)

$$ \left[\begin{array}{ccc|c} 2 & 1 & -1 & 8 \\ -3 & -1 & 2 & -11 \\ -2 & 1 & 2 & -3 \end{array}\right] $$

Example 2: Forward Elimination

$$ \left[\begin{array}{ccc|c} 2 & 1 & -1 & 8 \\ 0 & \frac{1}{2} & \frac{1}{2} & 1 \\ 0 & 2 & 1 & 5 \end{array}\right] \xrightarrow{R_3 \to R_3 - 4R_2} \left[\begin{array}{ccc|c} 2 & 1 & -1 & 8 \\ 0 & \frac{1}{2} & \frac{1}{2} & 1 \\ 0 & 0 & -1 & 1 \end{array}\right] $$

Special Case: No Solution

Sometimes elimination reveals a contradiction: a row like \( [0 \;\; 0 \;\; 0 \;|\; 5] \), which says \( 0 = 5 \). This means the system is inconsistent.

$$ \left[\begin{array}{cc|c} 1 & 2 & 3 \\ 0 & 0 & 5 \end{array}\right] \quad \Longrightarrow \quad \text{No solution!} $$

Special Case: Infinitely Many Solutions

If elimination produces a row of all zeros \( [0 \;\; 0 \;\; 0 \;|\; 0] \) (a dependent equation), there are free variables and infinitely many solutions.

$$ \left[\begin{array}{ccc|c} 1 & -1 & 2 & 3 \\ 0 & 1 & -1 & 1 \\ 0 & 0 & 0 & 0 \end{array}\right] $$

Common Mistakes

✕ Forgetting to Swap
If the pivot position is zero, you must swap with a row below that has a nonzero entry. Dividing by zero is undefined.
✕ Wrong Row Operation
Applying the operation to the wrong row (e.g., changing the pivot row instead of the target row). Always modify the row you want zeros in.
✕ Arithmetic Errors
Fraction mistakes during elimination are the most common source of wrong answers. Double-check every computation, especially signs.

Methods Compared

Gaussian Elim. Gauss-Jordan Cramer's Rule
Target form REF RREF Determinants
Back substitution? Yes No No
Handles \( n \) equations Any size Any size Small only
Detects no solution ✓ ✓ Limited
Efficiency \( O(n^3) \) \( O(n^3) \) \( O(n! \cdot n) \)

Question 1 of 5

Which of the following is not a valid elementary row operation?

Question 2 of 5

After applying \( R_2 \to R_2 - 2R_1 \) to the matrix \(\left[\begin{array}{cc|c} 1 & 3 & 7 \\ 2 & 8 & 18 \end{array}\right]\), what is row 2?

Question 3 of 5

A matrix in REF contains the row \( [\; 0 \;\; 0 \;\; 0 \;|\; 7 \;] \). What does this tell you about the system?

Question 4 of 5

Solve using Gaussian elimination: \(\begin{cases} x + y = 4 \\ 2x - y = 5 \end{cases}\). What is \( x \)?

Question 5 of 5

In the matrix below, the pivot in column 1 is zero. What should you do first? $$ \left[\begin{array}{ccc|c} 0 & 2 & 1 & 5 \\ 3 & -1 & 4 & 7 \\ 1 & 0 & -2 & 3 \end{array}\right] $$