Alphabeta Math

Gaussian Elimination, Elementary Matrices and Reduced Row Echelon Form

About this page
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.

✓ 23 results · all verified · 0 also independently AI-judged
Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 23 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.
1 · Prerequisites
Abstract Algebra
Combinatorics
Linear Algebra
Real Analysis
Set Theory
2 · Logical flowchart

3 · Items

Definition

Elementary row operations and row equivalence for finite matrices over a field

Lemma

Every elementary row operation has an elementary inverse, so row equivalence is an equivalence relation

Definition

Elementary matrices obtained by applying one elementary row operation to an identity matrix

Theorem

Applying an elementary row operation is left multiplication by its elementary matrix

Corollary

Every elementary matrix is invertible, with inverse given by the reverse elementary operation

Corollary

A finite row reduction from A to B is encoded by B=Eᵣ⋯ E₁A

Definition

Matrix equation Ax=b, its solution set, consistency, homogeneous systems and the augmented matrix [A∣ b]

Theorem

Elementary row operations on an augmented matrix preserve exactly the solutions of its linear system

Definition

Row echelon form, reduced row echelon form, leading entries, pivots, pivot positions and pivot columns

Theorem

Gaussian elimination reduces every finite matrix over a field to row echelon form

Theorem

Gauss–Jordan elimination reduces every finite matrix over a field to reduced row echelon form

Theorem

Every finite matrix over a field is row equivalent to exactly one reduced row echelon matrix

Definition

Row space, column space, nullspace, row rank, column rank and matrix rank

Lemma

Row-equivalent matrices have the same row space and the same row rank

Lemma

The nonzero rows of a row echelon form form a basis of the original row space

Theorem

For equal-sized matrices, row equivalence, equality of row spaces and equality of reduced row echelon forms are equivalent

Lemma

Elementary row operations preserve every linear relation among the columns and hence preserve column rank

Theorem

The columns of the original matrix indexed by pivot columns form a basis of its column space

Theorem

Row rank equals column rank, and both equal the number of pivots

Corollary

The rank of a matrix equals the rank of the linear map x↦ Ax

Corollary

For an m× n matrix A, rank(A)+dim N(A)=n

Definition

Affine subspaces as translates x+U of linear subspaces

Theorem

If Ax=b has one solution xₚ, then its full solution set is the affine subspace xₚ+N(A)

Theorem

Reduced row echelon form detects consistency and parametrises every solution by the nonpivot variables

Corollary

The system Ax=b is consistent if and only if rank(A)=rank([A∣ b])

Corollary

Over an infinite field, a finite linear system has no solution, exactly one solution, or infinitely many solutions according to its pivots

Theorem

Invertible matrix theorem: invertibility, full pivot rank, RREF I, trivial nullspace and unique solvability are equivalent

Theorem

Every invertible finite square real matrix is a finite product of elementary matrices

Corollary

Row reducing [A∣ I] yields [I∣ A⁻¹] exactly when A is invertible

Sources