Gaussian Elimination: Row Reduction

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:

Elementary Row Operations

\begin{aligned} R_i &\leftrightarrow R_j \quad \text{(swap)} \\ kR_i &\to R_i, \quad k \neq 0 \quad \text{(scaling)} \\ R_i + cR_j &\to R_i \quad \text{(addition)} \end{aligned}

Elementary row operations →

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

Elimination Notation

Notation

Elimination Notation

The bar that keeps a system from being just a matrix, the arrow that must point at the right row, and the tilde that says “same solutions, different entries.”

Matrices and their entries — matrix notation; bold

\mathbf{x}

,

\mathbf{b}

— vector notation;

R_i \leftrightarrow R_j

,

kR_i \to R_i

,

R_i + cR_j \to R_i

are defined in The Three Elementary Row Operations above.

[A \mid \mathbf{b}]

The augmented matrix — A, bar, b

The vertical bar is punctuation, not an operation: left of it, coefficient columns; right of it, the constants. The bar records where the

=

signs of the original system stood, and it rides along unchanged through every row operation.

CasesErase the bar and the object changes species — from a record of a system to a plain

m \times (n{+}1)

matrix. Multiple right-hand sides stack more columns behind the bar:

[A \mid \mathbf{b}_1 \; \mathbf{b}_2]

, the device that computes an inverse via

[A \mid I]

.

Also written

(A \mid \mathbf{b})

with parentheses, matching this site's matrix brackets; some texts drop the bar entirely and trust the reader's memory — the bar exists so nobody has to.

Do not confuseA determinant or divisibility bar. The single upright stroke has many jobs; between matrix columns inside brackets it only ever separates.

R_i + cR_j \to R_i

Row i plus c times row j, replacing row i

The arrow points at the row being replaced — that is the entire convention, and the entire hazard. In every legal addition step, the row that survives unscaled is the one being written over; row

j

is only read, never changed.

CasesTexts disagree on the spelling:

R_i \to R_i + cR_j

(arrow first),

R_i := R_i + cR_j

(assignment),

R_i' = R_i + cR_j

(primes). Same operation throughout — but the illegal move

cR_j \to R_i

, overwriting a row with a multiple of another, destroys information and no notation makes it legal.

Also writtenAnnotations over a long arrow between displayed matrices —

\xrightarrow{R_2 - 3R_1}

— the compact form worked examples use.

Do not confuseThe limit arrow. Same glyph as approach; here it means “becomes” — an update, not a tendency.

A \sim B

A is row-equivalent to B

The tilde asserts that a chain of row operations connects

A

to

B

— entries differ, solution sets agree. It is precisely not equality: writing

=

between elimination steps is the classic false statement, because the matrices are genuinely different.

CasesEvery elimination chain is a chain of tildes ending in echelon form; the tilde is what licenses reading the final matrix's solutions as the first matrix's.

Also written

\rightarrow

between displayed matrices, arrow standing in for the tilde in worked examples — including this page's.

Do not confuseThe tilde's other lives: equivalent sets in set theory, “is distributed as” in statistics,

\approx

's single-stroke cousin for approximation. One squiggle, four fields, four meanings.

All linear algebra symbols →↑ Linear Systems

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.

Clearing one entry beneath a pivot

A multiple of the pivot row is being subtracted from the row below to put a zero under the pivot. Nothing about the solution set changes, because the operation is reversible — the same multiple added back restores the original. That reversibility is the licence for the whole algorithm. Step through a full elimination on the Gaussian elimination visualizer.

Every step of forward elimination is one instance of this move, applied downward and then leftward across the matrix.

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.

Reduced row echelon form reached

Pivots have been scaled to one and cleared above as well as below, so each pivot column now holds a single one and nothing else. At this point no back substitution is left: the values are sitting in the final column. Compare the effort against stopping at echelon form on the Gaussian elimination visualizer.

Whether the extra clearing is worth it depends entirely on whether you want the answer or the structure.

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.

A row of zeros against a non-zero constant

The coefficients in this row have all been eliminated while the constant has not, so the row now asserts that zero equals something non-zero. One such row is enough to make the entire system inconsistent, regardless of how well the other rows behaved. Construct one deliberately on the Gaussian elimination visualizer.

Inconsistency is therefore detected, not decided — it announces itself as a row rather than having to be tested for.

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.

The stages below are not all of the same kind. The first two happen for every system and in that order; the third is a fork, where two different amounts of work lead to the same solution set. Separating the compulsory part from the choice is what makes the cost comparison meaningful — the elimination is paid either way, and only the reading differs.

