Row Reduced Echelon Form
Source inspiration: (Mathew 2000-2019).
Background
To solve a linear system
\[ A\mathbf{x} = \mathbf{b}, \]
we form the augmented matrix
\[ M = [A\mid \mathbf{b}] \tag{1} \]
and apply elementary row operations until \(M\) is in reduced row echelon form (RREF).
A matrix is in reduced row echelon form if:
- Every nonzero row has leading entry \(1\).
- Each leading \(1\) is the only nonzero entry in its column.
- Leading \(1\) positions move strictly to the right as you go down rows.
- All zero rows (if any) are at the bottom.
Every matrix has exactly one reduced row echelon form.
Rank Criteria For Solution Type
Let \(A\) be the coefficient matrix and \(M=[A\mid \mathbf{b}]\) the augmented matrix.
If \(A\) is \(m\times n\), then:
\[ \operatorname{rank}(A)=\operatorname{rank}(M)=n \quad\Longrightarrow\quad \text{unique solution}, \tag{2} \]
\[ \operatorname{rank}(A)=\operatorname{rank}(M)<n \quad\Longrightarrow\quad \text{infinitely many solutions}, \tag{3} \]
\[ \operatorname{rank}(A)<\operatorname{rank}(M) \quad\Longrightarrow\quad \text{no solution (inconsistent)}. \tag{4} \]
Gauss-Jordan Algorithm
- Build \(M=[A\mid\mathbf{b}]\).
- Move left to right through pivot columns.
- For each pivot column, swap rows if needed to get a nonzero pivot.
- Scale the pivot row so the pivot becomes \(1\).
- Eliminate all other entries in that pivot column.
- Continue until pivot columns are reduced and all zero rows are at the bottom.
The resulting matrix directly reveals consistency, rank, and solution formulas.
Example 1 - Unique Solution
Solve
\[ \begin{aligned} x_1 + x_2 - 2x_3 &= 1,\\ 3x_1 + 2x_2 + 4x_3 &= -4,\\ 4x_1 + 3x_2 + 3x_3 &= -5. \end{aligned} \]
Step 1: Form the augmented matrix.
\[ \left[ \begin{array}{ccc|c} 1 & 1 & -2 & 1\\ 3 & 2 & 4 & -4\\ 4 & 3 & 3 & -5 \end{array} \right]. \]
Step 2: Row reduce to RREF.
\[ \left[ \begin{array}{ccc|c} 1 & 0 & 0 & 10\\ 0 & 1 & 0 & -13\\ 0 & 0 & 1 & -2 \end{array} \right]. \]
So
\[ \mathbf{x} = \begin{pmatrix}10\\-13\\-2\end{pmatrix}. \]
Verification:
| Row | Left-hand side | Right-hand side |
|---|---|---|
| 1 | \(10+(-13)-2(-2)=1\) | \(1\ \checkmark\) |
| 2 | \(3(10)+2(-13)+4(-2)=-4\) | \(-4\ \checkmark\) |
| 3 | \(4(10)+3(-13)+3(-2)=-5\) | \(-5\ \checkmark\) |
Because \(\operatorname{rank}(A)=\operatorname{rank}(M)=3=n\), the solution is unique.
Example 2 - Inconsistent System
Solve
\[ \begin{aligned} x_1 + x_2 - 2x_3 &= 1,\\ 3x_1 + 2x_2 + 4x_3 &= -4,\\ 4x_1 + 3x_2 + 2x_3 &= -4. \end{aligned} \]
Step 1: Build the augmented matrix.
\[ \left[ \begin{array}{ccc|c} 1 & 1 & -2 & 1\\ 3 & 2 & 4 & -4\\ 4 & 3 & 2 & -4 \end{array} \right]. \]
Step 2: Eliminate with \(R_2\leftarrow R_2-3R_1\) and \(R_3\leftarrow R_3-4R_1\).
\[ \left[ \begin{array}{ccc|c} 1 & 1 & -2 & 1\\ 0 & -1 & 10 & -7\\ 0 & -1 & 10 & -8 \end{array} \right]. \]
Step 3: Subtract row 2 from row 3.
\[ R_3\leftarrow R_3-R_2 \quad\Rightarrow\quad \left[ \begin{array}{ccc|c} 1 & 1 & -2 & 1\\ 0 & -1 & 10 & -7\\ 0 & 0 & 0 & -1 \end{array} \right]. \]
The last row says
\[ 0=-1, \]
which is impossible.
Verification (consistency check):
| Statement | Result |
|---|---|
| RREF contains row \([0\ 0\ 0\mid -1]\) | contradiction \(0=-1\) |
| Rank comparison | \(\operatorname{rank}(A)=2<3=\operatorname{rank}(M)\) |
| Conclusion | no solution |
So the system is inconsistent.
Example 3 - Infinitely Many Solutions
Solve
\[ \begin{aligned} x_1 + x_2 - 2x_3 &= 5,\\ 2x_1 + 3x_2 + 4x_3 &= -3,\\ 3x_1 + 4x_2 + 2x_3 &= 2. \end{aligned} \]
Step 1: Form and row reduce the augmented matrix.
\[ \left[ \begin{array}{ccc|c} 1 & 0 & -10 & 18\\ 0 & 1 & 8 & -13\\ 0 & 0 & 0 & 0 \end{array} \right]. \]
This corresponds to
\[ x_1-10x_3=18, \qquad x_2+8x_3=-13. \]
Step 2: Choose the free variable \(x_3=t\).
\[ x_1=18+10t, \qquad x_2=-13-8t, \qquad x_3=t. \]
So the full solution set is
\[ \mathbf{x}(t)= \begin{pmatrix} 18+10t\\ -13-8t\\ t \end{pmatrix}, \qquad t\in\mathbb{R}. \]
Verification:
| Row | Left-hand side after substitution | Right-hand side |
|---|---|---|
| 1 | \((18+10t)+(-13-8t)-2t=5\) | \(5\ \checkmark\) |
| 2 | \(2(18+10t)+3(-13-8t)+4t=-3\) | \(-3\ \checkmark\) |
| 3 | \(3(18+10t)+4(-13-8t)+2t=2\) | \(2\ \checkmark\) |
Because \(\operatorname{rank}(A)=\operatorname{rank}(M)=2<3=n\), there are infinitely many solutions.
Free Variables In Practice
When \(\operatorname{rank}(A)<n\) but the system is still consistent, you must choose one or more free variables. Every free variable generates a family of solutions, not a single point.
For underdetermined systems, RREF is especially useful because pivot columns identify dependent variables and nonpivot columns identify free variables immediately.
Summary
RREF gives a complete picture of a linear system in one framework:
- It provides a direct computational route to solutions.
- It classifies systems into unique, inconsistent, or infinitely many solutions through rank.
- It exposes free-variable structure cleanly when solutions are non-unique.