The Row-Reducing Algorithm (Gauss-Jordan Elimination)

Q: How do I get the matrix that performed the reduction?

Append an identity block and reduce $[\, A \mid I_m \,]$. The right-hand block emerges as the non-singular $J$ satisfying $JA = \operatorname{RREF}(A)$, because it accumulates exactly the same sequence of operations. When $A$ is square and non-singular this computation returns $A^{-1}$.

Overview

Reduced row-echelon form is defined by four conditions, but a definition is not a method. The row-reducing algorithm supplies the method: a finite, fully specified procedure that takes any matrix whatsoever and returns a row-equivalent matrix satisfying all four conditions. Because the procedure never fails and never loops, it simultaneously proves that such a form always exists.

The structure is a single outer loop over the rows. On each pass the algorithm locates the leftmost non-zero entry available in the rows not yet finished, brings it into position with an interchange, normalises it to a leading $1$ by scaling, and then clears the rest of its column — above as well as below — with replacement operations. Clearing above the pivot is what distinguishes Gauss-Jordan reduction from plain Gaussian elimination, and it is what removes the need for back-substitution afterwards.

Correctness is established by an invariant rather than by inspection of the finished matrix. After the pass that fixes row $i$ using column $j$ , the first $i$ rows already satisfy all four reduced row-echelon conditions among themselves, and every entry of rows $i+1$ through $m$ in columns $1$ through $j$ is zero. The second half of the invariant forces the next pivot to lie strictly to the right, which is exactly the staircase condition; the first half means the work already done is never undone.

For an engineer the algorithm is the workhorse behind consistency tests, rank determination, null space bases, matrix inversion and change of basis. Its cost is cubic in the dimension, which sets the practical ceiling on hand and exact-arithmetic work, and its behaviour in floating point is governed entirely by how the pivot is chosen — a choice the mathematics leaves completely free and numerical analysis constrains tightly.

Definition

Row-Reducing

To row-reduce a matrix $A$ is to apply elementary row operations to $A$ until a row-equivalent matrix $B$ in reduced row-echelon form is reached. The term is used as a verb: one row-reduces a matrix. Because the destination is unique, the phrase the reduced row-echelon form of $A$ , written $\operatorname{RREF}(A)$ , is well defined.

Row-reducing a matrix produces information about the original matrix. Analysis normally proceeds by computing $B$ , reading structure from $B$ , and transferring conclusions to $A$ using theorems whose hypotheses include the row-equivalence of $A$ and $B$ .

Row-Equivalent Matrix in Echelon Form

REMEF

For every matrix $A$ there exists a matrix $B$ such that $A$ and $B$ are row-equivalent and $B$ is in reduced row-echelon form. The proof is constructive: it exhibits a terminating procedure that manufactures $B$ from $A$ using only elementary row operations, so the theorem and the algorithm are the same object.

Existence is proved here; uniqueness of $B$ is a separate theorem, and it is uniqueness that licenses the notation $\operatorname{RREF}(A)$ and phrases such as the rank of a matrix.

Concepts

The procedure, stated precisely

Let $A$ have $m$ rows. Initialise the row counter $k = 1$ and repeat the following. If $k = m+1$ , stop. Otherwise, search all entries in rows $k$ through $m$ for the leftmost non-zero entry and let $\ell$ be its column; if every one of those entries is zero, stop. If the entry found is not in row $k$ , apply an interchange so that row $k$ carries a non-zero entry in column $\ell$ . Scale row $k$ by the reciprocal of its entry in column $\ell$ , creating a leading $1$ . Use replacement operations driven by row $k$ to make every other entry of column $\ell$ zero. Increase $k$ by one and repeat.

Two features deserve attention. The search in the second step is over a rectangular block, not along a single column, which is what lets the algorithm skip columns that are entirely zero below the current row. And the clearing in the fifth step touches all other rows, including those above row $k$ ; restricting it to the rows below produces echelon form instead.

Why it terminates and why the output is correct

