Chapter 04

Gaussian Elimination & Row Reduction

00 · Symbol Glossary

$\sim$tilde — row equivalence

Row equivalence. $A \sim B$ means matrix $B$ was obtained from $A$ by a sequence of elementary row operations. Row-equivalent matrices have the same solution set — they encode the same system.

$R_i$R sub i — row i

The $i$ -th row of a matrix. Used in row operation notation: $R_2 \to R_2 - 3R_1$ means replace row 2 with row 2 minus 3 times row 1.

$\text{rank}(A)$rank of A

The number of pivot positions in the row echelon form of $A$ . Equals the dimension of the column space — the number of linearly independent columns. A fundamental measure of how much information $A$ carries.

$n - r$n minus r — nullity

The number of free variables in $A\mathbf{x} = \mathbf{0}$ , where $n$ is the number of columns and $r = \text{rank}(A)$ . Called the nullity of $A$ . The rank-nullity theorem states $\text{rank}(A) + \text{nullity}(A) = n$ .

01 · Row Echelon Form

Chapter 3 introduced row operations informally. Gaussian elimination is the systematic algorithm that applies them to reach a standard form where the solution is easy to read off.

A matrix is in row echelon form (REF) when it has a "staircase" pattern of leading nonzero entries descending from upper-left to lower-right.

Definition — Row Echelon Form (REF)

A matrix is in row echelon form if:

All zero rows are at the bottom.
Each row's leading entry (leftmost nonzero entry) is strictly to the right of the leading entry of the row above it.
All entries below a leading entry in its column are zero.

\begin{pmatrix}\mathbf{*}&*&*&*\\ 0&\mathbf{*}&*&*\\ 0&0&\mathbf{*}&*\\ 0&0&0&0\end{pmatrix}

$*$ — any nonzero value. Bold entries are pivot positions — the leading nonzero entries forming the staircase. The bottom row of all zeros indicates a free variable or dependent equation.

Definition — Reduced Row Echelon Form (RREF)

A matrix is in reduced row echelon form if it satisfies all REF conditions plus:

Each pivot (leading entry) equals exactly 1.
Each pivot is the only nonzero entry in its column.

\begin{pmatrix}1&0&*&0\\ 0&1&*&0\\ 0&0&0&1\\ 0&0&0&0\end{pmatrix}

RREF is unique — every matrix has exactly one RREF. REF is not unique — different row operation sequences may produce different REFs for the same matrix.

REF vs RREF

Gaussian elimination produces REF, then back-substitution solves. Gauss-Jordan elimination continues further to produce RREF, from which the solution can be read directly without back-substitution. Both give the same answer; RREF requires more computation but eliminates the back-substitution step.

02 · Gaussian Elimination Algorithm

Gaussian elimination proceeds column by column, left to right. In each column it creates zeros below the current pivot position.

Definition — Pivot Position and Pivot Column

A pivot position is a location in a matrix corresponding to a leading entry in the REF. A pivot column is any column that contains a pivot position. Free columns are columns with no pivot — they correspond to free variables.

Step-by-step — Gaussian Elimination on $\left(\begin{array}{ccc|c}0&2&-4&6\\3&-1&2&4\\6&-3&8&2\end{array}\right)$

Locate the first pivot column: column 1 has the leftmost nonzero entry. Current column 1 entries: $0, 3, 6$ . The top entry is 0 — swap rows to put a nonzero entry in position $(1,1)$ .

$R_1 \leftrightarrow R_2$ : matrix becomes $\left(\begin{array}{ccc|c}3&-1&2&4\\0&2&-4&6\\6&-3&8&2\end{array}\right)$ .

Eliminate below pivot $(1,1) = 3$ : zero out entries in column 1 below row 1.

$R_3 \to R_3 - 2R_1$ : $(6-6,\ -3-(-2),\ 8-4,\ 2-8) = (0,\ -1,\ 4,\ -6)$ .

Matrix: $\left(\begin{array}{ccc|c}3&-1&2&4\\0&2&-4&6\\0&-1&4&-6\end{array}\right)$ . Row 1 is the pivot row — it is now frozen.

