How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
Every finite matrix over a field is row equivalent to exactly one reduced row echelon matrix
Statement
Every finite matrix over a field is row equivalent to exactly one matrix in reduced row echelon form. This unique matrix is called its reduced row echelon form, or RREF.
Facts & Assumptions
Given: A finite matrix over a field, and two reduced row echelon matrices and row equivalent to .
Gauss–Jordan elimination gives at least one reduced row echelon form row equivalent to (Gauss–Jordan elimination reduces every finite matrix over a field to reduced row echelon form).
Row operations preserve exactly the solutions of every augmented linear system (Elementary row operations on an augmented matrix preserve exactly the solutions of its linear system).
In reduced row echelon form, each pivot is the leading entry of its row and every pivot column is a unit column (Row echelon form, reduced row echelon form, leading entries, pivots, pivot positions and pivot columns).
Induction applies to the finite ordered list of columns (The principle of mathematical induction).
Proof
Existence is [L1]. For uniqueness, [L2] applied to shows that and have the same homogeneous solution set.
The common homogeneous solution set determines the pivot columns. Indeed, column is a pivot column exactly when every solution satisfying for all also satisfies . For a pivot column this follows from its pivot equation; for a nonpivot column, set that free variable to and every other free variable to . Induction over the finite ordered columns therefore gives the same pivot positions for and .
For each nonpivot column , there is a unique homogeneous solution whose nonpivot coordinates are at and elsewhere. Its coordinate at pivot is the negative of the entry in row , column ; pivot columns are unit columns by [L3]. Thus the common solution set determines every entry. With no columns, no rows, or no pivots the same description is empty or all zero, so in every case .
Depends on
- Gauss–Jordan elimination reduces every finite matrix over a field to reduced row echelon form
- Elementary row operations on an augmented matrix preserve exactly the solutions of its linear system
- Row echelon form, reduced row echelon form, leading entries, pivots, pivot positions and pivot columns
- The principle of mathematical induction
Used by
- One matrix has two distinct row echelon forms but one reduced row echelon form Example
- For equal-sized matrices, row equivalence, equality of row spaces and equality of reduced row echelon forms are equivalent Theorem
- Reduced row echelon form detects consistency and parametrises every solution by the nonpivot variables Theorem
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 24 results over 12 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.
Sources
- J. Hefferon, Linear Algebra, 4th ed., Ch. One, §III.2 (standard reference, not scraped)