Termination is immediate: $k$ increases by one on every pass and the loop halts at $k = m+1$ , so at most $m$ passes occur. Since each pass consumes a distinct column as a pivot column, at most $\min(m, n)$ passes do any work.

Correctness follows from the invariant. Suppose the pass with $k = i$ used column $j$ . At its conclusion, rows $1$ through $i$ form a matrix in reduced row-echelon form, and rows $i+1$ through $m$ are zero in columns $1$ through $j$ . The pivot search guarantees columns $1$ through $j-1$ were already zero in those lower rows; the scaling step supplies the leading $1$ ; the clearing step zeroes column $j$ everywhere else; and rows above $i$ keep their leading ones because their pivot columns lie to the left of column $j$ , where row $i$ is zero. Consequently the next pivot must lie in a column strictly to the right of $j$ , which is precisely the fourth condition of reduced row-echelon form. If the loop exits because the search found no non-zero entry, all remaining rows are zero rows and they already sit at the bottom.

Three outcomes, one procedure

Applied to an augmented matrix $[\, A \mid \vec{b} \,]$ with $n$ unknowns, the algorithm resolves the system completely. If the final column becomes a pivot column, some row reads $[\,0\ \cdots\ 0 \mid 1\,]$ , representing the equation $0 = 1$ , and the system is inconsistent. Otherwise the system is consistent, and the count $r$ of pivot columns decides between the two remaining cases: $r = n$ leaves no free variables and the solution is unique; $r < n$ leaves $n - r$ free variables and the solution set is infinite.

No separate test, no discriminant and no determinant is required. The same fixed sequence of arithmetic operations discriminates all three cases, which is why row reduction rather than Cramer's rule is the basis of every practical solver.

Forward elimination versus full reduction

Stopping after the clearing below each pivot yields an echelon form and costs approximately $\tfrac{2}{3}n^3$ floating-point operations for an $n \times n$ matrix. Completing the reduction by clearing above every pivot adds roughly a further $\tfrac{1}{3}n^3$ , bringing the total to about $n^3$ . Against that extra 50% of arithmetic, the reduced form requires no back-substitution: each pivot row already isolates its variable.

For a single right-hand side the trade is unattractive, because back-substitution costs only $O(n^2)$ . The reduced form wins when the deliverable is structural — rank, a null space basis, a canonical form for comparison — or when many right-hand sides are carried simultaneously in a single augmented block, as in matrix inversion.

The pivot choice is free, the destination is not

Uniqueness of the reduced row-echelon form means the algorithm's output does not depend on which of several tied candidates is selected as the pivot, nor on the order in which columns are cleared. Only the intermediate arithmetic changes. That freedom is spent differently in different regimes.

In exact arithmetic the preferred pivot is a $\pm 1$ or a small integer that divides its column cleanly, since the scaling step is the only source of fractions. In floating point the preferred pivot is the entry of largest magnitude in the candidate column — partial pivoting — which bounds every replacement multiplier by $1$ in modulus and thereby limits the growth of rounding error. Without pivoting, a small pivot produces large multipliers and catastrophic cancellation, and the algorithm can return a confidently wrong answer for a perfectly well-conditioned matrix.

Recording the transformation

Since each operation is left multiplication by an invertible elementary matrix, the whole reduction amounts to a single non-singular $J$ with $J A = \operatorname{RREF}(A)$ . Running the algorithm on the extended array $[\, A \mid I_m \,]$ produces $[\, \operatorname{RREF}(A) \mid J \,]$ , because the identity block accumulates exactly the same operations.

This one modification turns the reducer into several other tools. When $A$ is square and non-singular, $\operatorname{RREF}(A) = I_n$ and $J = A^{-1}$ . When $A$ is rectangular, the rows of $J$ corresponding to the zero rows of $\operatorname{RREF}(A)$ form a basis for the left null space. The extended echelon form built this way yields all four fundamental subspaces from one reduction.

The row-reducing loop

InitialiseSet the row counter

k = 1

and the pivot column set

D = \emptyset

. The matrix may be a bare coefficient array, an augmented matrix, or a matrix extended by an identity block.

Search for the next pivotScan rows

k

through

m