Move to column 2, row 2. Pivot position $(2,2) = 2$ . Eliminate below:

$R_3 \to R_3 + \frac{1}{2}R_2$ : $(0+0,\ -1+1,\ 4+(-2),\ -6+3) = (0,\ 0,\ 2,\ -3)$ .

Matrix (REF): $\left(\begin{array}{ccc|c}3&-1&2&4\\0&2&-4&6\\0&0&2&-3\end{array}\right)$ .

Read off the REF: three pivots (positions $(1,1)$ , $(2,2)$ , $(3,3)$ ). No free variables. $\text{rank}(A) = 3$ .

Back-substitute to solve: From row 3: $2x_3 = -3 \implies x_3 = -3/2$ . The $-3$ came from the augmented column; dividing by $2$ (the pivot) gives $x_3$ .

From row 2: $2x_2 - 4(-3/2) = 6 \implies 2x_2 + 6 = 6 \implies x_2 = 0$ .

From row 1: $3x_1 - (0) + 2(-3/2) = 4 \implies 3x_1 - 3 = 4 \implies x_1 = 7/3$ .

Assemble the solution:

\mathbf{x} = \begin{pmatrix}7/3\\0\\-3/2\end{pmatrix}

Verify row 1:

3(7/3) + (-1)(0) + 2(-3/2) = 7 + 0 - 3 = 4

✓.

❌ Failure — Forgetting to Update the Augmented Column

When applying $R_i \to R_i + cR_j$ , the augmented column entry $b_i$ must also be updated: $b_i \to b_i + c \cdot b_j$ . Applying the operation only to the coefficient columns while leaving $b_i$ unchanged introduces an error that propagates silently through all subsequent steps. The resulting "solution" satisfies the modified system, not the original one.

03 · Gauss-Jordan Elimination and RREF

Gauss-Jordan continues where Gaussian elimination stops, eliminating upward as well to reach RREF.

Step-by-step — Gauss-Jordan on $\left(\begin{array}{ccc|c}2&4&-2&2\\1&3&0&4\\-1&-2&1&-1\end{array}\right)$

Scale row 1 to create pivot = 1: $R_1 \to \frac{1}{2}R_1$ : $(1, 2, -1, 1)$ .

Matrix: $\left(\begin{array}{ccc|c}1&2&-1&1\\1&3&0&4\\-1&-2&1&-1\end{array}\right)$ .

Eliminate below pivot $(1,1)$ :

$R_2 \to R_2 - R_1$ : $(0, 1, 1, 3)$ . $R_3 \to R_3 + R_1$ : $(0, 0, 0, 0)$ .

Matrix: $\left(\begin{array}{ccc|c}1&2&-1&1\\0&1&1&3\\0&0&0&0\end{array}\right)$ .

Row 3 is all zeros — it contributes no constraint and indicates a free variable.

Eliminate above pivot $(2,2)$ (Gauss-Jordan step):

$R_1 \to R_1 - 2R_2$ : $(1, 2-2, -1-2, 1-6) = (1, 0, -3, -5)$ .

RREF: $\left(\begin{array}{ccc|c}1&0&-3&-5\\0&1&1&3\\0&0&0&0\end{array}\right)$ .

Identify pivots and free variables: pivots in columns 1 and 2. Column 3 has no pivot — $x_3 = t$ is a free variable.

Write solution directly from RREF: row 1: $x_1 - 3t = -5 \implies x_1 = -5 + 3t$ . Row 2: $x_2 + t = 3 \implies x_2 = 3 - t$ .

\mathbf{x} = \begin{pmatrix}-5\\3\\0\end{pmatrix} + t\begin{pmatrix}3\\-1\\1\end{pmatrix}, \quad t \in \mathbb{R}

04 · Rank and the Rank-Nullity Theorem

The rank of a matrix is the number of pivot positions in its REF (or RREF — both give the same count). It measures how much of the output space $\mathbb{R}^m$ the matrix can reach.

Definition — Rank and Nullity

For $A \in \mathbb{R}^{m \times n}$ :

\text{rank}(A) = \text{number of pivot positions in REF of } A

