Gaussian Elimination: Row Reduction

The Goal

Fact: Elimination on a counting board

The Chinese Nine Chapters on the Mathematical Art, compiled by the 1st century AD, lays out a system as columns of rods on a board, in effect an augmented matrix, and eliminates column against column, some 1,700 years before Gauss. The subtractions produce negative numbers, so the same chapter gives rules for them.

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.

THEOREM

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

DownloadPNG2×PDF

Before you read

Three moves, all reversible

Gaussian elimination uses only three operations on rows. Each one changes the system without changing its solutions, and each can be undone.

Elementary row operations3 operations

Swap

R_i \leftrightarrow R_j

Doesreorders equations, fixes a zero pivot

Undone bythe same swap

Scaling

kR_i,\ k \neq 0

Undone byscaling by

1/k

$k = 0$ is forbidden

Addition

R_i + cR_j

Doeseliminates entries

Undone bysubtracting

cR_j

Takeaway

Only one move eliminates

Swapping and scaling tidy the rows; adding a multiple of one row to another is the operation that actually creates the zeros.

The three elementary row operations·/linear-algebra/linear-systems/gaussian-eliminationLearn Math Class

Row operations change the equations but never the solutions, because every one of them can be undone.

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.

Pitfall: Updating two rows from each other at once

Doing

R_1 - R_2 \to R_1

and

R_2 - R_1 \to R_2

in one step on

x_1 + x_2 = 2

,

x_1 - x_2 = 0

gives the rows

[0 \; 2 \mid 2]

and

[0 \; {-2} \mid {-2}]

, which allow infinitely many solutions.

R_2 - R_1 \to R_2

alone gives the unique solution

x_1 = x_2 = 1

.

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.

THEOREM

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

Back Substitution

\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

.

Pitfall: Reading the answer off echelon form

Reading the last column of the echelon form in the back substitution example as the solution gives

(9, 6, 10)

, and already the bottom row fails:

5 \cdot 10 \neq 10

. That matrix is in REF, not RREF; the solution is

(11/4, 5/2, 2)

.

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, raising the total work by up to roughly

50\%

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

Worked Example: Unique Solution

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:

Worked Example: Unique Solution

\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)

Worked Example: Unique Solution

\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)

Pitfall: Dropping the right-hand side

Applying

R_2 - 2R_1

to the coefficients only keeps the constant

8

instead of

8 - 2 \cdot 3 = 2

. Back substitution then gives

(71, -28, 12)

, which fails the second equation:

14 \neq 8

. The full row operation gives

(-1, 2, 0)

.

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.

To run the same elimination on your own system, use the linear systems calculator.

Worked Example: Infinitely Many Solutions

Solve the system

Worked Example: Infinitely Many Solutions

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:

Worked Example: Infinitely Many Solutions

\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:

Worked Example: Infinitely Many Solutions

\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}

Pitfall: Dropping the free variable's own entry

Writing the

s

-vector as

(1, 0, 0, 0)

, without the

1

for

x_2 = s

, gives at

s = 1, t = 0

the point

(0, 0, 2, 0)

, where the first equation reads

4 = 3

. The direction vectors are

(1, 1, 0, 0)

and

(3, 0, -2, 1)

.

The solution set is a two-dimensional plane in

\mathbb{R}^4

, passing through

(-1, 0, 2, 0)

and spanned by two direction vectors.

Each row of the vector form belongs to one unknown,

x_1

to

x_4

from top to bottom. The constant vector is the solution with

s = t = 0

, and the vector multiplied by

s

records how every unknown changes when

s

grows by

1

and

t

stays fixed. Any choice of the two parameters, such as

s = 1, t = 0

, must give a point that satisfies both original equations.

Worked Example: No Solution

Solve the system

Worked Example: No Solution

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

Form and reduce:

Worked Example: No Solution

\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.

Pitfall: Treating a zero row as a contradiction

For

x_1 + x_2 = 2

,

2x_1 + 2x_2 = 4

,

R_2 - 2R_1

leaves the row

[0 \; 0 \mid 0]

. Reading it as no solution is wrong: it says

0 = 0

, true for every pair, and the system has infinitely many solutions

(2 - s, s)

.

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, in the classical form that clears above each pivot during the sweep, the backward pass adds about half the work of 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 adds up to roughly 50% to 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

At about

\frac{2}{3}n^3

operations, elimination is cheaper than Cramer's rule or an explicit inverse, so direct solvers build on it.

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.

Fact: One tiny pivot, a wrong answer

Solve

10^{-20}x_1 + x_2 = 1

,

x_1 + x_2 = 2

in double precision without a swap: the multiplier

10^{20}

swamps the second row, and the computer returns

x_1 = 0

, although the true value is

1

to twenty decimal places. Swapping the rows first gives

x_1 = x_2 = 1

.

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 pivot positions, the rank, and the solution are the same in exact arithmetic; only the echelon form and the pivot values can differ. 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

.

Pivoting never changes the answer in exact arithmetic; it decides whether a computer actually finds it.

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 up to 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.

Common Pitfalls

Five mistakes account for many wrong answers in Gaussian elimination. Each is marked with a box where it happens in the sections above; here each is worked through in full, with the wrong and the right working side by side.

Updating two rows from each other at once

