What is Gaussian elimination?

Gaussian elimination transforms a linear system into row echelon form using three elementary row operations: row swaps, row scaling, and adding multiples of one row to another. Forward elimination creates zeros below each pivot, then back substitution solves from the bottom up.

What is the difference between REF and RREF?

Row echelon form (REF) has a staircase of pivots with zeros below each one — the solution requires back substitution. Reduced row echelon form (RREF) additionally has each pivot equal to 1 and zeros above each pivot, so the solution is visible by direct inspection.

How do you know if a system has no solution?

A system is inconsistent when row reduction produces a row of the form [0 0 ⋯ 0 | d] with d ≠ 0, representing the impossible equation 0 = d. This means rank([A | b]) > rank(A), and no solution exists.

What are pivot and free variables?

Pivot variables correspond to columns containing a pivot in the echelon form — their values are determined by back substitution. Free variables correspond to non-pivot columns and can take any real value. If there are free variables and the system is consistent, infinitely many solutions exist.

What is partial pivoting?

Partial pivoting selects the largest absolute value in the current pivot column and swaps it into the pivot position. This keeps multipliers small and limits rounding error accumulation in floating-point arithmetic. Every serious numerical implementation uses partial pivoting by default.

Gaussian Elimination

The Goal

The Three Elementary Row Operations

Forward Elimination

Pivots and Pivot Positions

Back Substitution

Gauss-Jordan Elimination

Worked Example: Unique Solution

Worked Example: Infinitely Many Solutions

Worked Example: No Solution

Computational Cost

Partial Pivoting

Summary: The Algorithm at a Glance

The Workhorse Algorithm of Linear Algebra

Gaussian elimination transforms a linear system into a simpler equivalent form by systematically applying row operations. Forward elimination creates zeros below each pivot, producing row echelon form. Back substitution then solves from the bottom up. The algorithm handles every case — unique solutions, infinitely many solutions, and inconsistent systems — within a single unified framework.

The Goal

The input is an augmented matrix

[A \mid \mathbf{b}]

representing a linear system

A\mathbf{x} = \mathbf{b}

. The output is an equivalent system — one with exactly the same solution set — in a form simple enough that the solution can be read off directly or obtained with minimal effort.

The "simple form" is echelon form: a staircase pattern where the leading entry of each row is to the right of the leading entry of the row above, and everything below each leading entry is zero. Once the augmented matrix is in echelon form, the solution is extracted by back substitution — solving from the last equation upward.

Optionally, the reduction can continue to reduced row echelon form (RREF), where each leading entry is

1

and is the only nonzero entry in its column. In RREF, the solution is visible by inspection.

The Three Elementary Row Operations

Gaussian elimination uses three operations, each of which transforms the augmented matrix without changing the solution set.

Row swap (

R_i \leftrightarrow R_j

): interchange two rows. This reorders the equations — a cosmetic change that is sometimes necessary to place a nonzero entry in the pivot position.

Row scaling (

kR_i \to R_i

k \neq 0

): multiply every entry in a row by a nonzero scalar. This rescales one equation. Multiplying by zero is forbidden because it would destroy information.

Row addition (

R_i + cR_j \to R_i

): add

c

times row

j

to row

i

, replacing row

i

with the result. This is the operation that actually eliminates entries — by choosing

c

appropriately, a targeted entry becomes zero.

Each operation is reversible: swapping the same pair undoes the swap, scaling by

1/k

undoes scaling by

k

, and subtracting

c

times row

j

from row

i

undoes the addition. Reversibility guarantees that no solutions are created or lost. Each operation also corresponds to left-multiplication by an elementary matrix, connecting the algorithm to the theory of matrix factorization.

Operation	Notation	Effect on the system	Reverse operation
Row swap	R_i ↔ R_j	reorders two equations; used to place a nonzero entry into the pivot position	the same swap R_i ↔ R_j
Row scaling	k · R_i → R_i (k ≠ 0)	rescales one equation; used to make pivots equal to 1 in RREF	scaling the same row by 1 / k
Row addition	R_i + c · R_j → R_i	replaces one equation by a combination; this is the operation that actually eliminates entries	R_i − c · R_j → R_i

Forward Elimination

Forward elimination is the first phase of the algorithm. It sweeps through the augmented matrix from left to right, top to bottom, creating zeros below each pivot.

Start with the leftmost column that contains a nonzero entry. Identify a nonzero entry in that column to serve as the pivot — if the entry in the current top row is zero, swap that row with a row below that has a nonzero entry in this column. Then use row addition to eliminate every entry below the pivot: for each row

i

below the pivot row, add

-\frac{a_{ij}}{a_{pj}}

times the pivot row to row

i

, zeroing out the

(i, j)

entry.

Move one column to the right and one row down, and repeat the process on the submatrix below and to the right of the current pivot. Continue until no rows or columns remain to process.

The result is a matrix in row echelon form: a staircase of pivots descending from upper-left to lower-right, with zeros filling in below and to the left of each pivot. Any rows that are entirely zero sit at the bottom.

Pivots and Pivot Positions

A pivot is the leading (leftmost) nonzero entry in each row of the echelon form. The column containing a pivot is a pivot column; every other column is a free column.

