# $SVD$ Exercise of Watkins' Fundamental of Matrix Computations

Apologies that this turned out a little long.

I have studied the Singular Value Decomposition in Fundamental of Matrix Computations by Watkins and I couldn't to solve the Exercise 4. 1. 16 which is a demonstration of the following theorem:

(Watkins) Theorem 4.1.1 (SVD Theorem) Let $$A\in \mathbb{R}^{n \times m}$$ be a nonzero matrix with rank $$r$$. Then $$A$$ can be expressed as a product $$\begin{equation} A = U \Sigma V^{T} \end{equation}$$ where $$U \in \mathbb{R}^{n \times n}$$ and $$V \in \mathbb{R}^{m \times m}$$ are orthogonal, and $$\Sigma \in \mathbb{R}^{n \times m}$$ is a rectangular "diagonal" matrix $$\begin{equation} \Sigma = \left( \begin{array}{cccccc} {\sigma_{1}} & {} & {} & {} & {} & {}\\ { } & {\sigma_2} & {} & {} & {} & {}\\ {} & {} & {\ddots} & {} & {} & {}\\ {} & {} & {} & {\sigma_r} & { } & {} \\ {} & {} & {} & {} & { } & {\ddots} \end{array} \right) \;\;\; \sigma_{1}\geq \sigma_2 \geq \cdots\geq \sigma_r > 0. \end{equation}$$

The Exercise is:

(Watkins) Exercise 4.1.16 In this exercise you will prove Theorem 4.1.1 by induction on $$r$$, the rank of $$A$$.

(a) Suppose $$A \in \mathbb{R}^{n \times m}$$ has rank 1. Let $$u_1 \in \mathbb{R}^{n}$$ be a vector in $$R(A)$$ such that $$|| u_1 ||_2 = 1$$. Show that every column of $$A$$ is a multiple of $$u_1$$. Show that $$A$$ can be written in the form $$A = \sigma_1 u_1 v_{1}^{T}$$, where $$v_1 \in \mathbb{R}^{m}$$, $$|| u_1 ||_2 = 1$$, and $$\sigma_1 > 0$$.

(b) Continuing from part (a), demonstrate that there is an orthogonal matrix $$U \in \mathbb{R}^{n \times n}$$ whose first column is $$u_1$$. (For example, $$U$$ can be a reflector that maps the unit vector $$e_1$$ to $$u_1$$.) Similarly there is an orthogonal $$V \in \mathbb{R}^{m \times m}$$ whose first column is $$v_1$$. Show that $$A = U \Sigma V^{T}$$, where $$\Sigma \in \mathbb{R}^{n \times m}$$ has only one nonzero entry, $$\sigma_1$$, in position $$(1,1)$$. Thus every matrix of rank 1 has an $$SVD$$.

(c) Now suppose $$A \in \mathbb{R}^{n \times m}$$ has rank $$r > 1$$. Let $$v_1$$ be a unit vector in the direction of maximum magnification by $$A$$, i.e., $$|| v_1 ||_2 = 1$$, and $$|| A v_1 ||_2 = \max_{|| v ||_{2} = 1} || Av||_2$$. Let $$\sigma_{1}=\left\|A v_{1}\right\|_{2}=\|A\|_{2}$$, and let $$u_1 = \sigma_{1}^{-1}Av_1$$. Let $$\tilde{U} \in \mathbb{R}^{n \times n}$$ and $$\tilde{V} \in \mathbb{R}^{m \times m}$$ be orthogonal matrices with first column $$u_1$$ and $$v_1$$, respectively. Let $$\tilde{A} = \tilde{U}^{T} A \tilde{V}$$, so that $$A = \tilde{U} \tilde{A} \tilde{V}^{T}$$. Show that $$\tilde{A}$$ has the form $$\begin{equation} \tilde{A}=\left[ \begin{array}{cc}{\sigma_{1}} & {z^{T}} \\ {0} & {\hat{A}}\end{array}\right], \end{equation}$$ where $$z \in \mathbb{R}^{m-1}$$ and $$\hat{A} \in \mathbb{R}^{(n-1) \times (m-1)}$$.