for the leftmost non-zero entry; call its column

\ell

. If no non-zero entry exists, stop — rows

k

through

m

are zero rows and are already at the bottom.

Interchange into positionIf the chosen entry is not in row

k

, swap rows so that row

k

holds it. In floating point, select the largest-magnitude candidate in column

\ell

rather than the first one found.

Normalise to a leading oneScale row

k

by the reciprocal of its entry in column

\ell

. The entry is non-zero by construction, so the scalar is legitimate. Record

\ell

D

Clear the whole columnApply replacement operations driven by row

k

to zero every other entry of column

\ell

, in rows above as well as below. Omitting the rows above yields echelon form, not reduced form.

AdvanceIncrease

k

by one and return to the search. Stop when

k = m+1

. On exit,

r = |D|

is the rank and the matrix satisfies all four RREF conditions.

Equations

Pivot search rule

EQ-RR-01

ℓ = min {c : \exists p \geq k, [A]_{p c} \neq 0}

The pivot column for pass $k$ is the leftmost column containing a non-zero entry in any row from $k$ downwards. Searching a block rather than a single column is what allows entirely zero columns to be skipped.

Normalisation and clearing operations for pass $k$

EQ-RR-02

\frac{1}{[A]_{k ℓ}} R_{k}, - [A]_{p ℓ} R_{k} + R_{p} \forall p \neq k

Scale the pivot row to create the leading $1$ , then drive every other row's entry in column $\ell$ to zero. The multiplier for row $p$ is the negative of that row's current entry in the pivot column.

Loop invariant after the pass fixing row $i$ with column $j$

EQ-RR-03

[A]_{p c} = 0 \forall p \geq i + 1, 1 \leq c \leq j

Everything below and to the left of the current pivot is already zero. This forces the next pivot column to satisfy $\ell > j$ , which is exactly the staircase condition of reduced row-echelon form.

Reduced form of an augmented matrix

EQ-RR-04

[A ∣ \vec{b}] \sim [\begin{matrix} 1 & * & 0 & c_{1} \\ 0 & 0 & 1 & c_{2} \\ 0 & 0 & 0 & 0 \end{matrix}]

A representative destination with $r = 2$ pivot columns among the coefficient columns and no pivot in the augmented column. The starred entries carry the coefficients of the free variables.

Three outcomes from the pivot set

EQ-RR-05

S = \emptyset \Leftrightarrow (n + 1) \in D, | S | = 1 \Leftrightarrow r = n, | S | = \infty \Leftrightarrow r < n

Read on the reduced augmented matrix, with the second and third statements conditional on consistency. $D$ is the pivot column set and $r = |D|$ counted over the coefficient columns.

Floating-point operation counts

EQ-RR-06

Floating-point operation counts

Leading-order counts for a dense $n \times n$ system. Full Gauss-Jordan reduction costs roughly 50% more than elimination followed by back-substitution and produces the same solution, so it is chosen for its structural output rather than its speed.

Reduction with an identity block records the transformation

EQ-RR-07

[A ∣ I_{m}] \sim [RREF (A) ∣ J], J A = RREF (A)

The identity block accumulates the same operations, so it emerges as the non-singular matrix $J$ that effects the whole reduction. For square non-singular $A$ this is exactly the computation of $A^{-1}$ .

Variable Definitions

Symbols used on this page
Symbol	Name	Meaning	Domain / type
$A$	Input matrix	The $m \times n$ array submitted to the algorithm; often an augmented matrix	m x n matrix
$B$	Reduced form	The row-equivalent matrix in reduced row-echelon form produced by the algorithm	m x n matrix
$k$	Row counter	Index of the row being fixed on the current pass; runs from $1$ upwards	1 to m+1
$ℓ$	Pivot column of the current pass	Column index of the leftmost non-zero entry found in rows $k$ through $m$	1 to n
$r$	Rank	Number of passes that placed a leading one, equal to the number of non-zero rows of $B$	0 to min(m,n)
$D$	Pivot column set	Ordered set of columns in which leading ones were created	subset of 1..n
$J$	Transforming matrix	Product of the elementary matrices for the whole reduction, satisfying $JA = B$	m x m non-singular matrix
$S$	Solution set	Set of vectors satisfying the represented system, unchanged by the reduction	subset of C^n
$I_{m}$	Identity matrix	Square matrix with ones on the diagonal, appended when the transformation is to be recorded	m x m matrix