\text{nullity}(A) = n - \text{rank}(A) = \text{number of free variables in } A\mathbf{x} = \mathbf{0}

Rank-Nullity Theorem:

\text{rank}(A) + \text{nullity}(A) = n

The total number of columns equals the number of pivot columns plus the number of free columns.

✓ Example — Rank from RREF

$A = \begin{pmatrix}1&2&0&3\\0&0&1&-1\\0&0&0&0\end{pmatrix}$ is already in RREF.

Pivot positions: $(1,1)$ and $(2,3)$ — columns 1 and 3. $\text{rank}(A) = 2$ .

Free columns: 2 and 4 — so $x_2$ and $x_4$ are free variables. $\text{nullity}(A) = 2$ .

Check: $\text{rank} + \text{nullity} = 2 + 2 = 4 = n$ ✓ ( $A$ has 4 columns).

❌ Failure — Mistaking a Zero Row for a Free Variable

A zero row (all entries zero, including the augmented column) means a redundant equation — it adds no constraint and contributes no free variable. It is the zero rows that the rank-nullity theorem counts through the pivot columns, not through the zero rows themselves. The number of free variables equals $n - \text{rank}(A)$ , counting columns, not rows.

05 · Consistency via Rank

The rank of $A$ compared to the rank of $[A|\mathbf{b}]$ determines whether the system is consistent.

Theorem — Consistency Criterion

A\mathbf{x} = \mathbf{b} \text{ is consistent} \iff \text{rank}([A|\mathbf{b}]) = \text{rank}(A)

If $\text{rank}([A|\mathbf{b}]) = \text{rank}(A) + 1$ , then the augmented column introduced a new pivot — meaning $\mathbf{b}$ cannot be expressed as a linear combination of $A$ 's columns — and the system is inconsistent.

When consistent: if $\text{rank}(A) = n$ (no free variables), the solution is unique. If $\text{rank}(A) < n$ , there are $n - \text{rank}(A)$ free variables and infinitely many solutions.

✓ Example — Sensitivity Analysis via Rank

A risk factor model has 3 factors and 4 constraints on factor exposures. The exposure matrix $A \in \mathbb{R}^{4 \times 3}$ row-reduces to $\text{rank}(A) = 2$ . Two of the 4 constraints are redundant. The nullity is $3 - 2 = 1$ — one degree of freedom remains in factor allocation. Every basis portfolio that satisfies the constraints lies on a one-dimensional affine subspace.

06 · Practice Exercises

EXERCISE 4.1

Work column by column. In each column, find the pivot (first nonzero entry from the top in that column). Eliminate all entries below it. Move to the next column.

Augmented: $\left(\begin{array}{ccc|c}1&-2&3&9\\2&-1&4&8\\-1&3&-2&-3\end{array}\right)$ .

$R_2 \to R_2-2R_1$ : $(0,3,-2,-10)$ . $R_3 \to R_3+R_1$ : $(0,1,1,6)$ .

Matrix: $\left(\begin{array}{ccc|c}1&-2&3&9\\0&3&-2&-10\\0&1&1&6\end{array}\right)$ .

$R_2 \leftrightarrow R_3$ (convenient): $\left(\begin{array}{ccc|c}1&-2&3&9\\0&1&1&6\\0&3&-2&-10\end{array}\right)$ .

$R_3 \to R_3-3R_2$ : $(0, 3-3, -2-3, -10-18) = (0,0,-5,-28)$ . REF reached.

Back-sub: $-5x_3 = -28 \implies x_3 = 28/5$ . $x_2 = 6 - x_3 = 6 - 28/5 = 2/5$ . $x_1 = 9+2x_2-3x_3 = 9+4/5-84/5 = 9-80/5 = 9-16 = -7$ .

Solution: $\mathbf{x} = (-7,\ 2/5,\ 28/5)^T$ .

Apply Gaussian elimination to reach REF, then back-substitute: $x_1 - 2x_2 + 3x_3 = 9$ ; $2x_1 - x_2 + 4x_3 = 8$ ; $-x_1 + 3x_2 - 2x_3 = -3$ . Show every row operation.

EXERCISE 4.2