(d) Show that in matrix $$\tilde{A}$$ above the vector $$z$$ must be zero. You may do this as follows: Let $$w=\left[ \begin{array}{c}{\sigma_{1}} \\ {z}\end{array}\right] \in \mathbb{R}^{m}$$. Show that $$\|\tilde{A} w\|_{2} /\|w\|_{2} \geq \sqrt{\sigma_{1}^{2}+z^{T} z}$$. Then show that this inequality forces $$z = 0$$. Thus $$\begin{equation} \tilde{A}=\left[ \begin{array}{cc}{\sigma_{1}} & {0} \\ {0} & {\hat{A}}\end{array}\right]. \end{equation}$$

(e) Show that $$\hat{A}$$ has rank $$r-1$$. By the induction hypothesis $$\hat{A}$$ has an SVD $$\hat{A} = \hat{U} \hat{\Sigma} \hat{V}^{T}$$. Let $$\sigma_2 \geq \sigma_3 \geq \cdots \sigma_r$$ denote the positive main-diagonal entries of $$\hat{\Sigma}$$. Show that $$\sigma_1 \geq \sigma_2$$. Embed the SVD $$\hat{A} = \hat{U} \hat{\Sigma} \hat{V}^{T}$$ in larger matrices to obtain an SVD of $$A$$. Then use the equation $$A = \tilde{U} \tilde{A} \tilde{V}^{T}$$ to obtain an SVD of $$A$$.

Question:

I know the exercise is well done (it's a step by step that I should probably complete the demonstration easily). But I could not do it and it also did not help me what I read in the book of Strang and Golub that I took to help me solve this exercise. So, I'd like to understand the solutions this Theorem/Exercise.

• I think it may be better if you split this question up for each subpart but someone more experienced than me may disagree
– user3417
May 29, 2019 at 20:33
• @Shogun sorry, but I can't understand your comment. Did you mean that there are many items and consequently many doubts? Unfortunately, I asked the whole question because here you can help me. And only with a book I couldn't understand. I am very difficult in this discipline (Watkins, Golub, Trefethen, ...). May 30, 2019 at 4:20
• I'm saying each part on it's own might make a good question however in retrospect they all kind of require each other. I'd note that I believe that this is actually answered in Trefethan and Bau in the section about the SVD to a degree.
– user3417
May 30, 2019 at 4:24
• I may answer this later today however I'm busy at the moment.
– user3417
May 30, 2019 at 18:52
• I'll attempt to clean that up but that is c-e
– user3417
May 31, 2019 at 19:21

Ok, suppose that $$A = U \Sigma V^{T}$$ . First of all consider how the SVD is calculated. The construction of the SVD uses the following idea

We get the left singular vectors $$U$$ by computing the covariance matrix

$$AA^{T} = U \Sigma V^{T}( U \Sigma V^{T})^{T} = U \Sigma V^{T} (V \Sigma^{T} U^{T})$$

now note that $$V^{T}V = I$$ so we have

$$U \Sigma V^{T} (V \Sigma^{T} U^{T}) = U \Sigma \Sigma^{T} U^{T}$$

note that $$\Sigma$$ is a diagonal matrix and $$\sigma_{jj}^{T} = \sigma_{jj}$$ so

$$U \Sigma \Sigma^{T} U^{T} = U \Sigma \Sigma U^{T}$$

now the singular values $$\sigma_{i}^{2} = \lambda_{i}$$ so you can write

$$U \Lambda^{\frac{1}{2}} \Lambda^{\frac{1}{2}} U^{T} = U \Lambda U^{T}$$

Similarly, the right singular vectors $$V$$ are given as

$$A^{T}A = (U \Sigma V^{T})^T (U \Sigma V^{T}) = V \Lambda V^{T}$$

Note that you can write this like

$$V^{T} A^{T}A V = \begin{pmatrix} v_{1}^{T} \\ v_{2}^{T} \\ \vdots \\ v_{m}^{T} \end{pmatrix} \left( A^{T}A v_{1}, A^{T}A v_{2} , \cdots A^{T} A v_{m} \right) = \begin{pmatrix} v_{1}^{T} \\ v_{2}^{T} \\ \vdots \\ v_{m}^{T} \end{pmatrix} \left( \lambda_{1} v_{1}, A^{T}A v_{2} , \cdots A^{T} A v_{m} \right) = \begin{pmatrix} \lambda_{1} & \textrm{z}^{*} \\ 0 & \textrm{B} \end{pmatrix}$$

where by induction we have $$B = \hat{V}{S} \hat{V}^{T}$$

$$V^{T} A^{T}A V = \begin{pmatrix} \lambda_{1} & z^{*} \\ 0 & \hat{V}{S} \hat{V}^{T}\end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & \hat{V} \end{pmatrix} \begin{pmatrix} \lambda & z^{*} \\ 0 & S \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & \hat{V} \end{pmatrix}^{T}$$

We use the same idea for $$\tilde{A} = \tilde{U}^{T} A \tilde{V}$$

$$\tilde{U}^{T} A \tilde{V} = \begin{pmatrix} \tilde{u}_{1}^{T} \\ \tilde{u}_{2}^{T} \\ \vdots \\ \tilde{u}_{m}^{T} \end{pmatrix} \left(A \tilde{v}_{1} , A \tilde{v}_{2} , \cdots A \tilde{v}_{m} \right) \\ = \begin{pmatrix} \tilde{u}_{1}^{T} \\ \tilde{u}_{2}^{T} \\ \vdots \\ \tilde{u}_{m}^{T} \end{pmatrix} \left(\sigma \tilde{v}_{1} , A \tilde{v}_{2} , \cdots A \tilde{v}_{m} \right) = \begin{pmatrix} \sigma_{1} & z^{*} \\ 0 & \hat{A} \end{pmatrix}$$

with $$\hat{A} = \hat{U} \hat{\Sigma} \hat{V}^{T}$$ we have

$$\begin{pmatrix} 1 & 0 \\ 0 & \hat{U} \end{pmatrix} \begin{pmatrix} \sigma_{1} & z^{*} \\ 0 & \hat{A} \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & \hat{V} \end{pmatrix}^{T}$$

The point is to continue along the lower part of the diagonal and prove $$z^{*}$$ is equal to $$0$$.

$$\bigg\| \begin{bmatrix} \sigma_{1} & z^{*} \\ 0 & \hat{A} \end{bmatrix} \begin{bmatrix} \sigma_{1} \\ z \end{bmatrix} \bigg\|_{2} \geq \sigma_{1}^{2} + z^{*} z = \left( \sigma_{1}^{2} + z^{*}z\right)^{\frac{1}{2}} \bigg\| \begin{bmatrix} \sigma_{1} \\ z \end{bmatrix} \bigg\|_{2}$$

Now, note we're working with $$\| \tilde{A}\| = \| \tilde{U}^{T} A \tilde{V} \|$$ and $$\| \tilde{A}\|_{2} \geq \left( \sigma_{1} + z^{*}z \right)^{\frac{1}{2}}$$. Since $$\| \tilde{A}\| = \| \tilde{U}^{T} A \tilde{V} \|$$ we know that $$\|\tilde{A}\| = \|A \| = \sigma_{1}$$ which forces $$z^{*} = 0$$

Once you have done this we then have

$$A = \tilde{U} \tilde{A} \tilde{V}^{T} = \begin{pmatrix} 1 & 0 \\ 0 & \hat{U} \end{pmatrix} \begin{pmatrix} \sigma_{1} & 0 \\ 0 & \hat{A} \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & \hat{V} \end{pmatrix}^{T}$$

Since this gives the form for a general matrix $$A \in \mathbb{R}^{n \times m}$$ and we have that $$\hat{A} \in \mathbb{R}^{ (n -1) \times (m-1)}$$ we know it has a SVD just like that...

I'm pretty sure I've messed up the $$\hat{A}, \tilde{A}$$ somewhere along here..

• I have much to thank you for. Tonight I will read all the details and if you have any doubts I put here. I jumped a little bit this subject and keep going in a book. When I finished my read about pseudoinverse I will return this. Again, Thanks too much! May 31, 2019 at 19:28