Worked Numerical Example

Problem statement

A four-branch hydraulic manifold is instrumented with three redundant flow constraints, giving three equations in four unknown branch flows: $2q_1 + 4q_2 - 6q_3 + q_4 = 11$ , $q_2 - 2q_3 + 3q_4 = 10$ , and $q_1 + 2q_2 - 3q_3 = 4$ . Run the row-reducing algorithm on the augmented matrix, classify the system, and report the solution set.

Form the augmented matrix and start the loop
Order the unknowns $q_1, q_2, q_3, q_4$ and append the constants. Set $k = 1$ . The leftmost non-zero entry among all three rows lies in column 1, so $\ell = 1$ .
$[\begin{matrix} 2 & 4 & - 6 & 1 & 11 \\ 0 & 1 & - 2 & 3 & 10 \\ 1 & 2 & - 3 & 0 & 4 \end{matrix}]$
Interchange to obtain a convenient pivot
Row 1 already has a non-zero entry in column 1, so no interchange is strictly required. Row 3 offers a pivot of $1$ , however, which avoids introducing fractions in the scaling step. Apply $R_1 \leftrightarrow R_3$ . The freedom to make this choice costs nothing, because the final reduced form is unique.
$[\begin{matrix} 1 & 2 & - 3 & 0 & 4 \\ 0 & 1 & - 2 & 3 & 10 \\ 2 & 4 & - 6 & 1 & 11 \end{matrix}]$
Clear column 1
The pivot entry is already $1$ , so no scaling is needed. Row 2 has a zero in column 1 and requires no operation. Apply $-2R_1 + R_3$ : row 3 becomes $(2-2,\ 4-4,\ -6+6,\ 1-0,\ 11-8) = (0,\ 0,\ 0,\ 1,\ 3)$ . Record $1 \in D$ and set $k = 2$ .
$Clear column 1$
Second pass: pivot in column 2
Search rows 2 and 3. The leftmost non-zero entry lies in column 2 of row 2, so $\ell = 2$ and no interchange is needed. The entry is already $1$ . Clear the column above as well as below: apply $-2R_2 + R_1$ , giving row 1 as $(1,\ 0,\ -3+4,\ 0-6,\ 4-20) = (1,\ 0,\ 1,\ -6,\ -16)$ . Row 3 already has zero in column 2. Record $2 \in D$ and set $k = 3$ .
$Second pass: pivot in column 2$
Third pass: column 3 is skipped
Search row 3 alone. Its entries in columns 1, 2 and 3 are all zero, so the leftmost non-zero entry is in column 4 and $\ell = 4$ . Column 3 is therefore not a pivot column, and $q_3$ will be a free variable. This is exactly the case the block search in the algorithm exists to handle; a naive column-by-column scan would stall here.
$Third pass: column 3 is skipped$
Clear column 4
The pivot entry is already $1$ . Apply $-3R_3 + R_2$ : row 2 becomes $(0,\ 1,\ -2,\ 0,\ 10-9) = (0,\ 1,\ -2,\ 0,\ 1)$ . Apply $6R_3 + R_1$ : row 1 becomes $(1,\ 0,\ 1,\ 0,\ -16+18) = (1,\ 0,\ 1,\ 0,\ 2)$ . Set $k = 4 = m+1$ and stop.
$Clear column 4$
Classify the system
All four reduced row-echelon conditions hold. The pivot columns are $D = \{1, 2, 4\}$ , so $r = 3$ . Column 5 is the augmented column and is not a pivot column, so the system is consistent. With $n = 4$ unknowns and $r = 3$ , there are $n - r = 1$ free variables. The solution set is an infinite one-parameter family.
$r = 3, n - r = 4 - 3 = 1$
Read and verify the solution set
Each non-zero row isolates its own dependent variable, so no back-substitution is required. Row 1 gives $q_1 = 2 - q_3$ , row 2 gives $q_2 = 1 + 2q_3$ , row 3 gives $q_4 = 3$ , with $q_3$ free. Substituting into the third original equation confirms the parameter cancels: $(2 - q_3) + 2(1 + 2q_3) - 3q_3 = 2 - q_3 + 2 + 4q_3 - 3q_3 = 4$ .
$S = {[\begin{matrix} 2 - q_{3} \\ 1 + 2 q_{3} \\ q_{3} \\ 3 \end{matrix}] ∣ q_{3} \in ℂ}$

