Difficulty: Introductory | Prerequisites: Augmented matrices, row operations, REF and RREF definitions (Lecture 02)
This section proves that every matrix can be reduced to RREF using a finite number of elementary row operations. The algorithm that does this is called Gaussian elimination. It is the foundational computational tool for solving linear systems throughout the course, and nearly every topic that follows (rank, solution sets, vector spaces) depends on it. If you missed the definitions of REF and RREF from last lecture, go back and nail those first.
Every matrix can be brought to RREF by a two-pass process: a forward pass (top to bottom) that produces REF, then a backward pass (bottom to top) that cleans up to RREF. The three elementary row operations are all you need.
Elementary row operations
The three legal moves you can perform on a matrix without changing its solution set:
Type 1: Swap two rows (Ri ↔ Rj)
Type 2: Multiply a row by a nonzero scalar (Ri → cRi, where c ≠ 0)
Type 3: Add a scalar multiple of one row to another (Rj → Rj + cRi)
In simple terms, these are the only transformations allowed during elimination. They rearrange or combine rows but never introduce or destroy solutions.
Row Echelon Form (REF)
A matrix where all zero rows sit at the bottom, each leading entry (first nonzero entry in a row) is strictly to the right of the leading entry in the row above, and entries below each leading entry are zero.
Think of it as a staircase pattern stepping down and to the right.
Reduced Row Echelon Form (RREF)
REF with two additional requirements: every leading entry equals 1, and every leading entry is the only nonzero entry in its column (zeros above and below).
In simple terms, RREF is the "cleanest" form of a matrix, where each pivot column has a single 1 and nothing else.
Gaussian elimination
The algorithm that converts any matrix into RREF via the two-pass procedure (forward pass to REF, backward pass to RREF).
Think of it as the standard recipe for row-reducing a matrix.
Forward pass
The first half of Gaussian elimination. Works top-to-bottom, producing REF by creating zeros below each leading entry.
Backward pass (back-substitution)
The second half of Gaussian elimination. Works bottom-to-top, producing RREF by making leading entries equal to 1 and creating zeros above each leading entry.
Every matrix can be put in RREF by a finite sequence of elementary row operations. The proof is constructive, meaning the theorem is proved by demonstrating the algorithm itself.
The forward pass works column by column, left to right, row by row, top to bottom:
Step (i): Use a Type 1 swap to place a nonzero entry at the top of the leftmost nonzero column. This becomes the leading entry (pivot) for that row.
Step (ii): Use Type 3 operations to create zeros in every position below the pivot.
Step (iii): Ignore the row you just processed. Move down one row and repeat steps (i) and (ii) on the remaining sub-matrix.
Continue until you reach the bottom row. The matrix is now in REF.
The backward pass works from the bottom-right pivot upward:
Step (i): Use a Type 2 operation to scale the bottommost leading entry to 1 (if it is not already).
Step (ii): Use Type 3 operations to create zeros in every position above this leading 1.
Step (iii): Move up to the next leading entry and repeat.
Continue until every leading entry is 1 with zeros above and below it. The matrix is now in RREF.
Starting matrix:
( 0 1 2 3 )
( 1 1 1 1 )
( 3 2 1 2 )
Forward pass:
R1 ↔ R2 (swap to get nonzero entry in top-left):
( 1 1 1 1 )
( 0 1 2 3 )
( 3 2 1 2 )
R3 → R3 − 3R1 (zero out below first pivot):
( 1 1 1 1 )
( 0 1 2 3 )
( 0 −1 −2 −1 )
R3 → R3 + R2 (zero out below second pivot):
( 1 1 1 1 )
( 0 1 2 3 )
( 0 0 0 2 )
R3 → (1/2)R3 (scale third pivot to 1). Now in REF:
( 1 1 1 1 )
( 0 1 2 3 )
( 0 0 0 1 )
Backward pass:
R1 → R1 − R3, R2 → R2 − 3R3 (zeros above third pivot):
( 1 1 1 0 )
( 0 1 2 0 )
( 0 0 0 1 )
R1 → R1 − R2 (zeros above second pivot):
( 1 0 −1 0 )
( 0 1 2 0 )
( 0 0 0 1 )
This is RREF.
Gaussian elimination is the backbone of how computers solve systems of linear equations. Every time an engineer runs a structural simulation or a data scientist fits a regression model, some variant of this algorithm is at work under the hood.
Students sometimes apply row operations to columns instead of rows. Column operations are a separate concept and are not part of Gaussian elimination.
Forgetting that the scalar in a Type 2 operation must be nonzero. Multiplying a row by zero destroys information and is never permitted.
Thinking the forward pass alone is enough. REF is useful for detecting properties (like rank), but you need the full backward pass to reach RREF and read off solutions cleanly.
Confusing the order of the backward pass. You must work from the rightmost (bottom) pivot upward, not the other way round.
⚠️ You will be asked to row-reduce matrices by hand. Showing each row operation explicitly is typically required for full marks.
⚠️ Errors compound: a single arithmetic mistake in an early row operation will propagate through every subsequent step. Double-check each operation before moving on.
⚠️ The distinction between REF and RREF is a common exam question. Know the extra conditions RREF imposes (leading 1s, zeros above pivots).
True or false: A matrix in RREF is also in REF.
Fill in the blank: The forward pass creates zeros ______ each pivot; the backward pass creates zeros ______ each pivot.
True or false: Multiplying a row by zero is a valid elementary row operation.
True or false: The forward pass of Gaussian elimination works from bottom to top.
Fill in the blank: In RREF, every leading entry equals ______.
Answers: 1. True. 2. below; above. 3. False (the scalar must be nonzero). 4. False (top to bottom). 5. 1.
Q: List the three types of elementary row operations.
A: (1) Swap two rows: Ri ↔ Rj. (2) Multiply a row by a nonzero scalar: Ri → cRi, c ≠ 0. (3) Add a scalar multiple of one row to another: Rj → Rj + cRi.
Q: In the forward pass, why do we swap rows before eliminating entries below a pivot?
A: We need a nonzero entry in the pivot position to use it for elimination. If the current top entry in that column is zero, swapping brings a nonzero entry into position.
Q: After the forward pass, what additional properties does the backward pass produce?
A: The backward pass scales each leading entry to 1 (using Type 2) and eliminates all entries above each leading 1 (using Type 3), converting REF into RREF.
Q: Why is Gaussian elimination considered a "constructive proof" of Theorem 2?
A: Because it does not merely assert that RREF exists; it provides an explicit algorithm (a sequence of row operations) that transforms any matrix into RREF.
This connects directly to solving linear systems (next set of notes), because once a matrix is in RREF the solution set can be read off immediately. Rank, which is defined by counting pivots in REF/RREF, determines whether a system has zero, one, or infinitely many solutions. Later in the course, the ideas here extend to determinants, invertibility, and change-of-basis computations.
Related Terms / Search Tags: Gaussian elimination, row reduction, row echelon form, REF, reduced row echelon form, RREF, elementary row operations, row swap, row scaling, row replacement, pivot, leading entry, forward elimination, back substitution, MATH 416, abstract linear algebra