Orthonormal Bases for Four Subspaces using Singular Value Decomposition

2019-10-23


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

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

where $$\bs{U}\in\R^{m\times m}$$, $$\bs{\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}$$. $$\bs{\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} \bs{\Sigma}_r & \bs{O}\\ \bs{O} & \bs{O} \end{bmatrix}\begin{bmatrix} \bs{V}_r & \hat{\bs{V}}_r \end{bmatrix}' = \bs{U}_r\bs{\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}$$; $$\bs{\Sigma}_r\in\R^{r\times r}$$ is the top-left square block of $$\bs{\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 $$\bs{\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\bs{\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\bs{\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\bs{\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 $$\bs{\Sigma}$$ from the regular SVD gives

$\bs{\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\\ \bar{\bs{U}}_r'\bs{A}\bs{V}_r & \bar{\bs{U}}_r'\bs{A}\bar{\bs{V}}_r \end{bmatrix} = \begin{bmatrix} \bs{\Sigma}_r & \bs{O}\\ \bs{O} & \bs{O} \end{bmatrix}$

and thus

$\begin{bmatrix} \bs{U}_r'\bs{A}\bar{\bs{V}}_r\\ \bar{\bs{U}}_r'\bs{A}\bar{\bs{V}}_r \end{bmatrix} = \begin{bmatrix} \bs{O} \\ \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.