Result

The manifold is under-determined by one degree of freedom: the three redundant flow constraints fix branch 4 at $3$ units and tie branches 1 and 2 to branch 3, but they cannot determine branch 3 itself. An extra independent measurement on any of branches 1, 2 or 3 would close the system; a fourth measurement on branch 4 would add nothing, because column 4 is already a pivot column.

Applications & Industry Use

Civil & structural engineering

Solving the assembled equilibrium system

After boundary conditions are imposed, a small frame analysis reduces to a dense system in the unknown displacements. Row reduction of the augmented matrix both solves it and reveals mechanisms: any free variable remaining after reduction corresponds to a rigid-body or internal mechanism that the restraint scheme has failed to suppress.

Electrical & power engineering

Load flow initialisation and network reduction

The linearised DC power flow is a sparse linear system in bus angles. Reduction identifies the reference bus as a free variable and detects islanded sub-networks, which appear as additional zero rows and additional degrees of freedom in the reduced form.

Chemical engineering

Balancing reactions and counting independent reactions

An atomic balance matrix is reduced to determine the stoichiometric coefficients. The number of free variables equals the number of independent reactions in the set, so the algorithm distinguishes a uniquely balanced equation from a reaction family requiring extra specification.

Computer graphics & geometry

Fitting transformations to point correspondences

Recovering an affine transformation from measured point pairs gives a linear system in the transformation entries. Row reduction reports immediately whether the correspondences are sufficient, redundant or contradictory, and the free variables identify precisely which components of the transformation remain undetermined.

Cryptanalysis & coding theory

Solving linear systems over a finite field

Algebraic attacks on stream ciphers and decoding of linear block codes both reduce to solving large sparse systems modulo a small prime. The same algorithm applies verbatim, with the advantage that arithmetic is exact and pivot selection needs no stability considerations at all.

Operations research

The pivot step of the simplex method

Each simplex iteration performs exactly one pass of the row-reducing algorithm on the tableau: choose an entering column, choose a pivot row by a ratio test, normalise, and clear the column throughout. The linear-programming machinery is a row reduction with an economic rule for pivot selection.

Design Considerations

Decide the deliverable before choosing the variant

If a single numeric solution is wanted, forward elimination with back-substitution — or better, a reusable LU factorisation — is cheaper and no less accurate. Choose full reduction when the required output is the pivot pattern, the rank, a null space basis or a canonical form for comparison. Paying 50% more arithmetic for structure you will not use is a common and avoidable waste.

Pivot for stability whenever the entries are inexact

Without pivoting, a small pivot generates large multipliers and the reduction can lose all significant digits on a matrix that is perfectly well conditioned. Partial pivoting — selecting the largest-magnitude candidate in the pivot column — bounds every multiplier by $1$ and is the standard default. Complete pivoting bounds growth more tightly but costs $O(n^3)$ comparisons and is rarely justified.

Never test a floating-point pivot against exact zero

Rounding turns structurally zero entries into small non-zero ones, so an exact-zero test selects noise as a pivot and reports a rank that is too large. Any production implementation must apply a tolerance scaled to the matrix norm, state that tolerance in its output, and treat the resulting rank as an estimate. Where the rank decision matters, a singular value decomposition is the defensible instrument.

Batch right-hand sides into one reduction

The operations are determined solely by the coefficient block, so several constant vectors — or an entire identity block — can be carried through the same reduction at marginal extra cost. This is why matrix inversion, multi-load-case analysis and the extended echelon form are all single reductions rather than repeated ones.

