Rank, rank–nullity and the four fundamental subspaces

Before this lesson: lesson 01 (matrices as maps, span, basis, independence). Time: about 70 minutes, plus the notebook.

---

Why this matters #

Rank answers one question: how many independent directions survive the map $x \mapsto Ax$? This one number decides whether $Ax = b$ has a solution, whether the solution is unique, and how much a matrix can be compressed. Low rank is everywhere in ML: a LoRA update $BA$ has rank at most $r$, an attention score matrix $QK^\top$ has rank at most the head dimension, and PCA keeps a low-rank part of the data. In science, the four subspaces of a graph's incidence matrix describe Kirchhoff's laws for electric circuits.

1. Predict first #

2. The picture #

$A$ is an $m \times n$ matrix, so it maps $\mathbb{R}^n \to \mathbb{R}^m$.

• The column space $C(A) = \{Ax : x \in \mathbb{R}^n\} \subseteq \mathbb{R}^m$ is the set of all outputs.
• The null space $N(A) = \{x : Ax = 0\} \subseteq \mathbb{R}^n$ is the set of inputs that are sent to zero.
• The rank $r = \dim C(A)$ is the number of independent output directions.

Start with a square example in $\mathbb{R}^3$. A matrix of rank 3 turns the unit cube into a solid box. A matrix of rank 2 flattens the cube into a parallelogram inside a plane: one input direction is lost. A matrix of rank 1 flattens everything onto a line: two input directions are lost.

Interactive figure: loading…

Rank–nullity is a counting statement about the $n$ input dimensions. Some of them are sent to 0 (that is $\dim N(A)$). The rest are carried one-to-one onto the output directions (that is $r$). So $r + \dim N(A) = n$: each input direction is counted exactly once.

Two more subspaces come from $A^\top$: the row space $C(A^\top) \subseteq \mathbb{R}^n$ (all combinations of the rows of $A$) and the left null space $N(A^\top) = \{y : A^\top y = 0\} \subseteq \mathbb{R}^m$.

Interactive figure: loading…

The figure is the whole lesson in one picture. $A$ sends the row space one-to-one onto the column space (both have dimension $r$), and it sends the null space to 0. The two pieces on each side are perpendicular, and their dimensions add up to $n$ on the input side and to $m$ on the output side.

3. Definitions and main results #

Echelon form, pivots and free columns #

Gaussian elimination subtracts multiples of one row from another (and swaps rows when needed) until the matrix has a staircase shape. Take

1. Row 2 − 2·row 1 gives $(0, 1, 1, -1)$. Row 3 − row 1 gives $(0, 1, 1, -1)$.
2. Row 3 − row 2 gives $(0, 0, 0, 0)$. This is the echelon form:

The first nonzero entry of each nonzero row is a pivot (boxed). Each pivot sits to the right of the pivot above it. Columns 1 and 2 contain pivots: they are the pivot columns. Columns 3 and 4 have no pivot: they are the free columns, and $x_3, x_4$ are the free variables of $Bx = 0$.

3. To reach the reduced row echelon form (RREF), make every pivot 1 and clear the entries above each pivot. Here row 1 − row 2 gives $(1, 0, 2, 1)$:

Rank by elimination #

Elimination multiplies $A$ on the left by an invertible matrix $E$ (the product of the row operations) and gives $R = EA$. Three facts make this useful:

1. The null space does not change. $Ax = 0 \iff EAx = 0$, because $E$ is invertible.
2. The row space does not change. Every row of $R$ is a combination of rows of $A$, and the other way round (use $E^{-1}$).
3. The column space does change, but the dependencies between columns do not. A combination of columns is zero in $A$ exactly when it is zero in $R$ (this is fact 1: the coefficients form a null vector).

Fact 3 on the example. In $R$ you can read the dependencies at once: column 3 of $R$ is $(2, 1, 0) = 2 \cdot (\text{column 1}) + 1 \cdot (\text{column 2})$, and column 4 is $(1, -1, 0) = \text{column 1} - \text{column 2}$. The same holds in $B$:

But the columns themselves changed: column 1 of $B$ is $(1, 2, 1)$, while column 1 of $R$ is $(1, 0, 0)$.

So the rank is the number of pivots. A basis of $C(A)$ is given by the pivot columns of the original $A$, and a basis of $C(A^\top)$ by the nonzero rows of $R$.

Row rank = column rank, and $A = CR$ #

