Row reduction and RREF
The lectures introduced Gaussian elimination and RREF as a procedure, with a brief worked example. This write-up gives the precise definitions, walks through several examples of different character, and carefully proves the dimension statements — in particular, that the number of free variables exactly equals the dimension of the solution space.
1. Two normal forms for matrices
Gaussian elimination ends at one of two normal forms, depending on how far you carry it. Understanding both is useful: echelon form is easier to reach; reduced echelon form makes the solution immediately readable.
Definition — Row echelon form
A matrix is in row echelon form (REF) if:
- Every zero row lies below every nonzero row.
- In every nonzero row, the leftmost nonzero entry (called a leading entry or pivot) lies strictly to the right of the pivot in the row above it.
The pivots thus form a staircase pattern, stepping right and down.
Definition — Reduced row echelon form
A matrix is in reduced row echelon form (RREF) if it satisfies both REF conditions and: 3. Every pivot equals
. 4. Every other entry in a pivot column is — not just entries below the pivot, but entries above it too.
Comparison.
In the RREF on the right, the pivot columns (columns 1, 2, and 4) each have a single
2. The Gauss-Jordan algorithm
The Gauss-Jordan algorithm transforms any matrix into RREF by systematically applying the three elementary row operations:
- Add a scalar multiple of one row to another (
) - Swap two rows (
) - Scale a row by a nonzero scalar (
, )
Each operation is reversible, so the solution set of a linear system does not change when these are applied to its augmented matrix.
Algorithm.
Repeat the following on the submatrix not yet processed:
- Find the leftmost column with a nonzero entry. If none exists, the matrix is already in RREF.
- Swap (if necessary) to bring a nonzero entry to the top of that column.
- Scale the top row so the leading entry becomes
. This entry is the pivot. - Eliminate: for every other row (both above and below), subtract the appropriate multiple of the pivot row to make its entry in the pivot column zero.
- Move down one row and right to the next unprocessed column. Repeat.
A pivot column is a column in which a pivot was placed. All other columns are free columns.
3. Worked examples
Example 1 — Unique solution (
System:
Augmented matrix and reduction:
RREF reached. Pivot columns: 1 and 2. No free variables.
Solution:
Example 2 — One free variable (
This is the system from Lecture 4.
System:
Augmented matrix and reduction:
RREF reached. Pivot columns: 1 (
Reading off the solution: Set
- From row 2:
- From row 1:
Parametric form:
The solution set is a line in
Example 3 — Two free variables (
System:
Augmented matrix and reduction:
RREF reached. Pivot columns: 1 (
Reading off the solution: Set
- From row 2:
- From row 1:
Parametric form:
The solution set is a 2-dimensional flat in
Example 4 — Inconsistent system
System:
Reduction:
The second row reads
The criterion. A system is inconsistent if and only if, after row reduction, the augmented matrix contains a row of the form
Example 5 — Unique solution (
System:
(Observe that
Augmented matrix and reduction:
Now eliminate upwards:
RREF reached. All three columns are pivot columns. No free variables.
Solution:
4. Pivot columns and free columns — summary
After reducing to RREF, the structure of the solution set is completely determined:
| Situation | Conclusion |
|---|---|
| Augmented matrix has a row | System is inconsistent (no solution) |
| No such row, and 0 free variables | System has a unique solution (a single point) |
| No such row, and | System has infinitely many solutions (a |
When solutions exist:
- Pivot variables are determined: each is expressed in terms of the free variables by its row.
- Free variables are parameters: each can be set to any real number independently.
5. Uniqueness of RREF
Theorem — Uniqueness of RREF
Given a matrix
, its RREF is unique: no matter which sequence of valid elementary row operations is applied, the result is always the same matrix. In particular, the set of pivot column indices is uniquely determined by
.
The proof is more involved than it looks — it requires showing that the staircase structure and the
Why it matters. Because RREF is unique, statements like “column 2 is free” or “the rank is 3” are well-defined properties of the original matrix, not of the reduction process. Without uniqueness, one could reach different RREFs by different paths and the pivot/free distinction would be ambiguous.
6. The dimension of the null space
The worked examples all confirmed the same pattern: the dimension of the null space equalled the number of free variables. This is not a coincidence.
Theorem — Dimension of the null space
Let
be an matrix. Suppose the RREF of has pivot columns (equivalently, pivots). Then: where
is the null space (solution set of the homogeneous system).
The number
Proof.
Let
Constructing
- Set
and for all (set the -th free variable to , all others to ). - Determine each pivot variable from its row in the RREF: the row corresponding to pivot column
reads , so is the negative of those free-variable terms.
The resulting vector
These
These
Corollary.
7. Connecting everything: a worked example
We combine the RREF computation, the parametric solution, and the dimension count for Example 3.
The coefficient matrix was
variables, pivot columns (columns 1 and 3), free variables (columns 2 and 4). , confirmed by the explicit basis . : the column space of is 2-dimensional inside . - Rank-nullity:
.
The direction vectors
8. Summary
| Quantity | Definition | Value from RREF |
|---|---|---|
| Number of pivot columns | ||
| Number of free columns | ||
| Dimension of solution space |
The three-way classification of consistent linear systems:
| Free variables | Solution set | Dimension |
|---|---|---|
| Single point | ||
| Line in | ||
| Plane in | ||
The full solution set of