Skip to content

Pivoted Row Reduction

Elimination method — instantiates Independent Generating Set Design

Runs elimination with pivoting to expose a maximal independent subset of columns as an exact basis, discarding the rest as redundant and reading the rank straight off the pivots.

Pivoted Row Reduction takes an over-complete or redundant set of vectors, stacks them into a matrix, and eliminates it into echelon form. Its defining move is the pivot: the columns that acquire a pivot during elimination are a maximal linearly independent subset — an exact basis for the column space — and every column that fails to get one is exposed as an explicit combination of the pivot columns. So it does two jobs at once that other methods split apart: it prunes the redundant vectors away, and it produces the exact dependency relations that say what each discarded vector was made of. The number of pivots is the rank. Where an extension routine grows a small set up, this trims a bloated set down — and it does so algebraically, telling you not just that a vector was redundant but how.

Example

An electrical engineer analyzing a circuit writes one Kirchhoff voltage-law equation per loop. On a circuit with many meshes it is tempting to write an equation for every loop you can trace — but most of those loops are just sums and differences of others, so the equation set is badly redundant. Stacking the loop equations into a matrix and row-reducing sorts it out: the pivot rows are a maximal independent set of loop equations, and the non-pivot rows come back written explicitly as combinations of them.

The pivot count matches the number of independent loops the circuit actually has — for a connected network, branches minus nodes plus one — so the engineer keeps exactly that many equations, no more, and solves a clean, non-redundant system. Just as valuably, the elimination shows which redundant loops were combinations of which independent ones, so nothing about the circuit's structure is lost in the trimming.

How it works

  • Choose pivots with care. In each column, select a pivot — with partial pivoting, the largest-magnitude available entry — for numerical safety, then eliminate the entries above and below it.
  • Read independence from pivots. A column that earns a pivot is independent of the earlier pivot columns; a column that does not is dependent, and its multipliers give the dependency explicitly.
  • Count the rank. The number of pivots is the rank and the size of the extracted basis.

What sets it apart is that it returns the exact dependency relations alongside the basis — the how of each redundancy, not merely a count.

Tuning parameters

  • Pivoting strategy — none, partial (largest in the column), or full (largest in the remaining submatrix); more pivoting buys numerical stability and cleaner independence detection at higher cost.
  • Reduced vs. plain echelon form — reduced form yields a canonical basis and the explicit dependency coefficients; plain form is cheaper but leaves them implicit.
  • Zero / pivot threshold — how small an entry counts as zero (and its column as dependent) — the knob that decides rank near the noise floor.
  • Exact vs. floating-point arithmetic — rational arithmetic makes rank unambiguous but is costly; floating point is fast but makes the zero-threshold load-bearing.
  • Pivot ordering — which independent subset is chosen when several would serve, decided by the order pivots are taken.

When it helps, and when it misleads

Its strength is exactness on two fronts: over rational arithmetic the rank is unambiguous, and unlike any purely numerical rank test it hands back the explicit combinations that express each redundant vector — invaluable when the dependencies themselves carry meaning (which reactions, which loops, which equations are the same information twice).

It misleads on noisy floating-point data. Row reduction has no principled tolerance of its own: the rank verdict then hinges entirely on the zero-threshold, and a small pivot may be a true zero or merely noise — a judgment echelon form cannot make for you.[1] Near-dependent columns can be mis-pivoted, and even a correctly independent basis it extracts can be badly conditioned. The classic misuse is trusting a reduced-echelon rank on noisy data where a tolerance-based test belongs. The discipline is to pivot, to cross-check rank on noisy data with the singular values (Singular-Value Rank Diagnosis), and to keep exact arithmetic whenever the dependency relations must be certified.

How it implements the components

Pivoted Row Reduction fills the exact prune-and-count side of the archetype:

  • minimality_and_pruning_rule — pivot selection keeps only the independent (pivot) columns and discards the rest; the non-pivot columns are the pruned redundancy.
  • generator_independence_criterion — a column earns a pivot if and only if it is independent of the earlier pivot columns, so elimination is the independence test.
  • dimension_and_rank_reference — the number of pivots is the rank and fixes the dimension of the column space.

It does not optimize the kept subset for numerical conditioning — Rank-Revealing QR Factorization does — nor supply a principled numerical rank tolerance under noise (Singular-Value Rank Diagnosis), nor grow a partial basis to completeness (Independent-Seed Basis Extension).

References

[1] Partial pivoting — choosing the largest-magnitude entry in a column as the pivot — controls error growth during elimination, but it does not supply a rank tolerance. Deciding whether a tiny pivot is a true zero or numerical noise is a separate, basis-dependent judgment that echelon form alone cannot make. ↩