Alessio Borgi

Alessio Borgi

PhD in Graph Neural Networks and Generative AI 👨🏻‍💻🤖

Matrices as Linear Maps: Span, Rank, and the Subspaces They Create

7 minute read

Published:

TL;DR: Reading \(Ax\) as a linear combination of the columns of \(A\) makes almost everything else immediate. The reachable outputs are exactly the span of the columns, the column space, and its dimension is the rank. Whatever the map destroys lives in the null space. Rank–nullity says the domain is exactly split between the two: \(\operatorname{rank}(A) + \dim\ker(A) = n\). Matrix multiplication is composition of maps; conjugation \(P^{-1}AP\) is the same map read in a different basis.

Two readings of \(Ax\)

The mechanical reading of \(Ax\) is “row \(i\) of \(A\) dotted with \(x\)”. It is correct and it explains nothing.

The useful reading is by columns. If \(A\) has columns \(a_1,\dots,a_n\) and \(x = (x_1,\dots,x_n)^\top\), then

\[ Ax = x_1 a_1 + x_2 a_2 + \dots + x_n a_n . \]

So \(A\) takes the coordinates in \(x\) and uses them as mixing weights on a fixed set of output vectors. The set of everything you can produce this way is the span of the columns, the column space \(\operatorname{col}(A)\). Nothing outside it is reachable, which is exactly why \(Ax = b\) has a solution if and only if \(b \in \operatorname{col}(A)\).

A basis for a subspace is a spanning set with no redundancy, and every basis of a given subspace has the same size, that size is the dimension. The rank of \(A\) is \(\dim \operatorname{col}(A)\): the number of genuinely independent output directions. A \(1000 \times 1000\) matrix of rank 3 maps a thousand-dimensional space onto a three-dimensional plane inside it.

What the map destroys

If the columns are dependent, some non-zero combination of them gives zero. Those coefficient vectors form the null space (or kernel) \(\ker(A) = \{x : Ax = 0\}\), a subspace of the domain. Every vector in it is annihilated.

That gives the conservation law. Each input dimension either survives to contribute an independent output direction, or it is collapsed:

\[ \underbrace{\operatorname{rank}(A)}_{\text{dimensions that survive}} \;+\; \underbrace{\dim \ker(A)}_{\text{dimensions destroyed}} \;=\; n = \text{number of columns}. \]

This is rank–nullity, and read this way it is almost a tautology rather than a theorem. The genuinely non-obvious fact sitting alongside it is that row rank equals column rank: the number of independent rows and the number of independent columns are the same, so \(\operatorname{rank}(A) = \operatorname{rank}(A^\top)\) even when \(A\) is rectangular and the two spaces live in different places.

A worked example

Take

\[ A = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{pmatrix}, \qquad A : \mathbb{R}^3 \to \mathbb{R}^2 . \]

The first two columns \((1,4)^\top\) and \((2,5)^\top\) are independent, so the column space is all of \(\mathbb{R}^2\) and \(\operatorname{rank}(A) = 2\). The third column is redundant: \((3,6)^\top = -(1,4)^\top + 2\,(2,5)^\top\), since \(-1 + 4 = 3\) and \(-4 + 10 = 6\).

That dependency is the null space. It says \(-1 \cdot a_1 + 2 \cdot a_2 - 1 \cdot a_3 = 0\), so \(x = (1,-2,1)^\top\) satisfies \(Ax = 0\): check \(1 - 4 + 3 = 0\) and \(4 - 10 + 6 = 0\). The null space is the line spanned by \((1,-2,1)^\top\), of dimension 1.

QuantityValueLives in
\(\operatorname{rank}(A)\)2,
\(\operatorname{col}(A)\)all of \(\mathbb{R}^2\)codomain \(\mathbb{R}^2\)
\(\ker(A)\)\(\operatorname{span}\{(1,-2,1)^\top\}\)domain \(\mathbb{R}^3\)
Rank–nullity\(2 + 1 = 3\)\(= n\), the 3 columns

Geometrically: \(A\) flattens \(\mathbb{R}^3\) onto the plane \(\mathbb{R}^2\) by crushing one particular line to the origin. Solutions to \(Ax = b\) are never unique, add any multiple of \((1,-2,1)^\top\) and you get another.

Rank–nullity for a 2 by 3 matrix of rank 2The domain, a box labelled R three, is divided into two parts: a large region labelled row space of dimension 2, and a thin strip labelled null space of dimension 1 spanned by the vector (1, minus 2, 1). An arrow from the row space region to the codomain box, labelled R two, lands on a region labelled column space of dimension 2, which fills the whole codomain. A second arrow from the null space strip is labelled collapsed to zero. Two plus one equals three, the number of columns. domain, all of ℝ³ row space dim 2 null space, dim 1: span{(1,−2,1)} codomain, all of ℝ² column space dim 2 = rank nothing left over A is one-to-one here everything sent to 0 rank 2 + nullity 1 = 3 columns
Notice that the split happens on different sides: rank and nullity partition the domain, while the column space sits in the codomain. Confusing the two sides is the most common source of wrong answers about null spaces.

