Gaussian Elimination

Gaussian elimination is a systematic algorithm for solving systems of linear equations by converting the system into an augmented matrix and then applying row operations to reach a triangular form. Named after Carl Friedrich Gauss, it is the foundational method of linear algebra and the approach used by every computer algebra system in the world to solve linear systems.

Unlike substitution and elimination (which rely on intuition about which variable to isolate), Gaussian elimination is purely mechanical — follow the steps and you will always reach the answer, whether the system has one solution, no solution, or infinitely many solutions.

The Augmented Matrix

An augmented matrix is a compact way to write a system of equations. You strip away the variables and write only the coefficients and constants, separated by a vertical bar.

For the system:

$2x + 3y = 8$

$x - y = 1$

The augmented matrix is:

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

Each row represents one equation. The columns to the left of the bar correspond to the variable coefficients (first column is $x$, second is $y$), and the column to the right is the constants.

For a 3-variable system like:

$x + 2y - z = 3$

$2x - y + 3z = 7$

$-x + y + 2z = 4$

The augmented matrix is:

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

The Three Row Operations

You may perform exactly three operations on the rows of a matrix. These operations do not change the solution set of the system.

These are the only moves you need. Every Gaussian elimination problem uses some combination of these three operations.

Row Echelon Form (REF)

The goal of Gaussian elimination is to transform the matrix into row echelon form, where:

1. All nonzero rows are above any all-zero rows
2. The leading entry (called the pivot) of each nonzero row is to the right of the pivot in the row above
3. All entries below each pivot are zero

A 3x3 system in row echelon form looks like:

$\left[\begin{array}{ccc|c} \boxed{1} & * & * & * \\ 0 & \boxed{1} & * & * \\ 0 & 0 & \boxed{1} & * \end{array}\right]$

where $*$ represents any number. Once you reach this form, you solve by back-substitution — start with the bottom equation and work upward.

Reduced Row Echelon Form (RREF) — Gauss-Jordan

Gauss-Jordan elimination continues beyond REF to reduced row echelon form (RREF), where every pivot is 1 and every other entry in a pivot column is 0:

$\left[\begin{array}{ccc|c} 1 & 0 & 0 & a \\ 0 & 1 & 0 & b \\ 0 & 0 & 1 & c \end{array}\right]$

In RREF, the solution reads directly from the matrix: $x = a$, $y = b$, $z = c$. No back-substitution needed.

Worked Examples

Example 1: Solving a 2x2 System

Solve:

$2x + 3y = 8$

$x - y = 1$

Step 1 — Write the augmented matrix:

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

Step 2 — Swap rows to put a leading 1 in the top-left position ($R_1 \leftrightarrow R_2$):

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

Step 3 — Eliminate the entry below the pivot. Apply $R_2 - 2R_1 \to R_2$:

$\left[\begin{array}{cc|c} 1 & -1 & 1 \\ 0 & 5 & 6 \end{array}\right]$

Step 4 — Scale Row 2 ($\frac{1}{5}R_2 \to R_2$):

$\left[\begin{array}{cc|c} 1 & -1 & 1 \\ 0 & 1 & \frac{6}{5} \end{array}\right]$

This is row echelon form. Back-substitute: from Row 2, $y = \frac{6}{5}$. Substituting into Row 1: $x - \frac{6}{5} = 1$, so $x = 1 + \frac{6}{5} = \frac{11}{5}$.

Answer: $x = \frac{11}{5}$, $y = \frac{6}{5}$

To verify: $2\left(\frac{11}{5}\right) + 3\left(\frac{6}{5}\right) = \frac{22}{5} + \frac{18}{5} = \frac{40}{5} = 8$ and $\frac{11}{5} - \frac{6}{5} = \frac{5}{5} = 1$.

Example 2: Solving a 3x3 System

Solve:

$x + 2y - z = 3$

$2x - y + 3z = 7$

$-x + y + 2z = 4$

Step 1 — Write the augmented matrix:

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

Step 2 — Eliminate below the first pivot. Apply $R_2 - 2R_1 \to R_2$ and $R_3 + R_1 \to R_3$:

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

Step 3 — Scale Row 2 ($-\frac{1}{5}R_2 \to R_2$):

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

