Rank, subspaces, and projections

Ketan Suhaas Saichandran

linear-algebraranksubspacesprojectionsspanbasis

Span and basis

The span of vectors $v_1,\dots,v_k$ is every linear combination of them:

$$ \operatorname{span}(v_1,\dots,v_k) = \{c_1v_1+\cdots+c_kv_k \ :\ c_i\in\mathbb{R}\}, $$

itself a subspace: closed under addition and scaling, and it contains $0$ (take every $c_i=0$).

Intuition: the span is everywhere you can reach by stretching and adding the given vectors.

A basis of a subspace $S$ is a spanning set for $S$ that is also linearly independent (no vector in it is a combination of the others). Every basis of $S$ has the same number of vectors, its dimension $\dim S$.

Intuition: a basis is a minimal spanning set, just enough vectors to reach all of $S$ with no redundancy; dropping any one of them would shrink what's reachable.

$A$'s columns span $C(A)$, and a basis for that span is exactly its pivot columns, so:

$$ \operatorname{rank}(A) = \dim\operatorname{span}(a_1,\dots,a_n) = \dim C(A). $$

Rank

$\operatorname{rank}(A) = \dim C(A) = \dim C(A^T)$ = # independent columns = # independent rows = # pivots.

Intuition: the number of genuinely independent directions $A$ can produce.

Shapes

A rank-1 matrix is a column times a row (an outer product), which is why all its columns are multiples of one vector:

$$ \underbrace{\begin{pmatrix} 1 & 2 \\ 2 & 4 \\ 3 & 6 \end{pmatrix}}_{3\times2} =\underbrace{\begin{pmatrix} 1 \\ 2 \\ 3 \end{pmatrix}}_{3\times1}\underbrace{\begin{pmatrix} 1 & 2 \end{pmatrix}}_{1\times2}. $$

Intuition: rank $r$ means $A$ can be squeezed through an $r$-dimensional bottleneck: $(m\times r)(r\times n)$.

Row-reduce any $A$ (permuting columns if needed) and that bottleneck becomes visible directly, as the size of an identity block:

$$ R = \begin{pmatrix} I_r & F \\ 0 & 0 \end{pmatrix}. $$

$I_r$ marks the $r$ pivot columns; $F$ expresses every free column as a combination of the pivot columns; the zero rows are exactly the rows that were dependent on the others and reduced away.

Intuition: rank isn't an abstract count, it's the size of the identity block left standing after canceling every row and column you possibly could.

Solving $Ax = b$

Behaviour depends on shape and rank $r$ of $A \in \mathbb{R}^{m \times n}$. Here are the three shapes side by side ($m$ equations, $n$ unknowns):

Shapes

$$ \underbrace{\begin{pmatrix}\ast&\ast\\\ast&\ast\\\ast&\ast\\\ast&\ast\end{pmatrix}}_{\text{tall, } m>n} \begin{pmatrix}x_1\\x_2\end{pmatrix}=\begin{pmatrix}b_1\\b_2\\b_3\\b_4\end{pmatrix}, $$

$$ \underbrace{\begin{pmatrix}\ast&\ast&\ast&\ast\\\ast&\ast&\ast&\ast\end{pmatrix}}_{\text{wide, } m<n} \begin{pmatrix}x_1\\x_2\\x_3\\x_4\end{pmatrix}=\begin{pmatrix}b_1\\b_2\end{pmatrix}, $$

$$ \underbrace{\begin{pmatrix}\ast&\ast&\ast\\\ast&\ast&\ast\\\ast&\ast&\ast\end{pmatrix}}_{\text{square, } m=n} \begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix}=\begin{pmatrix}b_1\\b_2\\b_3\end{pmatrix}. $$

Intuition: tall means more equations than unknowns (over-constrained); wide means fewer equations than unknowns (under-constrained); square is balanced.

Each case specializes the block form $R=\begin{pmatrix}I_r&F\\0&0\end{pmatrix}$ from above:

Tall ($m > n$), full column rank $r = n$: $N(A) = \{0\}$, so at most one solution. No column is free, so $F$ vanishes and only the zero rows remain:

$$ R = \begin{pmatrix} I_n \\ 0 \end{pmatrix}. $$