Multiplication is composition; conjugation is a change of basis

Because \((AB)x = A(Bx)\), the product \(AB\) is the map “do \(B\), then do \(A\)”. Non-commutativity stops being strange: rotating then projecting is not projecting then rotating. It also explains the shape rule, the output dimension of \(B\) must be the input dimension of \(A\), and the bound \(\operatorname{rank}(AB) \le \min(\operatorname{rank}A, \operatorname{rank}B)\), since a composition cannot recover dimensions an earlier stage destroyed.

The second reading of a product is a change of coordinates. Let \(P\) have as its columns a new basis, written in the old coordinates. Then \(P\) converts new coordinates into old ones, and \(P^{-1}\) does the reverse. So

\[ B = P^{-1} A P \]

reads right to left as: take a vector in the new coordinates, convert to old (\(P\)), apply the map (\(A\)), convert back (\(P^{-1}\)). \(A\) and \(B\) are the same linear map described in two languages. This is why similar matrices share rank, trace, determinant and eigenvalues, those are properties of the map, not of the description. It is also the whole point of diagonalisation: find the basis in which the description is as simple as possible.

Key Insight, rank is a statement about information, not about arithmetic: rank counts how many independent directions survive the map. Low rank means the output is confined to a thin slice of the space it nominally lives in, and that is why low-rank structure is exploitable, LoRA adapters, matrix factorisation for recommenders, and PCA all rest on the observation that a map with rank \(r\) can be stored and applied with \(r(m+n)\) numbers instead of \(mn\).
Interview trap, which space does it live in? For \(A \in \mathbb{R}^{m\times n}\), the null space is a subspace of \(\mathbb{R}^n\) (the domain) and the column space is a subspace of \(\mathbb{R}^m\) (the codomain). They generally have different ambient dimensions, so "orthogonal to each other" is meaningless. The correct orthogonality statement is that \(\ker(A)\) is the orthogonal complement of the row space inside \(\mathbb{R}^n\), which follows immediately from \(Ax = 0\) meaning every row is perpendicular to \(x\).

Why this matters in practice

Rank deficiency is what makes \(A^\top A\) singular in least squares, forcing ridge regularisation. Rank collapse in a transformer’s attention matrices is a real failure mode. And the entire family of parameter-efficient fine-tuning methods is a bet that the update to a weight matrix has far lower rank than the matrix itself.

Recap

  • \(Ax\) is a linear combination of the columns of \(A\); the column space is therefore the set of all reachable outputs, and the rank is its dimension.
  • The null space collects the input directions the map destroys. Rank–nullity, \(\operatorname{rank}(A) + \dim\ker(A) = n\), partitions the domain.
  • Row rank equals column rank, so \(\operatorname{rank}(A) = \operatorname{rank}(A^\top)\), even for rectangular \(A\).
  • \(AB\) means "\(B\) then \(A\)"; \(P^{-1}AP\) is the same map written in a different basis, which is why similar matrices share rank, trace, determinant and eigenvalues.
  • Null space lives in the domain, column space in the codomain, do not compare them directly.

References

  1. Strang, G. Introduction to Linear Algebra, 6th ed. Wellesley-Cambridge Press, 2023. See also MIT 18.06, lectures 5–10.
  2. Axler, S. Linear Algebra Done Right, 4th ed. Springer, 2024, the map-first treatment, free to read online.
  3. Deisenroth, M. P., Faisal, A. A., & Ong, C. S. Mathematics for Machine Learning, ch. 2. Cambridge University Press, 2020.
  4. Hu, E. J., et al. LoRA: Low-Rank Adaptation of Large Language Models. ICLR 2022.

You May Also Enjoy

The Standard Library Modules Worth Knowing Before You pip install

8 minute read

Published:

Python ships with a counter, a queue, a memoiser, a CLI parser, a test framework’s smaller cousin, and a JSON-safe date library already installed, most of what people reach for a package to solve is one import away.

Files and Context Managers: Why with Is Not Optional

9 minute read

Published:

A file object that falls out of scope without with does get closed eventually, but ‘eventually’ means whenever the garbage collector gets around to it, which is not a promise any program handling more than a handful of files can live with.

Errors and Exceptions: EAFP, the Hierarchy, and Reading a Traceback

9 minute read

Published:

Exceptions in Python are not exceptional. They are a normal control-flow mechanism that the language leans on so heavily that the idiomatic style is to try the operation and handle the failure, rather than check first, which is faster, shorter, and free of race conditions.