Reconsider the algorithm for sparse matrices

Clearing above the pivot as well as below causes far more fill-in than forward elimination alone, so a sparse matrix can densify catastrophically during full reduction. Sparse practice uses a fill-reducing ordering with a sparse LU or QR factorisation, and obtains rank information from the factorisation rather than from a reduced form.

Bound the arithmetic before committing to exact rationals

In rational arithmetic each replacement operation can double the bit length of the entries, so intermediate numerators may grow exponentially in the dimension even when input and output are small integers. For anything beyond a few hundred rows, use a fraction-free elimination or reduce modulo several primes and reconstruct.

Standards & Codes

Notation, interchange and numerical standards that govern how this material is written down, stored and computed in production systems.

Applicable standards, conventions and reference implementations
Reference	Title	Relevance to this topic
`IEEE 754-2019`	IEEE Standard for Floating-Point Arithmetic	Specifies the rounding of the multiply-add that dominates the inner loop and defines the special values that appear when a pivot underflows. Compliance is what makes the error analysis of pivoted elimination predictable across platforms.
`LAPACK reference`	Linear Algebra PACKage reference implementation	Provides the industrial realisation of this algorithm as blocked LU factorisation with partial pivoting (`xGETRF`) and the corresponding solver (`xGETRS`). No reduced row-echelon routine is offered, which reflects the profession's preference for reusable factorisations.
`BLAS Level 3`	Basic Linear Algebra Subprograms, matrix-matrix operations	Blocked variants of the algorithm restructure the elimination so that most work occurs in `xGEMM`, raising the arithmetic-to-memory ratio and delivering the bulk of achievable performance on cached architectures.
`ISO 80000-2`	Quantities and units — Part 2: Mathematics	Governs the presentation of the matrices, the operator names and the index conventions used in the statement of the algorithm and its invariant.
`ISO/IEC 40314`	Mathematical Markup Language (MathML) Version 3.0	Encodes each intermediate matrix of the reduction as structured markup, so a step-by-step derivation remains machine-readable and navigable by assistive technology rather than being flattened to images.

Material Selection

For a mathematical topic, "material" is the numeric representation: the scalar field, storage format and precision the computation is built from.

Representation and precision selection
Representation	Select when	Trade-off
Exact rational arithmetic	Small to moderate matrices where the pivot pattern must be certain and a symbolic answer is required.	No tolerance decisions at all, but entry sizes can grow exponentially through the reduction and memory use is unbounded.
Arbitrary-precision integers, fraction-free elimination	Integer matrices where exactness is required but rational blow-up must be controlled.	The Bareiss method keeps every intermediate entry integral and bounded by a minor of the original, at the cost of producing an echelon rather than fully reduced form.
IEEE 754 binary64 with partial pivoting	The default for engineering systems whose entries carry measurement uncertainty.	Excellent speed and well-understood error bounds, but the pivot pattern becomes a tolerance-dependent judgement and near-dependent columns may be misclassified.
IEEE 754 binary32 or mixed precision	Very large or accelerator-based computation where memory bandwidth dominates.	Halves data movement and often doubles throughput, but roughly seven significant digits demands iterative refinement in higher precision to recover an acceptable residual.
Finite field arithmetic modulo a prime	Coding theory, algebraic cryptanalysis, and modular rank certification of integer matrices.	Exact with fixed operand size and no stability concerns, but a poorly chosen prime can dividing a pivot to zero and report a rank lower than the rational rank.
Sparse storage with fill-reducing ordering	Large structured systems from discretised physical models.	Essential for tractability, but full reduction causes severe fill-in; a sparse LU or QR should be substituted and rank read from the factorisation.

Manufacturing Notes

Implementation notes — how the result is actually produced by hand, by algorithm and by library, including cost and numerical behaviour.

Operation count in detail