The pivot columns of $A$ and the nonzero rows of $R$ give a factorization. Let $C$ be the $m \times r$ matrix of pivot columns of $A$, and let $R_r$ be the $r \times n$ matrix of nonzero rows of $\operatorname{rref}(A)$. Then

Why. Column $j$ of $R_r$ lists how column $j$ of $\operatorname{rref}(A)$ is built from its pivot columns, which are $e_1, \dots, e_r$. By fact 3, column $j$ of $A$ is built from the pivot columns of $A$ with the same coefficients: column $j$ of $A$ $= C \cdot (\text{column } j \text{ of } R_r)$. This is the column view of the product (lesson 01).

For the example, $C$ holds columns 1 and 2 of $B$:

Check column 4: $1 \cdot (1, 2, 1) - 1 \cdot (1, 3, 2) = (0, -1, -1)$ ✓.

Theorem (row rank = column rank). For every matrix, $\dim C(A^\top) = \dim C(A)$.

Proof.

1. Let $r = \dim C(A)$ (the column rank). Write $A = CR_r$ with $R_r$ of size $r \times n$.
2. By the row view of the product, every row of $A$ is a combination of the $r$ rows of $R_r$. So the row space of $A$ is spanned by $r$ vectors: $\dim C(A^\top) \le \dim C(A)$.
3. Apply step 2 to $A^\top$, whose rows are the columns of $A$: $\dim C(A) \le \dim C(A^\top)$.
4. The two inequalities give equality. $\blacksquare$

The factorization also shows the rank in the outer-product view: $A = CR_r$ is a sum of $r$ rank-1 matrices (column $k$ of $C$ times row $k$ of $R_r$). LoRA, low-rank attention and the truncated SVD (lesson 08) all use this form.

Rank–nullity #

Theorem (rank–nullity). For $A \in \mathbb{R}^{m \times n}$: $\quad \operatorname{rank}(A) + \dim N(A) = n.$

Proof.

1. Reduce $A$ to echelon form $R$. By fact 1, $N(R) = N(A)$.
2. $R$ has $r$ pivot columns and $n - r$ free columns.
3. For each free variable $j$: set $x_j = 1$, set the other free variables to $0$, and solve for the pivot variables by back substitution. Call the result $s_j$ (a special solution).
4. The $s_j$ are independent: $s_j$ has a $1$ in position $j$, where every other special solution has a $0$.
5. The $s_j$ span $N(A)$: for any $x \in N(A)$, the vector $x - \sum_j x_j s_j$ is in $N(A)$ and has all free variables equal to $0$; back substitution then forces its pivot variables to $0$ too, so it is the zero vector.
6. Hence $\dim N(A) = n - r$. $\blacksquare$

For $B$: the free variables are $x_3$ and $x_4$. With $x_3 = 1, x_4 = 0$ the rows of $R$ give $x_1 = -2$, $x_2 = -1$, so $s_3 = (-2, -1, 1, 0)$. With $x_3 = 0, x_4 = 1$: $x_1 = -1$, $x_2 = 1$, so $s_4 = (-1, 1, 0, 1)$. Two special solutions, and $4 - 2 = 2$ ✓.

The four subspaces #

Subspace	Lives in	Dimension
column space $C(A)$	$\mathbb{R}^m$	$r$
left null space $N(A^\top)$	$\mathbb{R}^m$	$m - r$
row space $C(A^\top)$	$\mathbb{R}^n$	$r$
null space $N(A)$	$\mathbb{R}^n$	$n - r$

The last two rows use rank–nullity for $A$; the first two use it for $A^\top$ (which has $m$ columns and the same rank $r$).

$N(A) \perp C(A^\top)$. If $Ax = 0$, then every row $a_i^\top$ of $A$ satisfies $a_i^\top x = 0$: $x$ is orthogonal to every row, so also to every combination of rows. The same argument for $A^\top$ gives $C(A) \perp N(A^\top)$. More is true: the two pieces fill their space.

Theorem (orthogonal complements). $N(A)$ and $C(A^\top)$ are orthogonal complements in $\mathbb{R}^n$: every $x \in \mathbb{R}^n$ splits in exactly one way as $x = x_{\text{row}} + x_{\text{null}}$ with $x_{\text{row}} \in C(A^\top)$ and $x_{\text{null}} \in N(A)$. The same holds for $C(A)$ and $N(A^\top)$ in $\mathbb{R}^m$.

Proof: the two pieces fill $\mathbb{R}^n$

