Systems of Linear Equations — Gaussian Elimination

⚡ Key Takeaways

Gaussian elimination is a systematic algorithm for solving systems of linear equations by transforming the augmented coefficient matrix into row echelon form using elementary row operations, then back-substituting. Key result: any linear system has either no solution, exactly one solution, or infinitely many; the algorithm detects which case occurs and produces all solutions. Applies to: any $m \times n$ linear system over a field. Origin: named for Carl Friedrich Gauss (early 1800s), though the method appears in Chinese mathematics by ~150 BCE.

💡 The Core Insight

Replacing an equation by a combination of itself and other equations in the system does not change the solution set, as long as the operation is reversible. Gaussian elimination exploits this to strategically zero out coefficients one column at a time, manufacturing a staircase ("echelon") structure where each successive equation involves fewer unknowns — until the last reveals one variable directly, and the rest unravel by substitution.

DefinitionLinear System and Augmented Matrix

A system of $m$ linear equations in $n$ unknowns $x_1, \dots, x_n$ over a field $\mathbb{F}$ (usually $\mathbb{R}$ or $\mathbb{C}$ ) is:

1

\quad \sum_{j=1}^{n} a_{ij}\, x_j = b_i, \qquad i = 1, \dots, m

Derivation hint: each row $i$ collects the coefficients $a_{ij}$ multiplying the unknowns; $b_i$ is the constant term. In matrix form this is $A\mathbf{x} = \mathbf{b}$ , where $A = (a_{ij}) \in \mathbb{F}^{m\times n}$ is the coefficient matrix, $\mathbf{x} \in \mathbb{F}^n$ , and $\mathbf{b} \in \mathbb{F}^m$ . The augmented matrix is

2

\quad [\,A \mid \mathbf{b}\,] = \left[\begin{array}{ccc|c} a_{11} & \cdots & a_{1n} & b_1 \\ \vdots & & \vdots & \vdots \\ a_{m1} & \cdots & a_{mn} & b_m \end{array}\right]

Derivation hint: append the constant vector $\mathbf{b}$ as an extra column so row operations act on coefficients and constants together. A solution is $\mathbf{x}$ satisfying [1]; the set of all solutions is the solution set.

DefinitionElementary Row Operations

The three elementary row operations (EROs) on a matrix are: 1. Swap rows $R_i \leftrightarrow R_j$ . 2. Scale a row by a nonzero scalar $c$ : $R_i \to cR_i$ , $c \ne 0$ . 3. Replace a row by itself plus a multiple of another: $R_i \to R_i + cR_j$ ( $i \ne j$ ). Each ERO corresponds to left-multiplication by an invertible elementary matrix $E$ , so applying it to $[A \mid \mathbf b]$ yields $[EA \mid E\mathbf b]$ .

DefinitionRow Echelon Form (REF) and Reduced REF

A matrix is in row echelon form if:

All zero rows are at the bottom.
The leading nonzero entry of each row (the pivot) is strictly to the right of the pivot in the row above.

It is in reduced row echelon form (RREF) if additionally every pivot equals $1$ and is the only nonzero entry in its column. The columns containing pivots are pivot columns; the corresponding unknowns are basic variables, and the rest are free variables.

TheoremInvariance of the Solution Set

If $[A' \mid \mathbf{b}']$ is obtained from $[A \mid \mathbf{b}]$ by a sequence of elementary row operations, then the systems $A\mathbf{x} = \mathbf{b}$ and $A'\mathbf{x} = \mathbf{b}'$ have exactly the same solution set.

TheoremRouché–Capelli / Consistency

The system $A\mathbf{x}=\mathbf{b}$ is consistent (has a solution) if and only if

3

\quad \operatorname{rank}(A) = \operatorname{rank}([\,A \mid \mathbf b\,]).

Derivation hint: an inconsistent system reveals a pivot in the augmented column — a row $[\,0\ \cdots\ 0 \mid c\,]$ with $c \ne 0$ — which raises the augmented rank above the coefficient rank. When consistent, with $r = \operatorname{rank}(A)$ :

if $r = n$ , the solution is unique;
if $r < n$ , there are infinitely many solutions parametrized by $n - r$ free variables (over an infinite field).

ProofInvariance of the solution set under EROs

We show each ERO preserves solutions; since each is reversible, no solutions are gained or lost.

Step 1 — Setup. Let $\mathbf{x}^*$ satisfy $A\mathbf{x}^* = \mathbf{b}$ , i.e. every scalar equation [1] holds.

Step 2 — Swap. Reordering equations does not change which assignments satisfy them all. Solution set unchanged. Reverse: swap again.

Step 3 — Scale. Replace equation $i$ by $c \cdot (\text{eqn } i)$ , $c \ne 0$ :

4