Pass $k$ on an $n \times n$ matrix clears $n-1$ rows over roughly $n-k$ remaining columns, giving about $2(n-1)(n-k)$ flops. Summing over $k$ yields approximately $n^3$ floating-point operations for full reduction, against $\tfrac{2}{3}n^3$ for forward elimination alone plus $n^2$ for back-substitution. The reduction is memory-bound in a naive implementation and compute-bound only after blocking.

Executing the procedure by hand

Work strictly left to right, one pivot column at a time. Lock the pivot row before clearing and use only its original values as the source. Where the arithmetic allows, defer the scaling operation so intermediate entries remain integral, then normalise at the end. Write the operation shorthand beside every arrow; the record is what makes an error locatable rather than merely detectable.

Blocked and parallel variants

The elimination of a panel of columns can be deferred and applied as a single matrix-matrix update, which converts most of the work from Level 2 to Level 3 BLAS. Within a column pass the replacement operations on distinct target rows are independent and parallelise directly; the pivot search is the serial bottleneck, which is why communication-avoiding variants relax the pivoting strategy.

Verification of the output

Check all four reduced row-echelon conditions explicitly rather than by eye. Independently, substitute a candidate solution into the original equations, since an arithmetic slip during reduction produces a matrix that is internally consistent but no longer row-equivalent to the input. If the transformation was accumulated, verify $JA = B$ directly and inspect the residual as a measure of accumulated rounding.

Library behaviour

SymPy's Matrix.rref returns both the reduced matrix and the tuple of pivot columns, and works in exact arithmetic by default. MATLAB provides rref with a documented tolerance and a warning in its own documentation against relying on it numerically. NumPy deliberately offers no equivalent, exposing numpy.linalg.matrix_rank via singular values and scipy.linalg.lu instead.

Failure Modes & Common Mistakes

Failure modes, root causes and prevention
Failure mode / mistake	Impact	Root cause	Prevention & detection
Stopping at echelon form	high	Clearing only below each pivot, so entries above the leading ones remain non-zero.	The clearing step must run over all rows $p \ne k$ . Verify explicitly that each leading one is the only non-zero entry in its column.
Scanning a single column instead of a block	high	Assuming pivot $k$ must lie in column $k$ , so the algorithm stalls or aborts when a column is entirely zero below the current row.	Implement the pivot search over the whole remaining block and skip columns with no non-zero candidate. Track the pivot set $D$ explicitly rather than inferring it from row numbers.
No pivoting in floating point	high	Accepting the first non-zero candidate, producing multipliers far larger than one and amplifying rounding error.	Apply partial pivoting by default: select the largest-magnitude candidate in the pivot column before eliminating.
Exact-zero pivot test on rounded data	high	Testing `if entry == 0`, so an entry of magnitude $10^{-17}$ that should be structurally zero is selected as a pivot.	Use a tolerance scaled to the matrix norm, report it alongside the result, and prefer a singular value decomposition where the rank decision is consequential.
Dropping the augmented column	high	Reducing the coefficient block alone, discarding exactly the information needed to detect inconsistency.	Reduce $[\, A \mid \vec{b} \,]$ as one array and test whether column $n+1$ is a pivot column before interpreting anything else.
Re-using a row already modified in the current pass	medium	Updating the pivot row midway through clearing its own column, so later replacement operations use corrupted multipliers.	Compute all multipliers from the pivot row's values at the start of the pass, and do not modify the pivot row during that pass.
Miscounting free variables	medium	Counting zero rows rather than non-pivot columns among the coefficient columns.	Compute degrees of freedom as $n - r$ , where $n$ is the number of unknowns and $r = \|D\|$ excludes any pivot in the augmented column.
Applying the algorithm to a sparse matrix unchanged	low	Treating full reduction as a drop-in method for large discretised systems.	Estimate fill-in first. Substitute a sparse factorisation with a fill-reducing ordering, and obtain rank from that factorisation.

FAQs

Is Gauss-Jordan elimination the same as Gaussian elimination?

They share the forward phase. Gaussian elimination stops at an echelon form and finishes with back-substitution; Gauss-Jordan continues, clearing above every pivot as well as below, and finishes with the reduced row-echelon form. Gauss-Jordan costs about 50% more arithmetic and produces a unique, directly readable result.