The number of pivots equals the rank of the coefficient matrix. Pivot columns correspond to determined variables (pivot variables) whose values are fixed once the free variables are assigned. Free columns correspond to free variables (parameters) that can take any real value.

If every column of

A

is a pivot column, the system has no free variables and the solution (if it exists) is unique. If at least one column is free, the solution set (if nonempty) is infinite, parametrized by the free variables. The distinction between pivot and free columns is the structural core of the algorithm — it determines both the form and the dimension of the solution set.

Back Substitution

Once the augmented matrix is in row echelon form, the solution is obtained by solving from the bottom row upward.

The last nonzero row contains the fewest unknowns — typically one pivot variable in terms of free variables and a constant. Solve for that pivot variable. Substitute the result into the row above, which now also becomes solvable for its pivot variable. Continue upward until every pivot variable is expressed in terms of the free variables and the constants from

\mathbf{b}

Worked Example

\left(\begin{array}{ccc|c} 2 & -1 & 3 & 9 \\ 0 & 4 & -2 & 6 \\ 0 & 0 & 5 & 10 \end{array}\right)

The bottom row gives

5x_3 = 10

, so

x_3 = 2

. The middle row gives

4x_2 - 2(2) = 6

, so

4x_2 = 10

and

x_2 = 5/2

. The top row gives

2x_1 - 5/2 + 3(2) = 9

, so

2x_1 = 9 + 5/2 - 6 = 11/2

and

x_1 = 11/4

.

Each step required only previously solved variables. The process terminates in

n

steps, with the solution fully determined.

Gauss-Jordan Elimination

Gauss-Jordan elimination extends the forward pass with a backward pass that creates zeros above each pivot as well, and scales each pivot to

1

. The result is reduced row echelon form (RREF), where every pivot variable is already isolated in its row.

After forward elimination produces REF, continue by working from the bottom pivot upward. For each pivot, add appropriate multiples of its row to the rows above to eliminate all entries above the pivot. Then scale the pivot row so the pivot entry becomes

1

.

The payoff is that in RREF, the solution is visible by direct inspection — no back substitution is needed. Each pivot row reads "

x_i = \text{(expression in free variables and constants)}

." The trade-off is that the backward pass requires additional row operations, roughly doubling the total work compared to forward elimination alone.

For hand computation, the choice between back substitution (stop at REF) and Gauss-Jordan (continue to RREF) is a matter of preference. For computer implementations, both approaches are standard.

Worked Example: Unique Solution

Solve the system

x_1 + 2x_2 - x_3 = 3, \quad 2x_1 + 5x_2 + x_3 = 8, \quad 3x_1 + 8x_2 + 2x_3 = 13

Form the augmented matrix and apply forward elimination:

\left(\begin{array}{ccc|c} 1 & 2 & -1 & 3 \\ 2 & 5 & 1 & 8 \\ 3 & 8 & 2 & 13 \end{array}\right) \xrightarrow{R_2 - 2R_1,\; R_3 - 3R_1} \left(\begin{array}{ccc|c} 1 & 2 & -1 & 3 \\ 0 & 1 & 3 & 2 \\ 0 & 2 & 5 & 4 \end{array}\right)

\xrightarrow{R_3 - 2R_2} \left(\begin{array}{ccc|c} 1 & 2 & -1 & 3 \\ 0 & 1 & 3 & 2 \\ 0 & 0 & -1 & 0 \end{array}\right)

Three pivots in three columns — unique solution. Back substitution: row

3

gives

-x_3 = 0

, so

x_3 = 0

. Row

2

gives

x_2 + 3(0) = 2

, so

x_2 = 2

. Row

1

gives

x_1 + 2(2) - 0 = 3

, so

x_1 = -1

.

Verification:

-1 + 4 - 0 = 3

-2 + 10 + 0 = 8

-3 + 16 + 0 = 13

. All three equations are satisfied.

Worked Example: Infinitely Many Solutions

Solve the system

x_1 - x_2 + 2x_3 + x_4 = 3, \quad 2x_1 - 2x_2 + 5x_3 + 4x_4 = 8

Two equations in four unknowns — more unknowns than equations, so the solution (if it exists) cannot be unique. Form and reduce:

\left(\begin{array}{cccc|c} 1 & -1 & 2 & 1 & 3 \\ 2 & -2 & 5 & 4 & 8 \end{array}\right) \xrightarrow{R_2 - 2R_1} \left(\begin{array}{cccc|c} 1 & -1 & 2 & 1 & 3 \\ 0 & 0 & 1 & 2 & 2 \end{array}\right)

Pivots in columns

1

and

3

. Columns

2

and

4

are free. Let

x_2 = s

and

x_4 = t

. Row

2

gives

x_3 = 2 - 2t

. Row

1

gives

x_1 = 3 + s - 2(2 - 2t) - t = -1 + s + 3t

.

The general solution in parametric vector form:

\mathbf{x} = \begin{pmatrix} -1 \\ 0 \\ 2 \\ 0 \end{pmatrix} + s\begin{pmatrix} 1 \\ 1 \\ 0 \\ 0 \end{pmatrix} + t\begin{pmatrix} 3 \\ 0 \\ -2 \\ 1 \end{pmatrix}