1. They share only 0. If $x$ is in both, then $x \perp x$, so $\|x\|^2 = x^\top x = 0$ and $x = 0$.
2. Their bases together are independent. Take a basis $r_1, \dots, r_r$ of $C(A^\top)$ and a basis $s_1, \dots, s_{n-r}$ of $N(A)$. Suppose $\sum_i a_i r_i + \sum_j b_j s_j = 0$. Then $u = \sum_i a_i r_i = -\sum_j b_j s_j$ lies in both subspaces, so $u = 0$ by step 1. Each basis is independent, so all $a_i = 0$ and all $b_j = 0$.
3. They span $\mathbb{R}^n$. Step 2 gives $r + (n - r) = n$ independent vectors in $\mathbb{R}^n$, so they form a basis of $\mathbb{R}^n$ (lesson 01). Every $x$ is a combination of them: the part with the $r_i$ is $x_{\text{row}}$, the part with the $s_j$ is $x_{\text{null}}$.
4. The split is unique. If $x = p + q = p' + q'$ with $p, p'$ in the row space and $q, q'$ in the null space, then $p - p' = q' - q$ lies in both subspaces, so it is 0 by step 1.
5. For $C(A)$ and $N(A^\top)$, apply steps 1–4 to $A^\top$. $\blacksquare$

Two consequences you will use again and again:

• Solvability: $Ax = b$ has a solution exactly when $b \in C(A)$, that is, when $y^\top b = 0$ for every $y \in N(A^\top)$. (By the theorem, $b \in C(A)$ exactly when $b$ has no part in $N(A^\top)$.)
• Splitting: every $x$ splits as $x = x_{\text{row}} + x_{\text{null}}$. $A$ ignores $x_{\text{null}}$ and maps the row space one-to-one onto the column space.

$\operatorname{rank}(A^\top A) = \operatorname{rank}(A)$ #

Theorem. For every real matrix $A$, $N(A^\top A) = N(A)$, and so $\operatorname{rank}(A^\top A) = \operatorname{rank}(A)$.

Proof.

1. If $Ax = 0$, then $A^\top A x = A^\top 0 = 0$. So $N(A) \subseteq N(A^\top A)$.
2. If $A^\top A x = 0$, multiply on the left by $x^\top$: $0 = x^\top A^\top A x = (Ax)^\top (Ax) = \|Ax\|^2$. So $Ax = 0$, and $N(A^\top A) \subseteq N(A)$.
3. Both matrices have $n$ columns, so rank–nullity gives $\operatorname{rank}(A^\top A) = n - \dim N(A^\top A) = n - \dim N(A) = \operatorname{rank}(A)$. $\blacksquare$

Lessons 08 (SVD) and 12 (least squares) use this: $A^\top A$ is invertible exactly when $A$ has independent columns.

Answers to section 1. (1) No: $r \le 3$, so $\dim N(A) = 5 - r \ge 2$, and nonzero solutions always exist. (2) Yes, but only when $r = 3$, because then $C(A) = \mathbb{R}^3$.

4. Worked example #

Eliminate. Row 2 − 2·row 1 gives $(0, 0, 1, 2)$. Row 3 − 3·row 1 gives $(0, 0, 1, 2)$. Then row 3 − row 2 gives $0$:

Pivots in columns 1 and 3, so $r = 2$. Free variables: $x_2, x_4$. ($R$ is already reduced: the pivots are 1 and the entries above them are 0.)

Interactive figure: loading…

Special solutions.

• $x_2 = 1, x_4 = 0$: row 2 gives $x_3 = 0$; row 1 gives $x_1 = -2$. So $s_1 = (-2, 1, 0, 0)$.
• $x_2 = 0, x_4 = 1$: row 2 gives $x_3 = -2$; row 1 gives $x_1 = -1$. So $s_2 = (-1, 0, -2, 1)$.

All four subspaces.

• $C(A)$: columns 1 and 3 of $A$: $(1,2,3)$ and $(0,1,1)$. Dimension 2.
• $N(A)$: spanned by $s_1, s_2$. Dimension $4 - 2 = 2$. ✓
• $C(A^\top)$: rows $(1,2,0,1)$ and $(0,0,1,2)$ of $R$. Dimension 2.
• $N(A^\top)$: row 3 = row 1 + row 2, so $y = (-1, -1, 1)$ gives $A^\top y = 0$. Dimension $3 - 2 = 1$. ✓

