Gaussian Elimination (Row Echelon Method)

Gaussian elimination is the most general algorithm for solving systems of linear equations. It transforms the augmented matrix into row echelon form using elementary row operations, then applies back substitution to find the solution. It handles any system: unique solution, no solution, or infinitely many solutions.

Elementary Row Operations

Three operations preserve the solution set of a linear system:

Operation	Notation	Description
Row swap	Rᵢ ↔ Rⱼ	Exchange two rows
Row scaling	Rᵢ → k·Rᵢ	Multiply a row by a non-zero constant
Row replacement	Rᵢ → Rᵢ − k·Rⱼ	Subtract a multiple of one row from another

Forward Elimination Algorithm

Write the augmented matrix [A|b].
Identify the leftmost non-zero column (pivot column).
Move the row with the largest absolute value in that column to the top (partial pivoting).
For each row below the pivot, compute the multiplier k = aᵢ/aₚ and apply Rᵢ → Rᵢ − k·Rₚ.
Move to the next pivot position (next row and column) and repeat.
Continue until upper triangular form (row echelon form) is reached.

Interpreting the Final Matrix

Row pattern	Meaning
[0 0 … 0 \| c], c ≠ 0	No solution — system is inconsistent
[0 0 … 0 \| 0]	Free variable exists — infinitely many solutions
All pivots non-zero	Unique solution — proceed with back substitution

Worked Example 1 — 3×3 Unique Solution (Full Steps)

Solve: 2x₁ + x₂ − x₃ = 8, −3x₁ − x₂ + 2x₃ = −11, −2x₁ + x₂ + 2x₃ = −3

Initial: 2 - 3 - 2 1 - 1 1 - 1 22 8 - 11 - 3

Partial pivoting: |−3| > |2|, so swap R₁ ↔ R₂.

R_{1} \leftrightarrow R_{2} : - 3 2 - 2 - 1 11 2 - 1 2 - 11 8 - 3

R_{2} \to R_{2} - \frac{2}{- 3} R_{1} = R_{2} + \frac{2}{3} R_{1} : - 3 0 - 2 - 1 1/3 1 2 1/3 2 - 11 2/3 - 3

R_{3} \to R_{3} - \frac{- 2}{- 3} R_{1} = R_{3} - \frac{2}{3} R_{1} : - 3 00 - 1 1/3 5/3 2 1/3 2/3 - 11 2/3 - 25/3

R_{3} \to R_{3} - 5 R_{2} : - 3 00 - 1 1/3 0 2 1/3 - 1 - 11 2/3 - 9

Back substitution:

x_{3} = \frac{- 9}{- 1} = 9 (wait — let’s use a cleaner example below)

ℹThe calculator above shows every matrix state after each row operation. Enter any 3×3 system and click Solve to trace each step interactively.

Worked Example 1 — 3×3 Clean Example

Solve: x₁ + x₂ + x₃ = 6, 2x₁ + 3x₂ + x₃ = 10, x₁ + 2x₂ + 3x₃ = 14

12113211361014

R_{2} \to R_{2} - 2 R_{1}, R_{3} \to R_{3} - R_{1} : 100111 1 - 1 2 6 - 2 8

R_{3} \to R_{3} - R_{2} : 100110 1 - 1 3 6 - 2 10

Back substitution: x₃ = 10/3, x₂ = −2 + 10/3 = 4/3, x₁ = 6 − 4/3 − 10/3 = 6 − 14/3 = 4/3

ℹSolution: x₁ = 4/3, x₂ = 4/3, x₃ = 10/3. Verify: 4/3 + 4/3 + 10/3 = 18/3 = 6 ✓

Worked Example 2 — No Solution

System: x₁ + x₂ = 3, 2x₁ + 2x₂ = 7

[121237] R_{2} - 2 R_{1} [101031]

⚠Row 2 reads 0 = 1 — contradiction. The system has no solution.

Worked Example 3 — Infinitely Many Solutions

System: x₁ + 2x₂ = 4, 2x₁ + 4x₂ = 8

[122448] R_{2} - 2 R_{1} [102040]

ℹRow 2 is all zeros — x₂ is a free variable. The solution is x₁ = 4 − 2t, x₂ = t for any t ∈ ℝ.

Advantages of Gaussian Elimination

Property	Gaussian Elimination	Cramer's Rule
Time complexity	O(n³)	O(n! · n)
Handles all cases	Yes	D=0 gives no/infinite
Works for n > 4	Yes	Impractical
Shows row ops	Yes	No

Row Echelon Method Calculator — Solve 2×2 to 4×4 systems with full step display
Row Echelon Method Formula — Elimination formula and back substitution reference
Cramer's Rule — Determinant-based method for small systems

Frequently Asked Questions

Why use partial pivoting?

Partial pivoting moves the row with the largest absolute value in the pivot column to the top before elimination. This reduces rounding errors and prevents division by very small numbers that could amplify floating-point errors.

What is the difference between row echelon form and reduced row echelon form?

Row echelon form (REF) has zeros below each pivot. Reduced row echelon form (RREF) additionally has zeros above each pivot and each pivot equals 1. Gauss-Jordan elimination produces RREF; standard Gaussian elimination produces REF then uses back substitution.

Can Gaussian elimination solve underdetermined systems?

Yes. If there are fewer equations than unknowns (or some rows reduce to all zeros), free variables appear. The solution set is a subspace (a line, plane, etc.), and the algorithm can describe it parametrically.

What is the rank of a matrix?

The rank is the number of non-zero pivot rows in row echelon form. For an n×n system, if rank(A) = rank([A|b]) = n, there is a unique solution. If rank(A) < n, there are free variables.