The singular value decomposition (SVD) can be used to get orthonormal bases for each of the four subspaces: the column space $\newcommand{1}[1]{\unicode{x1D7D9}_{\{#1\}}}\newcommand{Corr}{\text{Corr}}\newcommand{E}{\text{E}}\newcommand{Cov}{\text{Cov}}\newcommand{Var}{\text{Var}}\newcommand{span}{\text{span}}\newcommand{bs}{\mathbf}\newcommand{R}{\mathbb{R}}\newcommand{rank}{\text{rank}}\newcommand{\norm}[1]{\left\lVert#1\right\rVert}\newcommand{diag}{\text{diag}}\newcommand{tr}{\text{tr}}\newcommand{braket}[1]{\left\langle#1\right\rangle}\newcommand{C}{\mathbb{C}}C(\bs{A})$, the null space $N(\bs{A})$, the row space $C(\bs{A}')$, and the left null space $N(\bs{A}')$.

In this post, we denote SVD of matrix $\bs{A}\in\R^{m\times n}$ as

$$ \bs{A} = \bs{U}\boldsymbol{\Sigma}\bs{V}' $$

where $\bs{U}\in\R^{m\times m}$, $\boldsymbol{\Sigma}\in\R^{m\times n}$ and $\bs{V}\in\R^{n\times n}$. $\bs{U}$ and $\bs{V}$ are orthonormal, namely $\bs{U}'\bs{U}=\bs{V}'\bs{V}=\bs{I}$. $\boldsymbol{\Sigma}$ is diagonal (despite being rectangle), which means all entries $\sigma_{ij}$ are zero if $i\neq j$. $\bs{V}'$ means transposition of $\bs{V}$. Apart from this regular form, we have full-rank SVD as

$$ \bs{A} = \begin{bmatrix} \bs{U}_r & \hat{\bs{U}}_r \end{bmatrix}\begin{bmatrix} \boldsymbol{\Sigma}_r & \bs{O}\newline \bs{O} & \bs{O} \end{bmatrix}\begin{bmatrix} \bs{V}_r & \hat{\bs{V}}_r \end{bmatrix}’ = \bs{U}_r\boldsymbol{\Sigma}_r\bs{V}_r' $$

where $r=\rank(A)$; $\bs{U}_r\in\R^{m\times r}$ is the block consisting of the first $r$ columns $\bs{U}$, $\hat{\bs{U}}_r\in\R^{m\times (m-r)}$ is the complement of $\bs{U}_r$ from $\bs{U}$; $\boldsymbol{\Sigma}_r\in\R^{r\times r}$ is the top-left square block of $\boldsymbol{\Sigma}$; $\bs{V}_r\in\R^{n\times r}$ is the block consisting of the first $r$ columns $\bs{V}$, $\hat{\bs{V}}_r\in\R^{n\times(n-r)}$ is the complement of $\bs{V}_r$ from $\bs{U}$. Note that orthonormality still holds for $\bs{U}_r$ and $\bs{V}_r$, and that now $\boldsymbol{\Sigma}_r$ is square and invertible.

Columns Space $C(\bs{A})$

Claim: $\bs{U}_r$ forms a basis of $C(\bs{A})$. We prove it as follows.

Proof. All we need is to show that $C(\bs{A})=C(\bs{U}_r)$. Left to right: assume $\bs{a}\in C(\bs{A})$, then we know $\exists \bs{x}$ s.t.

$$ \bs{a}=\bs{Ax}=\bs{U}_r\boldsymbol{\Sigma}_r\bs{V}_r’\bs{x}:= \bs{U}_r\bs{x}^* \in C(\bs{U}_r). $$

Right to left: assume $\bs{u}\in C(\bs{U}_r)$, then similarly $\exists \bs{x}$ s.t.

$$ \bs{u} = \bs{U}_r\bs{x} = \bs{A}\bs{V}_r\boldsymbol{\Sigma}_r^{-1}\bs{x} := \bs{A}\bs{x}^* \in C(\bs{A}). $$

Therefore, we conclude that $C(\bs{A})=C(\bs{U}_r)$.Q.E.D.

Row Space $C(\bs{A}')$

Claim: $\bs{V}_r$ gives a basis of $C(\bs{A}')$.

Proof. Similar to the column space, here we need to prove $C(\bs{A}')=C(\bs{V}_r)$. In fact, since SVD of $\bs{A}'$ is merely

$$ \bs{A}’ = \bs{V}_r\boldsymbol{\Sigma}_r\bs{U}_r’, $$

the conclusion follows right away from the previous one.Q.E.D.

Null Space $N(\bs{A})$

Claim: $\bar{\bs{V}}_r$ forms a basis of $N(\bs{A})$.

Proof. Solving $\boldsymbol{\Sigma}$ from the regular SVD gives

$$ \boldsymbol{\Sigma} = \bs{U}’\bs{A}\bs{V} = \begin{bmatrix} \bs{U}_r’\bs{A}\bs{V}_r & \bs{U}_r’\bs{A}\bar{\bs{V}}_r\newline \bar{\bs{U}}_r’\bs{A}\bs{V}_r & \bar{\bs{U}}_r’\bs{A}\bar{\bs{V}}_r \end{bmatrix} = \begin{bmatrix} \boldsymbol{\Sigma}_r & \bs{O}\newline \bs{O} & \bs{O} \end{bmatrix} $$

and thus

$$ \begin{bmatrix} \bs{U}_r’\bs{A}\bar{\bs{V}}_r\newline \bar{\bs{U}}_r’\bs{A}\bar{\bs{V}}_r \end{bmatrix} = \begin{bmatrix} \bs{O} \newline \bs{O} \end{bmatrix} \Rightarrow \bs{A}\bar{\bs{V}}_r = \bs{O} $$

which means $\bar{\bs{V}}_r\in N(\bs{A})$. Meanwhile, since $\bar{\bs{V}}_r$ is orthonormal with $\rank(\bar{\bs{V}}_r) = n-r = \dim(N(\bs{A}))$, we conclude that $\bar{\bs{V}}_r$ forms a basis of $N(\bs{A})$.Q.E.D.

Left Null Space $N(\bs{A}')$

Claim: $\bar{\bs{U}}_r$ gives a basis of $N(\bs{A}')$.

Proof. Similar to the null space of $N(\bs{A})$, if we consider $\bs{A}'$ in the place of $\bs{A}$, then we have right away that

$$ \bs{A}’\bar{\bs{U}}_r = \bs{O} \Rightarrow \bar{\bs{U}}_r\in N(\bs{A}’) $$

and because $\rank(\bar{\bs{U}}_r)=m-r=\dim(N(\bs{A}'))$, we conclude that $\bar{\bs{U}}_r$ forms a basis for the left null space of $\bs{A}$.Q.E.D.