$A = CR$. The pivot columns $(1, 2, 3)$ and $(0, 1, 1)$ times the two nonzero rows of $R$: column 4 of $A$ is $1 \cdot (1, 2, 3) + 2 \cdot (0, 1, 1) = (1, 4, 5)$ ✓, and column 2 is $2 \cdot (1, 2, 3)$ ✓.

Checks. $s_1 \cdot (1,2,0,1) = -2 + 2 = 0$ and $s_2 \cdot (0,0,1,2) = -2 + 2 = 0$: null space ⟂ row space. $Ax = b$ is solvable exactly when $y^\top b = -b_1 - b_2 + b_3 = 0$, that is, $b_3 = b_1 + b_2$.

5. In code #

The library computes all four subspaces, so you can check the hand computation. The notebook for this lesson has these cells and the exercises.

import numpy as np
from scipy.linalg import null_space, orth

A = np.array([[1, 2, 0, 1],
              [2, 4, 1, 4],
              [3, 6, 1, 5]], dtype=float)
r  = np.linalg.matrix_rank(A)   # counts singular values above a tolerance
N  = null_space(A)              # orthonormal basis of N(A),  shape (4, 2)
LN = null_space(A.T)            # orthonormal basis of N(Aᵀ), shape (3, 1)
Rb = orth(A.T)                  # orthonormal basis of C(Aᵀ), shape (4, 2)
print(r, N.shape[1], LN.shape[1])   # 2 2 1
print(np.abs(Rb.T @ N).max())       # ~6e-16: row space ⟂ null space
print(np.linalg.matrix_rank(A.T @ A))   # 2: rank(AᵀA) = rank(A)

In floating point, rank is a numerical idea: matrix_rank counts singular values above $\sigma_{\max} \cdot \max(m,n) \cdot \varepsilon$. A tiny perturbation makes almost every matrix full rank, so in practice you look at the singular values (lessons 08 and 13).

6. Where it shows up #

