Systems of Linear Equations and Row Reduction

15 min read

Video: Dr Lynch’s MATH 231 lectures (YouTube playlists)

Before You Start: Prerequisite Check

Try This First

Before any matrices or terminology, solve the following problem. Write your two equations, then solve the system.

Two numbers add to 11. The first is 3 more than the second. Find both numbers.

The Encoding Principle

Any linear system can be encoded as a matrix. Once encoded, three simple operations on the rows, none of which changes the solution set, reduce the matrix to a form where the answer is readable.

This matters because the same encoding works whether the system has two variables or two thousand. The algorithm is the same; only the size changes. Every numerical solver in science, engineering, and data science is built on this idea.

Two facts make this work:

1. Encoding: Strip the variable names and write only the coefficients and constants.
2. Preservation: Row operations transform the matrix into an equivalent one with the same solution set.

Prerequisite Map

graph LR
    subgraph Entry["Entry Point"]
        A["Basic<br/>Algebra"]
    end

    subgraph ThisSkill["This Skill"]
        B["Systems and<br/>Row Reduction"]
    end

    subgraph Unlocks
        C["Vector Equations<br/>and Span"]
        D["Matrix Equation<br/>Ax = b"]
        E["Solution Sets<br/>and Free Variables"]
        F["Matrix Operations<br/>and Invertibility"]
    end

    A --> B
    B --> C
    B --> D
    B --> E
    B --> F

    style B fill:#d1fae5,stroke:#a565f0,stroke-width:3px

    click C "../ch20-sec13/la231-vector-equations-span.html"
    click D "../ch20-sec14/la231-matrix-equation-axb.html"
    click E "../ch20-sec15/la231-solution-sets-free-variables.html"
    click F "../ch20-sec21/la231-matrix-operations-invertibility.html"

Quick Reference

Row Operations at a Glance

All three operations preserve the solution set.

Reading the Result

Key Concepts

The Augmented Matrix

Given a linear system, the augmented matrix records the coefficients and the constants in a rectangular array. The vertical bar separates the coefficient columns from the constant column. Variable names are dropped; position carries all the information.

\[ \begin{cases} x_1 - 2x_2 + x_3 = 0 \\ 2x_2 - 8x_3 = 8 \\ -4x_1 + 5x_2 + 9x_3 = -9 \end{cases} \longrightarrow \left[\begin{array}{rrr|r} 1 & -2 & 1 & 0 \\ 0 & 2 & -8 & 8 \\ -4 & 5 & 9 & -9 \end{array}\right] \]

The three rows correspond to the three equations. The four columns correspond to $x_1$, $x_2$, $x_3$, and the constant.

Source: Lay, Linear Algebra and Its Applications, Section 1.1: Systems of Linear Equations.

Row Operations

Three operations on the rows of an augmented matrix produce an equivalent system, one with exactly the same solution set:

1. Swap two rows: $R_i \leftrightarrow R_j$
2. Scale a row by a nonzero constant: $R_i \to k R_i$ where $k \neq 0$
3. Replace a row by itself plus a scalar multiple of another: $R_i \to R_i + k R_j$

These correspond exactly to the elimination steps you performed in the opening problem. The matrix is a compact recording of those steps.

Important: Only row operations are allowed. Column operations on the coefficient portion of the matrix reassign which variable corresponds to which column, producing a different system.

Echelon Forms

Row echelon form (REF) requires:

1. All zero rows are at the bottom.
2. In each nonzero row, the first nonzero entry, called the pivot, lies strictly to the right of the pivot in the row above it.

Reduced row echelon form (RREF) adds:

3. Each pivot equals 1.
4. Every other entry in a pivot column equals 0 (above and below).

RREF is unique. Every matrix has exactly one RREF, regardless of the sequence of row operations used to reach it.

Row Echelon Form:              Reduced Row Echelon Form:
[ 2   5  -1 | 3 ]             [ 1   0   0 | 2  ]
[ 0   3   2 | 1 ]   ----->    [ 0   1   0 | -1 ]
[ 0   0  -4 | 8 ]             [ 0   0   1 | 3  ]
                               Pivot columns 1, 2, 3: unique solution.

Pivot Positions and What They Tell You

A pivot position is the location of a leading entry in a row of an echelon form. A pivot column is any column containing a pivot position.

The consistency test: A system is consistent if and only if the augmented column (the rightmost column) does not become a pivot column.

Source: Lay, Linear Algebra and Its Applications, Section 1.2: Row Reduction and Echelon Forms.

The Row Reduction Algorithm

Input: The augmented matrix $[A \mid \mathbf{b}]$.

Forward phase (to REF):

1. Find the leftmost column with a nonzero entry. Call this the current pivot column.
2. If the top entry of the pivot column is zero, swap the current row with a row below that has a nonzero entry in this column.
3. Apply row replacements to create zeros in all positions below the pivot.
4. Move down one row. Ignore the rows above and to the left. Repeat steps 1-3 on the remaining submatrix.

Backward phase (to RREF):

