1.1316 min read

Gaussian Elimination

Gaussian elimination is the fundamental algorithm for solving linear systems. It transforms any system into echelon form through a sequence of three types of row operations, each preserving the solution set.

Row Operation 1 (Permute): Swap two rows. Reordering equations doesn't change which tuples satisfy all of them.

Row Operation 2 (Scale): Multiply a row by a nonzero constant. We showed this preserves solutions in Section 1.3.

Row Operation 3 (Combine): Replace one row by itself plus a scalar multiple of another row. This is the key elimination step — used to zero out entries below a pivot.

The algorithm works column by column. Find a pivot in the current column, move it to the top (using permutation if needed), then eliminate all entries below it. Move to the next column and repeat.

Formal View

Theorem 1.13 — Row Operations Preserve Solutions

The following three row operations produce an equivalent system (same solution set): \begin{enumerate} \item Permute: Swap equations

i

and

j

. \item Scale: Replace equation

i

k

times equation

i

, for

k \neq 0

. \item Combine: Replace equation

i

by equation

i

plus

k

times equation

j

(for

j \neq i

). \end{enumerate}

Remark 1.13 — Complexity

Gaussian elimination on an

m \times n

system requires

O(mn^2)

arithmetic operations. For a square

n \times n

system, this is

O(n^3)

Interactive Visualization

Gaussian Elimination — Step by Step

Why This Matters

Gaussian elimination is the most widely used algorithm in scientific computing — directly or as a building block.

MATLAB's backslash operator (x = A\b) uses Gaussian elimination with partial pivoting
Finite element simulation of physical systems uses elimination to solve millions of equations
Cryptography and coding theory rely on elimination over finite fields
Every linear algebra library (LAPACK, Eigen, NumPy) implements variants of Gaussian elimination

Learning Resources

Gaussian elimination

MIT OpenCourseWare

The complete story of Gaussian elimination from Gilbert Strang.

47 min

Row reduction (Gaussian elimination)

Khan Academy

Step-by-step Gaussian elimination examples.

13 min

Quiz

Question 1

Which row operation is used to create zeros below a pivot in Gaussian elimination?

Question 2

Gaussian elimination always produces a unique solution.

Common Mistakes

Performing row operations on only the coefficient matrix, forgetting to update the right-hand side.
Using the wrong row as the pivot row — always use a row with a nonzero entry in the pivot column.
Confusing row operations (legal) with column operations (change the problem!) in elimination.