Skip to content

RowReduce

Status: Stable

documented, exercised by the test suite and/or worked examples, with no known limitations recorded.

Description

RowReduce[m]

gives the row-reduced form of the matrix m.

RowReduce[m, Method -> "<name>"]

runs a specific elimination algorithm. Accepted method names: "Automatic" — alias for "DivisionFreeRowReduction" (default) "DivisionFreeRowReduction" — Bareiss-like fraction-free Gauss-Jordan "OneStepRowReduction" — classical Gauss-Jordan with division per pivot "CofactorExpansion" — identity-if-invertible via Laplace cofactor Det[m] (singular / rectangular m falls back to "DivisionFreeRowReduction")

RowReduce[m, ZeroTest -> f]

uses the predicate f to decide when an entry is zero during the reduction (an entry is zero iff f[entry] is True). Both a body such as (RootReduce[Together[#]] === 0 &) and a predicate head such as PossibleZeroQ are accepted; use it to catch algebraic zeros a structural test would miss. May be combined with Method.

Examples (9)

Every input below was run against the current Mathilda build and its output recorded.

Basic examples (2)

In[1]:= RowReduce[{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}]
Out[1]= {{1, 0, -1}, {0, 1, 2}, {0, 0, 0}}

In[2]:= RowReduce[{{a, b, c}, {d, e, f}, {a+d, b+e, c+f}}]
Out[2]= {{1, 0, (c e)/(-b d + a e) - (b f)/(-b d + a e)}, {0, 1, -(c d)/(-b d + a e) + (a f)/(-b d + a e)}, {0, 0, 0}}

Options (2)

In[3]:= RowReduce[{{2, 1, 0}, {0, 3, 1}, {1, 0, 2}}, Method -> "CofactorExpansion"]
Out[3]= {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}}

In[4]:= RowReduce[{{a, b}, {c, d}}, Method -> "OneStepRowReduction"]
Out[4]= {{1, 0}, {0, 1}}

Applications (5)

In[5]:= RowReduce[{{1, 2}, {3, 4}}]
Out[5]= {{1, 0}, {0, 1}}

In[6]:= RowReduce[{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}]
Out[6]= {{1, 0, -1}, {0, 1, 2}, {0, 0, 0}}

In[7]:= RowReduce[{{1, 1, 1, 1}, {1, 2, 4, 8}, {1, 3, 9, 27}, {1, 4, 16, 64}}]
Out[7]= {{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}}

In[8]:= RowReduce[{{2, 1, -1, 8}, {-3, -1, 2, -11}, {-2, 1, 2, -3}}]
Out[8]= {{1, 0, 0, 2}, {0, 1, 0, 3}, {0, 0, 1, -1}}

In[9]:= RowReduce[{{a, b}, {c, d}}]
Out[9]= {{1, 0}, {0, 1}}

Algorithm

matsol.c

Method-aware dispatcher for RowReduce[m] and LinearSolve[m, b].

Both builtins accept an optional Method -> "<name>" argument (RowReduce as arg 2, LinearSolve as arg 3) and route to one of three explicit algorithms:

  "Automatic"                  -- alias for "DivisionFreeRowReduction"
  "DivisionFreeRowReduction"   -- Bareiss-like fraction-free Gauss-Jordan
  "OneStepRowReduction"        -- classical Gauss-Jordan, one division per
                                  pivot per element of the pivot row
  "CofactorExpansion"          -- LinearSolve: Cramer's rule via Laplace
                                  cofactor expansion;
                                  RowReduce: identity-if-invertible (for a
                                  non-singular square matrix) with fallback
                                  to DivisionFreeRowReduction on
                                  singular / rectangular / empty input.

The DivisionFreeRowReduction workers are direct lifts of the previous bodies of builtin_rowreduce and builtin_linearsolve in src/linalg.c, so existing behaviour is preserved bit-for-bit when the user does not supply a Method option.

Algorithm choice for the four supported matrix families:

  - Machine precision (Real)            -> OneStep is fastest; DivFree fine.
  - Bignum integer                      -> DivFree avoids GCD blow-up.
  - MPFR / arbitrary precision          -> Same as machine precision.
  - Symbolic                            -> DivFree avoids algebraic growth;
                                           CofactorExpansion gives the
                                           textbook Cramer form for small n.

Implementation notes

Algorithm. builtin_rowreduce reduces m to reduced row-echelon form, dispatching on an optional Method option (matsol_parse_method_option):

  • DivisionFreeRowReduction (the default / Automatic): rowreduce_divfree, a Bareiss-like fraction-free Gauss-Jordan. Per pivot column it picks the first structurally non-zero pivot (is_zero_poly), eliminates every other row with the Bareiss update M[i,j] ← (pivot·M[i,j] − M[i,c]·M[r,j]) / P where P is the previous pivot and the division is exact (exact_div_wrapper), keeping all intermediates polynomial/integer with no GCD blow-up. A final pass scales each pivot row to a leading 1, reducing each entry by its PolynomialGCD with the leading coefficient and expand-ing.
  • OneStepRowReduction: rowreduce_onestep, textbook Gauss-Jordan — normalise the pivot row by dividing by the pivot (matsol_div_entry, which prefers exact division and canonicalises with Together), then subtract multiples from every other row. Result is already RREF.
  • CofactorExpansion: rowreduce_cofactor returns identity-if-invertible for a non-singular square matrix, otherwise warns (RowReduce::cofnsq) and falls back to the fraction-free path.

Data structures. A flat row-major Expr** of size m·n; all arithmetic (Times, Plus, Power, PolynomialGCD, Together) is driven through the evaluator via eval_and_free, so integer, rational, complex, and free-symbolic matrices share one code path. Pivot detection is purely structural (is_zero_poly), so a Real cancellation of magnitude ~1e-18 is not treated as zero. Bad Method values emit RowReduce::method and leave the call unevaluated.

  • Protected.
  • Uses fraction-free division logic to perform exact algorithmic reduction across numerical, rational, and symbolics expressions natively avoiding division errors.
  • FLINT acceleration (when built with FLINT): an all-integer/rational matrix is reduced exactly via fmpq_mat_rref; the reduced row echelon form is unique so it matches the classical result, computed in polynomial time. Symbolic matrices fall through. Exposed directly as FLINT`RowReduce (see the FLINT` context section in Structural Manipulation).
  • Lives in src/linalg/linsolve.c; the helper primitives (Laplace cofactor determinant, exact polynomial division, tensor flatten / dimensions) are exposed from src/linalg/util.c and src/linalg/det.c.
  • Accepts an optional Method -> "<name>" argument:
  • Method -> Automatic or Method -> "Automatic" (default) — alias for "DivisionFreeRowReduction".
  • Method -> "DivisionFreeRowReduction" — Bareiss-like fraction-free Gauss-Jordan. Best for exact integer / rational / symbolic input — never produces a denominator larger than necessary.
  • Method -> "OneStepRowReduction" — classical Gauss-Jordan with one division per pivot per element. Each entry is canonicalised via Together so symbolic cancellations are still detected. Fast on numeric matrices.
  • Method -> "CofactorExpansion" — for a non-singular square matrix, returns the identity (verified via Det[m] != 0 computed by Laplace cofactor expansion). On singular or rectangular input, falls back to "DivisionFreeRowReduction" and emits RowReduce::cofnsq.
  • ZeroTest -> f supplies a predicate deciding when an entry is zero during the reduction (zero iff f[entry] is True). Both a body such as (RootReduce[Together[#]] === 0 &) and a predicate head such as PossibleZeroQ are accepted. With a ZeroTest, an exact Gauss-Jordan RREF consults the predicate at every pivot (a structural RREF would pivot on an algebraic zero the predicate rejects) and keeps entries canonical via Together. Shares the machinery with NullSpace (matsol_rref_with_zerotest); Method and ZeroTest may be combined.
  • Unknown method names emit RowReduce::method and the call remains unevaluated.

Attributes: Protected.

References

See also: Together, PossibleZeroQ, NullSpace

Notes & additional examples

Notes

RowReduce[m] returns the reduced row-echelon form of m. The default method is a Bareiss-like fraction-free Gauss-Jordan elimination ("DivisionFreeRowReduction"), which avoids intermediate-coefficient swell; pass Method -> "OneStepRowReduction" for classical division-per-pivot, or Method -> "CofactorExpansion" to certify invertibility via the determinant. The pivot columns of the result identify a basis for the row space, and a zero bottom row (as in the 3x3 magic-style example) signals linear dependence.