The solution set is a two-dimensional plane in

\mathbb{R}^4

, passing through

(-1, 0, 2, 0)

and spanned by two direction vectors.

Worked Example: No Solution

Solve the system

x_1 + x_2 = 2, \quad 2x_1 + 2x_2 = 3

Form and reduce:

\left(\begin{array}{cc|c} 1 & 1 & 2 \\ 2 & 2 & 3 \end{array}\right) \xrightarrow{R_2 - 2R_1} \left(\begin{array}{cc|c} 1 & 1 & 2 \\ 0 & 0 & -1 \end{array}\right)

The second row reads

0x_1 + 0x_2 = -1

, which is the equation

0 = -1

. This is a contradiction — no values of

x_1

and

x_2

can satisfy it.

The system is inconsistent. Geometrically, the two equations represent parallel lines in

\mathbb{R}^2

x_1 + x_2 = 2

and

x_1 + x_2 = 3/2

(the second equation, after dividing by

2

). Parallel lines with different intercepts never intersect.

Inconsistency is always detectable in echelon form: a row

[0 \; 0 \; \cdots \; 0 \mid d]

with

d \neq 0

means

\text{rank}([A \mid \mathbf{b}]) > \text{rank}(A)

, and by the Rouché-Capelli theorem, no solution exists.

Computational Cost

Forward elimination on an

n \times n

system requires roughly

\frac{2}{3}n^3

arithmetic operations (multiplications and additions). The cost comes from the nested loop structure: for each of the

n

pivot columns, elimination involves

O(n)

rows, each requiring

O(n)

operations.

Back substitution requires roughly

n^2

operations — a negligible addition compared to forward elimination. Gauss-Jordan elimination (continuing to RREF) raises the total to roughly

n^3

, because the backward pass does comparable work to the forward pass.

These costs are dramatically better than the alternatives for large systems. Cramer's rule requires

n + 1

determinant evaluations, each costing

O(n^3)

via row reduction or

O(n!)

via cofactor expansion — orders of magnitude slower. Computing the inverse explicitly costs roughly

2n^3

operations. Gaussian elimination is the standard baseline against which all other direct methods are measured.

Phase or method (n × n system)	Approximate operation count	Comment
Forward elimination (produces REF)	~ (2/3) n³	dominant cost of Gaussian elimination
Back substitution after REF	~ n²	negligible compared to forward elimination
Gauss-Jordan (forward + backward to RREF)	~ n³	backward pass roughly doubles the forward pass
Computing A⁻¹ explicitly, then x = A⁻¹b	~ 2 n³	roughly 3× the cost of direct elimination
Cramer's rule	(n + 1) determinants, each O(n³) via row reduction	orders of magnitude slower than elimination for large n; cofactor-expansion routes are O(n!), astronomically slow

Partial Pivoting

In exact arithmetic, any nonzero entry can serve as a pivot. In floating-point arithmetic, the choice matters. A very small pivot amplifies rounding errors — dividing by a number close to zero magnifies any imprecision in the numerator.

Partial pivoting addresses this by modifying the pivot selection step. At each stage, instead of using whatever nonzero entry happens to sit in the pivot position, the algorithm scans the entries below (and including) the current position in the pivot column and swaps the row with the largest absolute value into the pivot position. This keeps the multipliers

-a_{ij}/a_{pj}

small, which limits the accumulation of rounding error.

Partial pivoting does not change the mathematical structure of Gaussian elimination — it only changes which row swaps are performed. The echelon form, the rank, the pivots, and the solution are all the same in exact arithmetic. The difference is entirely numerical: partial pivoting makes the computation stable.

Every serious numerical implementation of Gaussian elimination uses partial pivoting by default. In the LU decomposition, the row swaps are recorded in a permutation matrix

P

, giving the factorization

PA = LU

Summary: The Algorithm at a Glance

Gaussian elimination splits cleanly into a small number of stages — preparing the augmented matrix, reducing it forward, classifying columns as pivot or free, and reading the solution by back substitution or Gauss-Jordan. The table below collects each stage alongside what happens in it and what the next step receives as input, providing a single-page workflow card for the procedure.

Stage	What happens	Output / next step
Input	augmented matrix [A \| b] representing A x = b	ready for forward elimination
Forward elimination	sweep left-to-right; row swaps (with partial pivoting if numerical) and row additions zero entries below each pivot	row echelon form (REF)
Classify columns	identify pivot columns (determined variables) and free columns (parameters); check for a contradiction row [0 ⋯ 0 \| d ≠ 0]	rank, free variables, solvability verdict
Read solution — option A	back substitution: solve each pivot variable from the bottom row upward	explicit values (or parametric expressions) for each variable
Read solution — option B	Gauss-Jordan: continue with row addition and scaling to zero entries above each pivot and make pivots = 1	reduced row echelon form (RREF); solution by direct inspection
Output	single point (unique), parametric vector form x_p + free directions (infinitely many), or "no solution" (inconsistent)	the solution set of A x = b