Download

PNGRaster · 2×PDFPrint quality

Linear systems · the algorithm

Gaussian elimination, stage by stage

Two stages are compulsory and the third is a choice. Forward elimination and classification happen once; after that, back substitution and Gauss–Jordan reach the same solution set by different amounts of work.

5stages

Compulsory — every system, every time2

1

Forward elimination§ 3

swaps and row additions, left to right

[A \mid \mathbf{b}] \to

row echelon form

Sweep column by column, using each pivot to zero everything beneath it. This is the expensive stage at roughly

\tfrac{2}{3}n^3

operations, and it is where partial pivoting belongs — choosing the largest available pivot rather than the first nonzero one.

2

Classify the columns§ 4

and check for

[\,0 \cdots 0 \mid d \neq 0\,]

pivot columns vs free columns

Everything diagnostic happens here. The pivot count is the rank, the free columns are the parameters, and a contradiction row settles solvability before any solution is attempted.

A choice — two ways to read the answer2

3

Back substitution§ 5

stops at REF

solve upward from the last pivot row

Less arithmetic: roughly

n^2

operations on top of the elimination, and no further row operations at all. The usual choice by hand and the one every numerical library uses, since the triangular form is already enough to solve from.

4

Gauss–Jordan§ 6

zero above the pivots, scale pivots to

1

continue to reduced row echelon form

Roughly

50\%

more arithmetic than back substitution for the same solution, so it is not the method of choice for solving. Its value is elsewhere: the RREF is unique, which makes it the right form for reading a null space basis or inverting a matrix.

What comes out1

5

The solution set§ 7

decided at the classification stage

a point, or

\mathbf{x}_p + \operatorname{Null}(A)

, or empty

Never anything else. Unique when every column has a pivot, a translated subspace when some do not, empty when a contradiction row appeared — and which of the three it is was known before the solution was computed.

The whole algorithm is three row operations applied until the shape is triangular, and every one of them is reversible — which is why the solution set is unchanged at every step. Elimination does not solve the system so much as rewrite it into a form where the solution can be read.

Gaussian elimination, stage by stage·/linear-algebra/linear-systems/gaussian-eliminationLearn Math Class

The classification stage is the one most easily skipped and the one that carries the most. Before any solution is written down, the pivot positions already give the rank, the free columns already give the number of parameters, and a contradiction row already settles that there is no solution at all. Work done after that point is filling in a shape that has already been determined.

Between the two readings, back substitution wins on arithmetic and Gauss–Jordan wins on form. Continuing to the reduced row echelon form costs roughly half again as much for the same answer, which is a poor trade if solving is the goal. It is the right trade when the form is the goal — the RREF is unique where the REF is not, so it is what a null space basis, a matrix inverse, or a comparison between two matrices has to be read from.

Gaussian Elimination FAQ

What is the bar doing in $[A \mid \mathbf{b}]$ ?

+

Separating, nothing more. It marks the array as a record of a system rather than a plain matrix, and erasing it changes the object's species into an ordinary

m \times (n{+}1)

matrix. The same device stacks more columns behind the bar for multiple right-hand sides, which is how

[A \mid I]

computes an inverse.Read more →

Can you overwrite a row with a multiple of a different row?

+

No, and no notation makes it legal. The valid replacement keeps the target row in the expression, as in

R_i \to R_i + cR_j

, so the operation is reversible. Writing

cR_j \to R_i

discards whatever

R_i

contained, destroying information the system needed and producing a matrix that is not row-equivalent to the original.Read more →

Does the tilde in $A \sim B$ mean approximately equal?

+

Not here, where it means row-equivalent: one matrix reaches the other through elementary row operations, so both describe the same solution set. The squiggle leads several lives across mathematics, marking equivalent sets in set theory and "is distributed as" in statistics, besides its single-stroke role as a cousin of the approximation sign.Read more →

Gaussian Elimination

The Workhorse Algorithm of Linear Algebra

The Goal

The Three Elementary Row Operations

Elimination Notation

Elimination Notation

Forward Elimination

Pivots and Pivot Positions

Back Substitution

Worked Example

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

Gaussian elimination, stage by stage

Gaussian Elimination FAQ

What is the bar doing in [A∣b][A \mid \mathbf{b}][A∣b]?

Can you overwrite a row with a multiple of a different row?

Does the tilde in A∼BA \sim BA∼B mean approximately equal?

What is the bar doing in $[A \mid \mathbf{b}]$ ?

Does the tilde in $A \sim B$ mean approximately equal?