\quad \sum_j a_{ij} x_j = b_i \iff \sum_j (c\,a_{ij}) x_j = c\,b_i \quad (c \ne 0).

Derivation hint: multiplying both sides of a true equation by nonzero $c$ keeps it true, and dividing by $c$ recovers the original — equivalence in both directions.

Step 4 — Replacement. Replace equation $i$ by (eqn $i$ ) $+\,c\,$ (eqn $j$ ). If $\mathbf{x}^*$ satisfies both equations $i$ and $j$ , then

5

\quad \Big(\sum_k a_{ik}x_k^* - b_i\Big) + c\Big(\sum_k a_{jk}x_k^* - b_j\Big) = 0 + c\cdot 0 = 0,

Derivation hint: add zero ( $=$ eqn $j$ residual) scaled by $c$ to zero ( $=$ eqn $i$ residual); the new equation is also satisfied. Subtracting $c\cdot$ (eqn $j$ ) reverses it. so the new equation holds. Conversely, given the new system, subtract $c\cdot$ (eqn $j$ ) to recover the original. Equation $j$ is untouched throughout.

Step 5 — Conclusion. Each operation and its inverse are EROs, so the solution sets of the original and transformed systems coincide. $\blacksquare$

∎

ProofTermination and existence of REF

Step 1. Find the leftmost column with a nonzero entry. Swap a row with a nonzero entry into the top position; call this entry the pivot.

Step 2. Use replacement operations $R_i \to R_i - (a_{i,\text{pivot}}/\text{pivot})R_{\text{top}}$ to zero all entries below the pivot in that column.

Step 3. Ignore the pivot row and column; recurse on the smaller submatrix below-right.

Step 4. Each step fixes one more pivot and shrinks the active submatrix; the process halts after at most $\min(m,n)$ pivots, yielding REF. Continuing upward (clearing above pivots and scaling) gives RREF, which is unique for a given matrix. $\blacksquare$

∎

mathematician · Carl Friedrich Gauss | 1777–1855

Gauss developed the elimination method around 1809–1810 while computing the orbit of the asteroid Pallas by least squares — he needed to solve the resulting normal equations, a large symmetric system. He described the systematic reduction in his work on celestial mechanics, and the notation/method was later formalized by the geodesist Wilhelm Jordan (giving "Gauss–Jordan" for full reduction to RREF). Ironically Gauss never claimed it as new; he treated it as routine arithmetic. The "Gaussian" name spread through 20th-century numerical analysis, particularly after the algorithm's role in early electronic computation was studied by Alan Turing, John von Neumann, and Herman Goldstine in the 1940s.

🧠 Intuition

Think of each equation as a constraint slab in $n$ -dimensional space — a hyperplane. Solving the system means finding the intersection of all these hyperplanes. Gaussian elimination is the act of replacing the tangle of slabs with an equivalent, neatly stacked one where the constraints decouple: the last equation pins down one variable, the second-to-last then pins down another given the first, and so on. The "staircase" of REF is geometrically the statement that you've untangled the constraints into a triangular cascade. Free variables are directions along which no constraint bites — the solution can slide freely, generating a line, plane, or higher flat. A contradictory row $0 = c$ (with $c\ne 0$ ) means the slabs have no common point — like three lines in a plane forming a triangle that never meet at one spot.

Figure

Reducing an augmented matrix to row echelon form: pivots form a descending staircase

ExampleUnique solution — a 3×3 system

Given:

2x + y - z = 8,\qquad -3x - y + 2z = -11,\qquad -2x + y + 2z = -3.

Step 1 — Augmented matrix:

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

Step 2 — Eliminate below pivot $2$ (col 1). $R_2 \to R_2 + \tfrac32 R_1$ , $R_3 \to R_3 + R_1$ :

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

Step 3 — Eliminate below pivot $\tfrac12$ (col 2). $R_3 \to R_3 - 4R_2$ :

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

Step 4 — Back-substitute.

Row 3: $-z = 1 \Rightarrow z = -1$ .
Row 2: $\tfrac12 y + \tfrac12(-1) = 1 \Rightarrow y = 3$ .
Row 1: $2x + 3 - (-1) = 8 \Rightarrow 2x = 4 \Rightarrow x = 2$ .

Answer:

\boxed{(x,\,y,\,z) = (2,\ 3,\ -1)}

ExampleInfinitely many solutions — a free variable

Given:

x + 2y + 3z = 6,\qquad 2x + 4y + 8z = 14,\qquad 3x + 6y + 11z = 20.

Step 1 — Augmented matrix and elimination. $R_2 \to R_2 - 2R_1$ , $R_3 \to R_3 - 3R_1$ :

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

Step 2 — $R_3 \to R_3 - R_2$ :

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

Pivot columns: 1 and 3. Free variable: $y = t$ .

Step 3 — Back-substitute.