After reaching REF, continue with upward elimination to clear entries above each pivot. Then scale each pivot row so the pivot equals 1.

Start: $\left(\begin{array}{ccc|c}2&4&-2&4\\1&5&3&10\\-1&1&5&8\end{array}\right)$ .

$R_1 \to \frac{1}{2}R_1$ : $(1,2,-1,2)$ . $R_2 \to R_2-R_1$ : $(0,3,4,8)$ . $R_3 \to R_3+R_1$ : $(0,3,4,10)$ .

$R_3 \to R_3-R_2$ : $(0,0,0,2)$ . This gives row $(0,0,0|2)$ , i.e. $0=2$ . Inconsistent.

The system has no solution. $\text{rank}([A|\mathbf{b}]) = 3 > \text{rank}(A) = 2$ — the augmented column introduced a new pivot.

Apply Gauss-Jordan elimination to reach RREF: $2x_1 + 4x_2 - 2x_3 = 4$ ; $x_1 + 5x_2 + 3x_3 = 10$ ; $-x_1 + x_2 + 5x_3 = 8$ . Show every step. If the system is inconsistent, identify which row reveals the contradiction.

EXERCISE 4.3

Row reduce to RREF. Identify pivot columns (they determine the basic variables) and free columns (they determine the free variables). Each free variable gets its own parameter $t$ .

$A = \begin{pmatrix}1&3&-2&0\\2&6&-5&-2\\0&0&5&10\end{pmatrix}$ .

$R_2 \to R_2-2R_1$ : $(0,0,-1,-2)$ . Matrix: $\begin{pmatrix}1&3&-2&0\\0&0&-1&-2\\0&0&5&10\end{pmatrix}$ .

$R_3 \to R_3+5R_2$ : $(0,0,5-5,10-10)=(0,0,0,0)$ . Scale $R_2$ by $-1$ : $(0,0,1,2)$ .

$R_1 \to R_1+2R_2$ : $(1,3,0,4)$ . RREF: $\begin{pmatrix}1&3&0&4\\0&0&1&2\\0&0&0&0\end{pmatrix}$ .

Pivots in columns 1, 3. Free variables: $x_2 = s$ , $x_4 = t$ . Row 2: $x_3 = 2-2t$ . Wait — this is the homogeneous augmented form with $\mathbf{b}=0$ .

For $A\mathbf{x}=\mathbf{0}$ : RREF of $[A|0]$ . Same row ops. $x_3 = 0$ from $R_2$ . $x_1 = -3x_2 = -3s$ . Free: $x_2=s$ .

$\text{rank}(A) = 2$ , $\text{nullity}(A) = 4-2=2$ . Check: $2+2=4=n$ ✓.

For $A = \begin{pmatrix}1&3&-2&0\\2&6&-5&-2\\0&0&5&10\end{pmatrix}$ : (a) Find the RREF of $A$ . (b) State $\text{rank}(A)$ and $\text{nullity}(A)$ . (c) Verify the rank-nullity theorem.

EXERCISE 4.4

For the system to have a unique solution, $\text{rank}(A) = n = 3$ (no free variables) and the system must be consistent. Row reduce and find the condition on $k$ .

$\left(\begin{array}{ccc|c}1&2&1&4\\0&1&-1&2\\2&5&k&10\end{array}\right)$ .

$R_3 \to R_3-2R_1$ : $(0,1,k-2,2)$ . $R_3 \to R_3-R_2$ : $(0,0,k-2-(-1),2-2) = (0,0,k-1,0)$ .

For unique solution: row 3 must give a pivot, so $k-1 \neq 0 \implies k \neq 1$ .

If $k=1$ : row 3 is $(0,0,0,0)$ — free variable, infinitely many solutions. If $k \neq 1$ : three pivots, unique solution.

Condition for unique solution: $k \neq 1$ .

For what values of $k$ does the system $x_1+2x_2+x_3=4$ ; $x_2-x_3=2$ ; $2x_1+5x_2+kx_3=10$ have a unique solution? Row reduce and identify the condition on $k$ .

EXERCISE 4.5

The rank of a matrix equals the number of pivot columns. Count pivots in the RREF. Compare the rank to the number of columns and rows.