5. Scale each pivot row so the pivot equals 1.
6. Apply row replacements to create zeros in all positions above each pivot.

Worked Example: A Complete Row Reduction

Reduce the system from the Augmented Matrix section to RREF and give the solution.

Start: \[ \left[\begin{array}{rrr|r} 1 & -2 & 1 & 0 \\ 0 & 2 & -8 & 8 \\ -4 & 5 & 9 & -9 \end{array}\right] \]

Step 1. Pivot in column 1 is already $1$ in row 1. Eliminate below: $R_3 \to R_3 + 4R_1$. \[ \left[\begin{array}{rrr|r} 1 & -2 & 1 & 0 \\ 0 & 2 & -8 & 8 \\ 0 & -3 & 13 & -9 \end{array}\right] \]

Step 2. Pivot in column 2 will be $2$ in row 2. Scale: $R_2 \to \frac{1}{2} R_2$. \[ \left[\begin{array}{rrr|r} 1 & -2 & 1 & 0 \\ 0 & 1 & -4 & 4 \\ 0 & -3 & 13 & -9 \end{array}\right] \]

Step 3. Eliminate below the pivot in column 2: $R_3 \to R_3 + 3R_2$. \[ \left[\begin{array}{rrr|r} 1 & -2 & 1 & 0 \\ 0 & 1 & -4 & 4 \\ 0 & 0 & 1 & 3 \end{array}\right] \]

This is REF. Now the backward phase.

Step 4. Use the pivot $1$ in row 3, column 3 to eliminate above: $R_2 \to R_2 + 4R_3$, then $R_1 \to R_1 - R_3$. \[ \left[\begin{array}{rrr|r} 1 & -2 & 0 & -3 \\ 0 & 1 & 0 & 16 \\ 0 & 0 & 1 & 3 \end{array}\right] \]

Step 5. Eliminate above the pivot in column 2: $R_1 \to R_1 + 2R_2$. \[ \left[\begin{array}{rrr|r} 1 & 0 & 0 & 29 \\ 0 & 1 & 0 & 16 \\ 0 & 0 & 1 & 3 \end{array}\right] \]

Solution: $x_1 = 29$, $x_2 = 16$, $x_3 = 3$.

Verify: Row 1: $1(29) - 2(16) + 1(3) = 29 - 32 + 3 = 0$ (correct); Row 2: $2(16) - 8(3) = 32 - 24 = 8$ (correct); Row 3: $-4(29) + 5(16) + 9(3) = -116 + 80 + 27 = -9$ (correct).

Common Pitfalls

Practice Problems

Common Misconceptions

Mastery Checklist

Novice (Level 1-2):

• I can write the augmented matrix for any linear system.
• I can identify and apply each of the three row operations.
• I can determine whether a given matrix is in row echelon form.

Competent (Level 3-4):

• I can row-reduce any augmented matrix to RREF using the forward-backward algorithm.
• I can identify pivot columns and free variables from RREF.
• I can determine consistency from a partially reduced matrix before completing RREF.

Proficient (Level 5):

• I can write the complete parametric solution in vector form for systems with free variables.
• I can describe the solution set geometrically (empty, point, line, plane, or higher).
• I can explain why row operations preserve the solution set while column operations do not.

Mental Model

The Systematic Elimination Machine

Think of the augmented matrix as a table: rows are equations, columns are variables, and entries are coefficients. Row operations are the allowed moves: you can reorder rows, scale a row, or replace a row by a combination of itself and another. Each move preserves everything that matters (the solution set) while changing the appearance of the table.

The forward phase clears below each pivot, building a staircase from the top left. The backward phase clears above each pivot, erasing everything that obscures the answer. When the machine stops, each variable is either pegged to a specific value (pivot column) or left open as a free parameter (non-pivot column).

The deeper point: row operations are equivalences, not approximations. The original system and the RREF system have exactly the same solution set. Algebra is preserved; appearance changes. This is why the algorithm is trustworthy.

Connections

Looking ahead in MATH 231:

• Vector Equations and Span: the question “does $\mathbf{b}$ lie in the span of the columns of $A$?” is answered by row-reducing the augmented matrix $[A \mid \mathbf{b}]$, the same object you built here
• The Matrix Equation $Ax = \mathbf{b}$: matrix-vector multiplication reframes the same problem as a column combination; row reduction answers it
• Solution Sets and Free Variables: the parametric vector form from Level 5 becomes the systematic language for all solution sets

Real-world connections:

• Every circuit analysis based on Kirchhoff’s laws produces a linear system; row reduction solves it.
• Structural engineering load calculations produce systems of tens or hundreds of equations; computers apply the same algorithm.
• Data fitting by least squares requires solving a system of normal equations whose structure is governed by the pivot count.

Source: Lay, Linear Algebra and Its Applications, Section 1.1: Systems of Linear Equations; Section 1.2: Row Reduction and Echelon Forms.

Last updated: 2026-06-16

Watch and Read

• Lynch, MATH 231 lecture playlists (YouTube)Recorded MATH 231 lectures at EWU. Use them to see each topic worked through in a full class session.