• Least squares and identifiability. If two features are collinear, $N(X) \ne \{0\}$ and infinitely many weight vectors fit equally well. Ridge regression picks one.
• Low rank in ML. LoRA: $\operatorname{rank}(BA) \le r$. Attention: $\operatorname{rank}(QK^\top) \le d_k$. Outer product: $\operatorname{rank}(uv^\top) = 1$. In general $\operatorname{rank}(AB) \le \min(\operatorname{rank} A, \operatorname{rank} B)$.
• Graphs and conservation laws. The incidence matrix $A$ of a directed graph has one row per edge and one column per node, with $+1$ at the start node and $-1$ at the end node of each edge (the convention of the notebook). Then:
  • $Av$ gives the potential differences along the edges;
  • for a connected graph, $N(A)$ is the constant potentials (dimension 1);
  • $A^\top y = 0$ means flows that are conserved at every node (Kirchhoff's current law); $\dim N(A^\top) = E - N + 1$, the number of independent loops;
  • $A^\top A$ is the graph Laplacian, the basis of spectral graph methods and GNNs.

7. Common mistakes #

• Taking the pivot columns of $R$ as a basis of $C(A)$. Elimination changes the column space; take those columns from the original $A$.
• Mixing up home spaces. $N(A) \subseteq \mathbb{R}^n$ (inputs), $C(A) \subseteq \mathbb{R}^m$ (outputs).
• Wrong nullity for $A^\top$. It is $m - r$, not $n - r$.
• "Full rank means invertible." Only for square matrices. A $3 \times 5$ matrix of rank 3 has full row rank, but its null space has dimension 2.
• Exact rank on floats. Use a tolerance on singular values.

8. Check yourself #

1. $A$ is $5 \times 3$ with rank 3. Give the dimensions of the four subspaces.
   Answer

   $C(A)$: 3 (in $\mathbb{R}^5$); $N(A^\top)$: 2; $C(A^\top)$: 3, so all of $\mathbb{R}^3$; $N(A)$: 0.
2. Why do row operations not change the null space?
   Answer

   They multiply by an invertible $E$, and $EAx = 0 \iff Ax = 0$.
3. What is $\operatorname{rank}(AA^\top)$?
   Answer

   $\operatorname{rank}(A)$. Apply the theorem $\operatorname{rank}(M^\top M) = \operatorname{rank}(M)$ to $M = A^\top$: $\operatorname{rank}(AA^\top) = \operatorname{rank}(A^\top) = \operatorname{rank}(A)$ (row rank = column rank).
4. In the worked example, what happens for $b = (1, 1, 0)$?
   Answer

   $b_3 \ne b_1 + b_2$, so $y^\top b = -2 \ne 0$: no solution. Only a least-squares solution exists.
5. Can a $4 \times 4$ matrix have $C(A) = N(A)$?
   Answer

   Yes, with $r = 2$ (needs $r = 4 - r$) and $A^2 = 0$. Example: ones at positions (1,3) and (2,4), zeros elsewhere; then $C(A) = N(A) = \operatorname{span}(e_1, e_2)$.
6. Write $\begin{pmatrix} 1 & 2 & 3 \\ 2 & 4 & 6 \end{pmatrix}$ as $CR$.
   Answer

   Rank 1: row 2 = 2·row 1, and the only pivot column is column 1. $C = \begin{pmatrix} 1 \\ 2 \end{pmatrix}$, $R = \begin{pmatrix} 1 & 2 & 3 \end{pmatrix}$, so the matrix is the outer product $\begin{pmatrix} 1 \\ 2 \end{pmatrix}\begin{pmatrix} 1 & 2 & 3 \end{pmatrix}$.

Recall cardsAnswer in your head first, then reveal. Add the cards to your review deck to see them again just before you would forget.

1. Define the rank of a matrix $A$.

   Show answer

2. State rank–nullity for $A \in \mathbb{R}^{m \times n}$.

   Show answer

3. An $m \times n$ matrix has rank $r$. Give the dimensions of $C(A)$, $N(A^\top)$, $C(A^\top)$ and $N(A)$.

   Show answer

4. Why is $N(A)$ orthogonal to the row space $C(A^\top)$?

   Show answer

5. After elimination $A \to R$, where do you take a basis of $C(A)$ from?

   Show answer

6. How do you test with the left null space whether $Ax = b$ has a solution?

   Show answer

7. What are $C$ and $R$ in the factorization $A = CR$?

   Show answer

8. Why does row rank equal column rank?

   Show answer

9. Why is $\operatorname{rank}(A^\top A) = \operatorname{rank}(A)$?

   Show answer

10. A $3 \times 5$ matrix has rank 3. What is $\dim N(A)$?

    Show answer

Add these cards to my reviewOpen the review →

9. Interview angle #

• "What is the rank of $uv^\top$? Of $AB$?" — 1 (for nonzero $u, v$); at most $\min(\operatorname{rank} A, \operatorname{rank} B)$.
• "When does least squares have a unique solution?" — when $X$ has full column rank ($N(X) = \{0\}$), which is when $X^\top X$ is invertible.
• "Why is LoRA cheap, and what can it not represent?" — $r(m+n)$ parameters instead of $mn$; it cannot represent an update of rank above $r$.
• "What does the null space of a graph Laplacian tell you?" — the connected components (one constant vector per component).

10. Practice #

The notebook for this lesson runs in Colab. It has four exercises, each with a check cell and a folded solution:

1. Write rref: Gauss–Jordan elimination with a tolerance, returning $R$ and the pivot columns.
2. Build a basis of $N(A)$ from the special solutions, and check rank–nullity on random low-rank matrices.
3. Decide whether $Ax = b$ is solvable with the left null space: $y^\top b = 0$ for every $y \in N(A^\top)$.
4. Build the incidence matrix of a small circuit graph and read Kirchhoff's laws from its four subspaces: one constant potential, $E - N + 1$ loops, and $A^\top A$ = the graph Laplacian.

11. Watch and read #

The Four Fundamental SubspacesGilbert Strang · MIT 18.06, lecture 10 · 49 min

Solving Ax = 0: Pivot Variables, Special SolutionsGilbert Strang · MIT 18.06, lecture 7 · 43 min

Inverse matrices, column space and null space3Blue1Brown · Essence of linear algebra, chapter 7 · 12 min

• Gilbert Strang, MIT 18.06 (2010), lecture 10: The four fundamental subspaces and lecture 7: Solving $Ax = 0$, with notes and problem sets.
• Gilbert Strang, A 2020 Vision of Linear Algebra (MIT OpenCourseWare): the first lecture builds $A = CR$ and row rank = column rank.
• 3Blue1Brown, Inverse matrices, column space and null space, the text version of chapter 7.
• Sheldon Axler, Linear Algebra Done Right, 4th edition, free PDF: §3B (null spaces and ranges; 3.21, the fundamental theorem of linear maps, is rank–nullity) and §3C (3.57: column rank equals row rank).