Step 4 — Eliminate below the second pivot. Apply $R_3 - 3R_2 \to R_3$:

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

Step 5 — Scale Row 3 ($\frac{1}{4}R_3 \to R_3$):

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

This is row echelon form. Now back-substitute:

From Row 3: $z = \frac{19}{10}$

From Row 2: $y - z = -\frac{1}{5}$, so $y = -\frac{1}{5} + \frac{19}{10} = -\frac{2}{10} + \frac{19}{10} = \frac{17}{10}$

From Row 1: $x + 2y - z = 3$, so $x = 3 - 2\left(\frac{17}{10}\right) + \frac{19}{10} = 3 - \frac{34}{10} + \frac{19}{10} = 3 - \frac{15}{10} = 3 - \frac{3}{2} = \frac{3}{2}$

Answer: $x = \frac{3}{2}$, $y = \frac{17}{10}$, $z = \frac{19}{10}$

Example 3: An Inconsistent System

Solve:

$x + y = 3$

$2x + 2y = 10$

Augmented matrix:

$\left[\begin{array}{cc|c} 1 & 1 & 3 \\ 2 & 2 & 10 \end{array}\right]$

Apply $R_2 - 2R_1 \to R_2$:

$\left[\begin{array}{cc|c} 1 & 1 & 3 \\ 0 & 0 & 4 \end{array}\right]$

Row 2 now reads $0x + 0y = 4$, which is $0 = 4$ — a contradiction. This system is inconsistent and has no solution. Geometrically, the two lines are parallel.

Example 4: A Dependent System with Free Variables

Solve:

$x + 2y - z = 1$

$2x + 4y - 2z = 2$

$-x - 2y + z = -1$

Augmented matrix:

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

Apply $R_2 - 2R_1 \to R_2$ and $R_3 + R_1 \to R_3$:

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

All three equations were multiples of the same equation. There is only one independent equation with three unknowns, so $y$ and $z$ are free variables. Let $y = s$ and $z = t$ (where $s$ and $t$ are any real numbers). Then from Row 1:

$x = 1 - 2s + t$

Answer: The system has infinitely many solutions: $(x, y, z) = (1 - 2s + t,\; s,\; t)$ for any real numbers $s$ and $t$.

Real-World Application: Electrical Circuit Analysis

An electrician analyzing a circuit with three loops writes Kirchhoff’s voltage equations:

$I_1 + 2I_2 - I_3 = 5$

$3I_1 - I_2 + 2I_3 = 10$

$-I_1 + I_2 + 3I_3 = 8$

where $I_1$, $I_2$, $I_3$ are loop currents in amps. Rather than juggling three equations by hand, the electrician writes the augmented matrix and applies Gaussian elimination — the same mechanical process regardless of how many loops the circuit has. For circuits with 10 or 20 unknowns (common in industrial work), Gaussian elimination is the only practical approach.

Common Mistakes

1. Applying a row operation to the wrong row. When you compute $R_2 - 3R_1$, the result replaces $R_2$, not $R_1$. The pivot row stays unchanged.
2. Forgetting to apply the operation to every entry. When you multiply a row by a constant or add a multiple of another row, every entry in the row (including the constant after the bar) must be updated.
3. Dividing by zero. If a pivot position contains 0, swap that row with a row below that has a nonzero entry in that column. If no such row exists, the variable is free.
4. Arithmetic errors with fractions. Gaussian elimination often produces fractions. Work carefully, or multiply a row by a convenient number to clear denominators before proceeding.

Practice Problems

Test your understanding with these problems. Click to reveal each answer.

Key Takeaways

• An augmented matrix separates coefficients from constants with a vertical bar, compactly representing a system of equations
• The three row operations (swap, scale, replace) transform a matrix without changing the solution set
• Row echelon form (REF) has zeros below each pivot — solve by back-substitution
• Reduced row echelon form (RREF) has zeros above and below each pivot — the solution reads directly
• A row of the form $[0 \; 0 \; \cdots \; 0 \mid c]$ with $c \neq 0$ signals an inconsistent system (no solution)
• A row of all zeros indicates a dependent equation — expect free variables and infinitely many solutions
• Gaussian elimination works for systems of any size and always terminates

Return to College Algebra for more topics in this section.