Row 2: $2z = 2 \Rightarrow z = 1$ .
Row 1: $x + 2t + 3(1) = 6 \Rightarrow x = 3 - 2t$ .

Answer (parametric form):

\boxed{(x,\,y,\,z) = (3 - 2t,\ t,\ 1),\quad t \in \mathbb{R}}

A one-parameter family — a line in $\mathbb{R}^3$ .

⚠️ Pitfalls

Forgetting the augmented column. Every row operation must act on $\mathbf{b}$ too. Operating only on $A$ silently changes the system.
"More equations means a unique solution." Not so. Redundant equations (like Example 2) collapse to zero rows; $m \ge n$ does not guarantee uniqueness.
Dividing by zero pivots. If a pivot position holds $0$ , you must swap in a nonzero row first — never scale by an undefined reciprocal.
Confusing REF and RREF. REF suffices for back-substitution; full RREF is unnecessary work unless you need the inverse or a canonical form. RREF is unique; REF is not.
Reading consistency wrong. A row $[\,0\ 0\ 0 \mid 5\,]$ means $0 = 5$ — inconsistent. A row $[\,0\ 0\ 0 \mid 0\,]$ is harmless (a redundant equation).

CounterexampleOrder of operations changes numerical accuracy

In exact arithmetic the pivot choice never affects the answer. But consider, in floating-point with ~3 significant digits:

\begin{aligned} 0.0001\,x + y &= 1,\\ x + y &= 2. \end{aligned}

Using the tiny $0.0001$ as pivot, $R_2 \to R_2 - 10000\,R_1$ gives $y \approx 10000$ , $x \approx 0$ after rounding — catastrophically wrong (true: $x \approx y \approx 1$ ). Swapping rows first (partial pivoting, choosing the largest-magnitude pivot) recovers the correct answer. So "any nonzero pivot works" is false in practice — pivot magnitude controls error amplification.

connection

Gaussian elimination is the computational core linking many topics. The pivot count is the Matrix Rank, and the existence of a contradictory row is the Rouché–Capelli Theorem in action. The forward-elimination multipliers and pivots assemble into the LU Decomposition $A = LU$ , which lets you re-solve $A\mathbf{x}=\mathbf{b}$ for many $\mathbf{b}$ cheaply. The product of pivots (with a sign for row swaps) gives the Determinant. Applying elimination to $[A \mid I]$ produces the Matrix Inverse. The free variables of the homogeneous system $A\mathbf{x}=\mathbf{0}$ span the Null Space (Kernel), while pivot columns of the original $A$ form a basis of the Column Space — together these realize the Rank–Nullity Theorem. The whole framework lives inside the theory of Vector Spaces and Linear Transformations.

🔬 Where this appears

⏳ History

- ~150 BCE — The Chinese text Jiuzhang Suanshu (Nine Chapters on the Mathematical Art), Chapter 8 Fangcheng, presents elimination on counting-board arrays — essentially the algorithm two millennia early.

- 263 CE — Liu Hui writes a commentary refining the fangcheng elimination procedure.

- 1750s — Gabriel Cramer publishes the determinant-based rule (Cramer's rule); elegant but exponentially slow, motivating practical elimination.

- 1809–1810 — Carl Friedrich Gauss systematizes elimination for least-squares orbit determination of Pallas, solving the normal equations.

- 1888 — Wilhelm Jordan (geodesist) popularizes reduction to fully reduced form in his handbook, giving rise to "Gauss–Jordan elimination."

- 1947 — Alan Turing analyzes rounding-error growth in elimination, introducing condition-number ideas.

- 1947 — von Neumann & Goldstine publish a rigorous error analysis for digital computers.

- 1961 — James Wilkinson develops backward error analysis, proving that elimination with partial pivoting is numerically stable in practice.

- 1969 onward — Strassen and successors show matrix operations (and hence solving) can beat

O(n^3)

, reframing elimination's complexity in modern algorithmic terms.

open-problem

Complexity and stability frontiers. Classical Gaussian elimination costs $\Theta(n^3)$ operations. Whether dense linear systems can be solved in essentially optimal time hinges on the matrix multiplication exponent $\omega$ : solving is asymptotically as hard as multiplying, and the exact value of $\omega$ (currently bounded near $2.37$ , conjectured $2$ ) is open. Separately, the numerical status is subtle: partial pivoting is stable on virtually all real-world matrices, yet contrived examples (Wilkinson's $2^{n}$ growth-factor matrices) make the error blow up exponentially — proving tight average-case or smoothed stability bounds remains an active research area. For huge sparse systems, exact elimination causes fill-in (zeros becoming nonzero), and finding fill-minimizing pivot orderings is NP-hard, so practitioners turn to iterative methods (CG, GMRES) where elimination becomes infeasible.

Systems of Linear Equations — Gaussian Elimination

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also