$A = \begin{pmatrix}2&-4&2\\-1&2&-1\\3&-6&3\end{pmatrix}$ . Rows 2 and 3 are $-\frac{1}{2}$ and $\frac{3}{2}$ times row 1.

$R_1 \to \frac{1}{2}R_1$ : $(1,-2,1)$ . $R_2 \to R_2+R_1$ : $(0,0,0)$ . $R_3 \to R_3-3R_1$ : $(0,0,0)$ . RREF: $\begin{pmatrix}1&-2&1\\0&0&0\\0&0&0\end{pmatrix}$ .

$\text{rank}(A)=1$ . $\text{nullity}(A)=3-1=2$ . The null space has dimension 2.

$A\mathbf{x}=\mathbf{0}$ : $x_1-2x_2+x_3=0$ , so $x_1=2s-t$ with $x_2=s$ , $x_3=t$ free. $\text{Null}(A) = s\begin{pmatrix}2\\1\\0\end{pmatrix}+t\begin{pmatrix}-1\\0\\1\end{pmatrix}$ .

Find the rank and nullity of $A = \begin{pmatrix}2&-4&2\\-1&2&-1\\3&-6&3\end{pmatrix}$ . Then find a basis for $\text{Null}(A)$ .

EXERCISE 4.6

A factor model is a system $F\mathbf{w} = \mathbf{r}$ where $F$ is the factor exposure matrix and $\mathbf{r}$ is the target factor return vector. Row reduce the augmented matrix $[F|\mathbf{r}]$ .

$F = \begin{pmatrix}1&0&2\\0&1&-1\\1&1&1\end{pmatrix}$ , $\mathbf{r} = \begin{pmatrix}3\\1\\4\end{pmatrix}$ .

Augmented: $\left(\begin{array}{ccc|c}1&0&2&3\\0&1&-1&1\\1&1&1&4\end{array}\right)$ . $R_3 \to R_3-R_1$ : $(0,1,-1,1)$ . $R_3 \to R_3-R_2$ : $(0,0,0,0)$ .

RREF: $\left(\begin{array}{ccc|c}1&0&2&3\\0&1&-1&1\\0&0&0&0\end{array}\right)$ . $w_3=t$ free. $w_2=1+t$ . $w_1=3-2t$ .

Solution: $\mathbf{w} = \begin{pmatrix}3\\1\\0\end{pmatrix}+t\begin{pmatrix}-2\\1\\1\end{pmatrix}$ . The free parameter $t$ represents a portfolio in the null space of $F$ — a factor-neutral overlay. Any value of $t$ achieves the same factor exposures. A risk manager would choose $t$ to minimise residual variance.

A three-factor model assigns factor exposures via $F\mathbf{w} = \mathbf{r}$ where $F = \begin{pmatrix}1&0&2\\0&1&-1\\1&1&1\end{pmatrix}$ and target exposures $\mathbf{r} = \begin{pmatrix}3\\1\\4\end{pmatrix}$ . Find all weight vectors $\mathbf{w}$ achieving these exposures. Interpret the free parameter.

07 · Summary

Term	Definition
REF	Staircase pattern: each leading entry to the right of the one above. Zeros below each pivot.
RREF	REF plus: each pivot equals 1, and is the only nonzero in its column. Unique for every matrix.
Pivot	Leading nonzero entry in a row of the REF. Determines a basic variable.
Free variable	Unknown corresponding to a non-pivot column. Can take any value $t \in \mathbb{R}$ .
Rank	Number of pivots in REF/RREF. $\text{rank}(A) = r$ .
Nullity	$n - r$ . Number of free variables. Dimension of $\text{Null}(A)$ .
Rank-nullity	$\text{rank}(A) + \text{nullity}(A) = n$ (number of columns). Always.
Consistency	Consistent $\iff$ $\text{rank}([A\mid\mathbf{b}]) = \text{rank}(A)$ .
Unique solution	Consistent and $\text{rank}(A) = n$ . No free variables.

Next: Determinants — the single number attached to a square matrix that reveals whether it is invertible and measures the scaling of volume under the linear transformation it represents.