Null space for $\mathcal{N}(A)$ given SVD of $A$

Question

Let $A \in \mathbb{R}^{m \times n}$ be a matrix with singular value decomposition

$$ A = U \tilde{\Sigma} V^{T}. $$

Let $\text{rank}(A) = r \leq \min(m, n)$. My textbook notes that the first $r$ columns of $U$ then constitute a basis for $\mathcal{R}(A)$ (the range of $A$). That makes sense, since $Ax = U \tilde{\Sigma} V^{T} x = U \tilde{x}$ where $\tilde{x} = \tilde{\Sigma}V^{T} x$.

However, my book also states that the first $n-r$ columns of $V$ constitute a basis for $\mathcal{N}(A)$ (the null space of $A$). Shouldn't it instead be that the last $n-r$ rows of $V$ are a basis for $\mathcal{N}(A)$? If we want $V^{T} x = 0$, then multiplication by $x$ must produce a linear combination of the rows of $V$ that sum to the zero vector.

Answer 1

The assertion is true if the singular values are ordered in a way that the first $n-r$ diagonal entries of $\tilde \Sigma$ are zero.

Let $v_1, v_2, \dots $ be the columns of $V$. Let $$v= \sum_{i=1}^{n-r}x_i v_i$$ be a linear combination of the first $n-r$ columns. This means that in the first row of $v$, there's a linear combination of the first row of the $v_i$s, in the second row the second and so on.

Thus we can write $v=Vx$, where $x= \begin{pmatrix}x_1\\ x_2\\ \vdots \\ x_{n-r}\\ 0 \\ \vdots \\0 \end{pmatrix}.$

Then we have that $V^T V = I$, so that

$$Av = U \tilde \Sigma V^T V x = U \tilde \Sigma x.$$

Now, since we required $\tilde \Sigma$ to be of a shape that the left-upper $(n-r)\times (n-r)$ block consists of zeros and this is precisely where $x$ doesn't have any zeros, so we get $$\tilde \Sigma x = 0, \mbox{ hence } Ax = 0.$$

If the zeros wouldn't be on the top of the diagonal of $\tilde \Sigma$, but on the bottom, then indeed, we'd need to look at the last $n-r$ columns of $V$.

Addendum: I'm pretty sure that you should be able to proof this with some kind of nice duality argument (since by $A= U\tilde \Sigma V^T$ we get $A^T = V \tilde \Sigma ^T U,$ which shows that the columns of $V$ span $\mathcal R(A^T) = (\mathcal N(A))^\perp$.)

Answer 2

Every matrix $$ \mathbf{A} \in \mathbb{C}^{m\times n}_{\rho} $$ has a singular value decomposition

$$ \begin{align} \mathbf{A} &= \mathbf{U} \, \Sigma \, \mathbf{V}^{*} \\ % &= % U \left[ \begin{array}{cc} \color{blue}{\mathbf{U}_{\mathcal{R}}} & \color{red}{\mathbf{U}_{\mathcal{N}}} \end{array} \right] % Sigma \left[ \begin{array}{cc} \mathbf{S}_{\rho\times \rho} & \mathbf{0} \\ \mathbf{0} & \mathbf{0} \end{array} \right] % V* \left[ \begin{array}{c} \color{blue}{\mathbf{V}_{\mathcal{R}}}^{*} \\ \color{red}{\mathbf{V}_{\mathcal{N}}}^{*} \end{array} \right] \\ % % &= % U \left[ \begin{array}{cc} \color{blue}{\mathbf{U}_{\mathcal{R}}} & \color{red}{\mathbf{U}_{\mathcal{N}}} \end{array} \right] % Sigma \left[ \begin{array}{cccc|cc} \sigma_{1} & 0 & \dots & & & \dots & 0 \\ 0 & \sigma_{2} \\ \vdots && \ddots \\ & & & \sigma_{\rho} \\\hline & & & & 0 & \\ \vdots &&&&&\ddots \\ 0 & & & & & & 0 \\ \end{array} \right] % V \left[ \begin{array}{c} \color{blue}{\mathbf{V}_{\mathcal{R}}}^{*} \\ \color{red}{\mathbf{V}_{\mathcal{N}}}^{*} \end{array} \right] \\ % & = % U \left[ \begin{array}{cccccccc} \color{blue}{u_{1}} & \dots & \color{blue}{u_{\rho}} & \color{red}{u_{\rho+1}} & \dots & \color{red}{u_{n}} \end{array} \right] % Sigma \left[ \begin{array}{cc} \mathbf{S} & \mathbf{0} \\ \mathbf{0} & \mathbf{0} \end{array} \right] % V \left[ \begin{array}{c} \color{blue}{v_{1}^{*}} \\ \vdots \\ \color{blue}{v_{\rho}^{*}} \\ \color{red}{v_{\rho+1}^{*}} \\ \vdots \\ \color{red}{v_{n}^{*}} \end{array} \right] % \end{align} $$

The $\rho$ singular values are ordered and satisfy $$ \sigma_{1} \ge \sigma_{2} \ge \dots \sigma_{1} > 0 $$

The column vectors are orthonormal basis vectors: $$ \begin{align} % R A \color{blue}{\mathcal{R} \left( \mathbf{A} \right)} &= \text{span} \left\{ \color{blue}{u_{1}}, \dots , \color{blue}{u_{\rho}} \right\} \\ % R A* \color{blue}{\mathcal{R} \left( \mathbf{A}^{*} \right)} &= \text{span} \left\{ \color{blue}{v_{1}}, \dots , \color{blue}{v_{\rho}} \right\} \\ % N A* \color{red}{\mathcal{N} \left( \mathbf{A}^{*} \right)} &= \text{span} \left\{ \color{red}{u_{\rho+1}}, \dots , \color{red}{u_{m}} \right\} \\ % N A \color{red}{\mathcal{N} \left( \mathbf{A} \right)} &= \text{span} \left\{ \color{red}{v_{\rho+1}}, \dots , \color{red}{v_{n}} \right\} \\ % \end{align} $$ The dimensions of the subspace matrices are $$ \begin{align} % \color{blue}{\mathbf{U}_{\mathcal{R}}} &\in \mathbb{C}^{m\times\rho} \\ % \color{blue}{\mathbf{V}_{\mathcal{R}}} &\in \mathbb{C}^{n\times\rho} \\ % \color{red}{\mathbf{U}_{\mathcal{N}}} &\in \mathbb{C}^{m\times (m-\rho)} \\ % \color{red}{\mathbf{V}_{\mathcal{N}}} &\in \mathbb{C}^{n\times (n-\rho)} \\ % \end{align} $$ To answer your question: Yes, the final $n-\rho$ columns of $\mathbf{V}$ are a span for $\color{red}{\mathbf{V}_{\mathcal{N}}}$.