Does the algorithm always terminate?

Yes, unconditionally. The row counter increases on every pass and the loop halts at $k = m+1$ , or earlier when the pivot search finds nothing but zeros. No hypothesis on the matrix is required — it need not be square, need not be consistent, and may be entirely zero.

Does the answer depend on which pivots I choose?

The final reduced row-echelon form does not; only the intermediate arithmetic does. Uniqueness of the reduced form means pivot strategy is free to be chosen on numerical or convenience grounds. In floating point the choice still matters greatly, because rounding means the computed result only approximates the exact reduced form.

Why does the pivot search look at a block of rows rather than one column?

Because a column may be entirely zero below the current row, in which case it contains no pivot and must be skipped. Searching for the leftmost non-zero entry over all remaining rows handles this automatically and is what allows the algorithm to produce a correct staircase for rank-deficient and rectangular matrices.

How do I get the matrix that performed the reduction?

Append an identity block and reduce $[\, A \mid I_m \,]$ . The right-hand block emerges as the non-singular $J$ satisfying $JA = \operatorname{RREF}(A)$ , because it accumulates exactly the same sequence of operations. When $A$ is square and non-singular this computation returns $A^{-1}$ .

Can I use the algorithm to compute a determinant?

Yes, and it is the standard efficient method, but track the scaling. Reduce to triangular form, multiply the diagonal entries, then multiply by $-1$ for each interchange and divide by every scaling factor applied. Cofactor expansion costs $O(n!)$ operations; reduction costs $O(n^3)$ .

Why do numerical libraries not expose a reduced row-echelon routine?

Because the pivot pattern is discontinuous in the entries: an arbitrarily small perturbation can promote a structurally zero entry to a pivot and change the reported rank. Libraries therefore expose rank-revealing tools with explicit tolerances — pivoted QR and singular value decomposition — rather than a form whose exactness they cannot guarantee.

References

Beezer, R. A. A First Course in Linear Algebra, Version 0.70. University of Puget Sound, 2006. Section RREF, Theorem REMEF and Definition RR. Licensed under the GNU Free Documentation License v1.2.
Golub, G. H. and Van Loan, C. F. Matrix Computations, 4th edition. Johns Hopkins University Press, 2013.
Higham, N. J. Accuracy and Stability of Numerical Algorithms, 2nd edition. Society for Industrial and Applied Mathematics, 2002.
IEEE 754-2019, IEEE Standard for Floating-Point Arithmetic. Institute of Electrical and Electronics Engineers.
Anderson, E. et al. LAPACK Users' Guide, 3rd edition. Society for Industrial and Applied Mathematics, 1999.
Bareiss, E. H. “Sylvester's identity and multistep integer-preserving Gaussian elimination.” Mathematics of Computation, 22(103), 1968.

AI Suggested Questions

Trace the row-reducing algorithm on a 4x6 matrix whose third column is entirely zero, and show where the block pivot search matters.
Construct a 3x3 matrix for which elimination without pivoting loses all accuracy in binary64 but partial pivoting succeeds.
Derive the leading-order flop count for full reduction and compare it with LU factorisation plus two triangular solves.
How does the Bareiss fraction-free variant keep intermediate entries integral, and what does it cost relative to rational elimination?
Show how one pass of the row-reducing algorithm corresponds exactly to one pivot step of the simplex method on a linear programming tableau.
Estimate the fill-in produced by full reduction of a banded matrix of bandwidth $b$ compared with forward elimination alone.

Related Calculators

RREF Calculator

Row-reduce any matrix with a complete audit trail of the operations, pivot columns and rank.

Linear System Solver

Solve $A\vec{x} = \vec{b}$ and report consistency, rank, free variables and the vector form of the solution set.

Gauss-Jordan Stepper

Execute the algorithm one pass at a time with selectable pivoting strategy and exact or floating-point arithmetic.

Matrix Inverse Calculator

Reduce $[\, A \mid I_n \,]$ to obtain $A^{-1}$ , or report the singularity that prevents it.