Rank, Nullity and the Four Fundamental Subspaces

Column space, row space, null space and left null space, the definition and computation of rank, the rank–nullity theorem, rank inequalities for sums and products, rank of special matrices (outer products, Gram matrices), full-rank matrices and the invertible matrix theorem.

The four fundamental subspaces

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

Subspace	Definition	Lives in	Dimension
Column space $C(A)$	$\{A\mathbf x\}$ — span of the columns	$\mathbb R^m$	$r$
Row space $C(A^\top)$	span of the rows	$\mathbb R^n$	$r$
Null space $N(A)$	$\{\mathbf x : A\mathbf x = \mathbf 0\}$	$\mathbb R^n$	$n - r$
Left null space $N(A^\top)$	$\{\mathbf y : A^\top\mathbf y = \mathbf 0\}$	$\mathbb R^m$	$m - r$

They pair up as orthogonal complements: $N(A) = C(A^\top)^\perp$ in $\mathbb R^n$ and $N(A^\top) = C(A)^\perp$ in $\mathbb R^m$ .

A maps the row space one-to-one onto the column space and sends the null space to zero.

Rank

The rank of $A$ is the number of pivots after elimination, equivalently:

the dimension of the column space (column rank) = the dimension of the row space (row rank);
the maximum number of linearly independent columns (or rows);
the size of the largest non-zero minor (largest square sub-matrix with non-zero determinant);
the number of non-zero singular values.

Computing rank: row-reduce and count non-zero rows. To find a basis of $C(A)$ , take the original columns of $A$ in the pivot positions; for $C(A^\top)$ , take the non-zero rows of the echelon form.

The rank–nullity theorem

\operatorname{rank}(A) + \operatorname{nullity}(A) = n\ (\text{number of columns}).

Interpretation: of the $n$ input dimensions, $r$ survive (map to the column space) and $n - r$ are crushed to zero. For a linear map $T: V \to W$ , $\dim\operatorname{range}T + \dim\ker T = \dim V$ .

Rank inequalities

Result	Statement
Bounds	$0 \le \operatorname{rank}A \le \min(m, n)$
Transpose	$\operatorname{rank}A^\top = \operatorname{rank}A$
Product	$\operatorname{rank}(AB) \le \min(\operatorname{rank}A, \operatorname{rank}B)$
Sylvester	$\operatorname{rank}(AB) \ge \operatorname{rank}A + \operatorname{rank}B - n$ ( $n$ = inner dimension)
Invertible factor	$\operatorname{rank}(PA) = \operatorname{rank}(AQ) = \operatorname{rank}A$ for invertible $P, Q$
Sum	$\operatorname{rank}(A + B) \le \operatorname{rank}A + \operatorname{rank}B$
Gram matrices	$\operatorname{rank}(A^\top A) = \operatorname{rank}(AA^\top) = \operatorname{rank}A$
Outer product	$\operatorname{rank}(\mathbf u\mathbf v^\top) = 1$ for non-zero $\mathbf u, \mathbf v$
Diagonalisable	rank = number of non-zero eigenvalues

Full rank and the invertible matrix theorem

Full column rank ( $r = n \le m$ ): columns independent, $N(A) = \{\mathbf 0\}$ , $A^\top A$ invertible, $A\mathbf x = \mathbf b$ has at most one solution. Needed for the least-squares formula.
Full row rank ( $r = m \le n$ ): rows independent, $C(A) = \mathbb R^m$ , $A\mathbf x = \mathbf b$ always solvable.

For square $A$ ( $n \times n$ ), the following are equivalent: $A$ is invertible; $\operatorname{rank}A = n$ ; $N(A) = \{\mathbf 0\}$ ; the columns form a basis of $\mathbb R^n$ ; $\det A \ne 0$ ; 0 is not an eigenvalue; $A\mathbf x = \mathbf b$ has a unique solution for every $\mathbf b$ ; $A^\top$ is invertible; all singular values are positive.

Rank in data science

A data matrix with $n$ samples and $p$ features has rank $\le \min(n, p)$ ; perfectly collinear features reduce rank and make $X^\top X$ singular (the reason for ridge regression).
Low-rank approximation (truncated SVD) compresses data and is the basis of PCA and recommender systems.