Wide ($m < n$), full row rank $r = m$: $C(A) = \mathbb{R}^m$, so always consistent; $n - r$ free variables $\Rightarrow$ infinitely many solutions. No row is redundant, so no zero rows survive, and every non-pivot column lands in $F$:

$$ R = \begin{pmatrix} I_m & F \end{pmatrix}. $$

Square ($m = n$): full rank $\Rightarrow$ invertible, unique $x = A^{-1}b$ for every $b$; neither $F$ nor zero rows survive:

$$ R = I_n. $$

Rank-deficient $\Rightarrow$ no solution or infinitely many, depending on $b$.

Vector space, subspace

Vector space $V$: closed under addition and scalar multiplication, $0 \in V$. Subspace $S \subseteq V$: a subset that is itself a vector space.

Intuition: a subspace is a flat slice of the space that passes through the origin.

Fundamental subspaces

For $A\in\mathbb{R}^{m\times n}$ with $\operatorname{rank}(A) = r$, four subspaces:

Column space $C(A) \subseteq \mathbb{R}^m$, $\dim = r$
Null space $N(A) = \{x : Ax = 0\} \subseteq \mathbb{R}^n$, $\dim = n - r$
Row space $C(A^T) \subseteq \mathbb{R}^n$, $\dim = r$
Left null space $N(A^T) \subseteq \mathbb{R}^m$, $\dim = m - r$

Intuition: $C(A)$ is everywhere $Ax$ can reach; $N(A)$ is everything that collapses to $0$.

$$ N(A) \perp C(A^T) \ \text{in } \mathbb{R}^n, \qquad N(A^T) \perp C(A) \ \text{in } \mathbb{R}^m. $$

Projection, via the residual

Intuition: the closest point in a subspace is the one whose leftover error is perpendicular to it.

Onto $C(A)$: write $p = A\hat x$, residual $e = b - A\hat x$. Require $e \perp C(A)$, i.e. $A^Te = 0$:

$$ A^T(b - A\hat x) = 0 \;\Rightarrow\; A^TA\,\hat x = A^Tb \;\Rightarrow\; \hat x = (A^TA)^{-1}A^Tb \;\Rightarrow\; p = \underbrace{A(A^TA)^{-1}A^T}_{P}\,b. $$

Tracking shapes ($A$ tall, $m\times n$): the middle factor is small, the outer factors are tall and wide, and $P$ ends up $m\times m$ while only having rank $n$:

Shapes

$$ P=\underbrace{A}_{m\times n}\ \underbrace{(A^TA)^{-1}}_{n\times n}\ \underbrace{A^T}_{n\times m}\in\mathbb{R}^{m\times m}, \qquad \hat x=\underbrace{(A^TA)^{-1}A^T}_{n\times m}\,\underbrace{b}_{m\times1}\in\mathbb{R}^{n}. $$

The big picture

$A$ is a map taking a vector from one space ($\mathbb{R}^n$) to another ($\mathbb{R}^m$). It's constrained both ways: it can't reach every point of the output space, and it can't keep every input alive: some vectors just die to $0$.

$$ \mathbb{R}^m = C(A) \oplus N(A^T), \qquad \mathbb{R}^n = C(A^T) \oplus N(A). $$

Output side. Every $b$ splits uniquely into a reachable part and a part $A$ is blind to:

$$ b = b_{\text{col}} + b_\perp, \quad b_{\text{col}} \in C(A), \ b_\perp \in N(A^T). $$

$Ax$ can only ever land in $C(A)$, so $b_\perp$ can never be reached; the best we can do is $Ax = b_{\text{col}}$, exactly the projection above.

Intuition: $b_\perp$ is the part of $b$ that $A$ is structurally blind to.

Input side. Every $x$ splits uniquely too:

$$ x = x_{\text{row}} + x_{\text{null}}, \quad x_{\text{row}} \in C(A^T), \ x_{\text{null}} \in N(A). $$

$$ Ax = A(x_{\text{row}} + x_{\text{null}}) = Ax_{\text{row}} + \underbrace{Ax_{\text{null}}}_{=\,0} = Ax_{\text{row}}. $$

The null-space part of $x$ is invisible to $A$: only $x_{\text{row}}$ ever matters.

Intuition: $A$ only ever "sees" the row-space part of its input.

Together: $A$ is a bijection from the row space onto the column space, with $N(A)$ and $N(A^T)$ as the blind spots on either side.