# Singular value decomposition - subspace

it is me agian. I am stuck with the following sentence:

Let $A\in\mathbb{R}^{p\times q}$ with $\operatorname{rank}(A)=r<\min(p,q)$. Now by the definition of singular values, there exist a $(q-r+1)$-dimensional subspace $V$ of $\mathbb{R}^q$ such that $\|Av\|\leq\sigma_r(A)\|v\|$ for all $v\in V$.

I do not understand why the inequality holds. The singular value decomposition delivers me orthogonal matrices $U\in\mathbb{R}^{p\times p}$ and $V\in\mathbb{R}^{q\times q}$ which columns form a orthogonal basis of $\mathbb{R}^p$ or $\mathbb{R}^q$ respectively. Since $r<\min(p,q)$, I pick $q-r+1$ vectors and those form my space $V$. Let $v\in V$ be arbitrary.$$\|Av\|=\|U\Sigma Vv\|\leq\|U\|\|\Sigma\|\|V\|\|v\|=\|\Sigma\|\|v\|$$

I do not know why I am allowed to size up with $\sigma_r(A)$ instead of $\sigma_1(A)$.

I am very confused and appreciate every help.

• Just to be clear about your notation, are you using the convention that $\sigma_1(A) \geq \cdots \geq \sigma_r(A)$? – Branimir Ćaćić Jun 7 '17 at 7:46
• Yes. The singular values are ordered from the largest to the smallest. – Hypertrooper Jun 7 '17 at 7:52

To avoid notational confusion, let's denote the desired $(q-r+1)$-dimensional subspace of $\mathbb{R}^n$ by $W$.
Suppose you have an SVD for $A$, which means $$A = U \Sigma V^T$$ for $U$ an orthogonal $m \times m$ matrix, $V$ an orthogonal $n \times n$ matrix, and $\Sigma$ the $m \times n$ matrix given by $$\Sigma_{ij} := \begin{cases} \sigma_i(A) &\text{if 1 \leq i = j \leq r,}\\ 0 &\text{else.}\end{cases}$$ If you take a closer look at the matrix multiplications above, this is equivalent to saying that the columns $\{U_1,\dotsc,U_m\}$ of $U$ form an orthonormal basis for $\mathbb{R}^m$ and the columns $\{V_1,\dotsc,V_n\}$ of $U$ form an orthonormal basis for $\mathbb{R}^n$ such that $$AV_i = \begin{cases} \sigma_i(A)U_i &\text{if 1 \leq i \leq r,}\\ 0 &\text{if r+1\leq i \leq n;} \end{cases}$$ in particular, it follows that $\{V_{i+1},\dotsc,V_n\}$ is a basis for $\ker A$. Given this, it's easy to figure out for which values of $i$ you get $$\|AV_i\| \leq \sigma_r(A) \|V_i\|.$$ So, does this give you a clue as to what your subspace $W$ will be? Mind you, you will need to check that $W$ really does do the job---to do so, you may need to remember that $\{V_1,\dotsc,V_n\}$ is an orthonormal basis for $\mathbb{R}^n$.
• Thank you! It helped a lot. The subspace $W$ will be the span of $V_r,V_{r+1},\ldots,V_n$. – Hypertrooper Jun 8 '17 at 15:49