Two row additions are carried out in the same step, and each one reads the other row before it has changed:

R_1 - R_2 \to R_1

and

R_2 - R_1 \to R_2

together. Each move on its own is a legal row operation, but the pair is not, and information is lost.

Wrong working: for

x_1 + x_2 = 2

,

x_1 - x_2 = 0

,

\left(\begin{array}{cc|c} 1 & 1 & 2 \\ 1 & -1 & 0 \end{array}\right) \to \left(\begin{array}{cc|c} 0 & 2 & 2 \\ 0 & -2 & -2 \end{array}\right)

The second row is

-1

times the first, so only

x_2 = 1

remains,

x_1

looks free, and the system seems to have infinitely many solutions.

Right working: one operation, with the pivot row left as it is.

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

Row

2

gives

x_2 = 1

and row

1

gives

x_1 = 1

: the unique solution

(1, 1)

.

Why it happens: worked examples write several operations over one arrow, such as

R_2 - 2R_1,\; R_3 - 3R_1

, and that looks as if any two operations can be combined. Those two are safe only because both read row

1

, which neither of them changes.

How to check: row operations never change the rank. The coefficient matrix

\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}

has rank

2

, but the wrong result has rank

1

, so a step was not a row operation.

Reading the answer off echelon form

The last column of the augmented matrix is read as the solution as soon as the matrix is in row echelon form. That reading is valid only in reduced row echelon form, where every pivot is

1

and is the only nonzero entry in its column.

Wrong working: from the matrix of the back substitution example,

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

the values

x_1 = 9

,

x_2 = 6

,

x_3 = 10

are read off.

Right working: back substitution from the bottom row gives

x_3 = 2

, then

x_2 = 5/2

, then

x_1 = 11/4

. Continuing to RREF gives the same values in the last column:

\left(\begin{array}{ccc|c} 1 & 0 & 0 & 11/4 \\ 0 & 1 & 0 & 5/2 \\ 0 & 0 & 1 & 2 \end{array}\right)

Why it happens: both forms are staircases with zeros below the pivots, and in RREF the last column really is the answer, so the habit carries over to REF.

How to check: substitute into the bottom row. With

x_3 = 10

it reads

5 \cdot 10 = 50

, not

10

. Before reading the last column, check that every pivot is

1

and has zeros above it.

Dropping the right-hand side

A row operation is applied to the coefficients but not to the constant behind the bar. The coefficient part still reduces correctly, so nothing looks wrong until the end.

Wrong working: in the unique-solution example,

R_2 - 2R_1

turns

(2, 5, 1)

into

(0, 1, 3)

but the constant

8

is kept.

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

Back substitution gives

x_3 = 12

,

x_2 = 8 - 36 = -28

and

x_1 = 3 - 2(-28) + 12 = 71

.

Right working: the constant becomes

8 - 2 \cdot 3 = 2

, the third row ends in

0

instead of

-12

, and back substitution gives

x_3 = 0

,

x_2 = 2

,

x_1 = -1

.

Why it happens: the bar sets the constants apart, and attention goes to the entries being eliminated, which all sit to the left of it.

How to check: substitute into the original equations. The wrong answer

(71, -28, 12)

satisfies the first and third equations, but the second gives

2(71) + 5(-28) + 12 = 14

, not

8

.

Dropping the free variable's own entry

When the parametric vector form is assembled, each direction vector is filled in only from the pivot rows. The entry of the free variable itself, which equals its parameter, is left at

0

.

Wrong working: from

x_1 = -1 + s + 3t

and

x_3 = 2 - 2t

,

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

Right working: write all four unknowns, including

x_2 = s

and

x_4 = t

, and then split by parameter.

\mathbf{x} = \begin{pmatrix} -1 + s + 3t \\ s \\ 2 - 2t \\ t \end{pmatrix} = \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}

Why it happens: the free variables never stand alone on the left of an equation from the echelon form, so they are easy to miss when the vector is built from those equations.

How to check: set one parameter to

1

and the other to

0

, and substitute. The wrong form gives

(0, 0, 2, 0)

at

s = 1, t = 0

, and the first equation reads

0 - 0 + 4 + 0 = 4

, not

3

. The right form gives

(0, 1, 2, 0)

, which satisfies both equations. In the right form, the free-variable entries of the direction vectors are always

1

and

0

.

Treating a zero row as a contradiction

Any row with zeros in all the coefficient columns is read as a sign that the system has no solution. Only a row

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

with

d \neq 0

is a contradiction; a row that is zero all the way across says

0 = 0

.

Wrong working: for

x_1 + x_2 = 2

,

2x_1 + 2x_2 = 4

,

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

and the second row is taken to mean that the system is inconsistent.

Right working: the second row reads

0 = 0

, which every pair

(x_1, x_2)

satisfies, so it puts no condition on the solution. Row

1

has its pivot in column

1

and column

2

is free:

x_2 = s

,

x_1 = 2 - s

. There are infinitely many solutions; the two equations describe the same line.

Why it happens: the no-solution example also ends in a row whose coefficients are all zero, and the entry behind the bar is overlooked.

How to check: look behind the bar before deciding. Here

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

, so the system is consistent; the point

(2, 0)

satisfies both equations.

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

Common Pitfalls

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?