2
$\begingroup$

Say you're given the following SVD:

$B= \begin{bmatrix} 1 & -2 & -2 \\ -6 & 3 & -6 \\ \end{bmatrix} = \begin{bmatrix} 0 & d \\ 1 & e\\ \end{bmatrix} \begin{bmatrix} 9 & 0 & 0 \\ 0 & f & g \\ \end{bmatrix} \begin{bmatrix} -2/3 & -1/3 & a \\ 1/3 & 2/3 & b \\ -2/3 & 2/3 & c \\ \end{bmatrix}^T $

How does one find the values for $f$ and $g$. I've found the values for $a,b,c,d,e$ simply because they are orthogonal matrices which rotate. So you can find the corresponding perpendicular vectors and use the determinant to find out which, when filled in, make them rotating matrices.

However, I'm having trouble figuring out the values for $f, g$. I suppose $g = 0$ because it's not in the diagonal of $\Sigma$, thus it has to be $0$?

Also I've gotten as tip to use $BB^T$ to calculate the eigenvalues and singular values, however I'm still having trouble understand how to approach this.

$\endgroup$
  • $\begingroup$ It would help if your SVD would be included in the body of the question, which makes the question easier to read. $\endgroup$ – Roland May 26 '17 at 15:18
  • $\begingroup$ @Roland Noted, added the SVD into the question! $\endgroup$ – marcusvbb May 26 '17 at 15:34
1
$\begingroup$

If the r.h.s. of your equation is indeed a SVD, then all values apart from the upper left main diagonal need to be zero, i.e. $g=0$. This leaves us with the task of finding $f$.

There are two approaches:

  1. Use the fact that $9$ and $f$ are the square roots of the Eigenvalues of $BB^T$ (a $2 \times 2$ matrix). So multiply $B$ with its transpose, and calculate the eigenvalues of that matrix.

  2. Since $B=U\Sigma V$ and we know $B$, $U$ (since you know $d,e$) and $V$ (since you know $a,b,c$), we can multiply $U$, $\Sigma$, $V$ with each other and see which value $f$ needs to have in order to yield $B$ as a result of the computation.

$\endgroup$
  • $\begingroup$ Ok, so solving the 2x2 matrix $BB^T$ gives me the EV's: 9 and 81. How do I know which of these is to be used the the $\Sigma$ matrix? As in, how does one know which of these eigenvalues becomes the singular value $f$? $\endgroup$ – marcusvbb May 26 '17 at 15:37
  • $\begingroup$ Ah. Figured it out. As you said the EV's from the $BB^T$ matrix are the singular values in $\Sigma$ but squared. So we know sqrt(81) = 9, which we already have so we take sqrt(9) which is 3, giving us $f = 3$. Thanks! $\endgroup$ – marcusvbb May 27 '17 at 14:51
  • $\begingroup$ @marcusvbb correct. If the eigenvalues of $BB^T$ are 9 and 81, then the non-zero singular values of $B$ are 3 and 9. $\endgroup$ – Roland May 27 '17 at 15:38
1
$\begingroup$

This is a nice problem to probe understanding of the singular value decomposition. My upvote goes to @Roland for his succinct answer. The following elaboration is to help other readers who may need help with other parts.


Problem

Input matrix: $$ \mathbf{A} = \left[ \begin{array}{rrr} 1 & -2 & -2 \\ -6 & 3 & -6 \\ \end{array} \right] \in \mathbb{C}^{2\times 3}_{2} $$

Complete the singular value decomposition $$ \mathbf{A} = \left[ \begin{array}{rrr} 1 & -2 & -2 \\ -6 & 3 & -6 \\ \end{array} \right] = % U \left[ \begin{array}{rrr} 0 & d \\ 1 & d \\ \end{array} \right] % S \left[ \begin{array}{ccc} 9 & 0 & 0 \\ 0 & f & g \\ \end{array} \right] % V \frac{1}{3} \left[ \begin{array}{rrr} -2 & 1 & 3a \\ 1 & -2 & 3b \\ 2 & -2 & 3c \end{array} \right]^{*} % $$

Observations: the matrix has full row rank, and a column rank defect of 1. This is an underdetermined system.


Tools

The Fundamental Theorem of Linear Algebra

A matrix $\mathbf{A} \in \mathbb{C}^{m\times n}_{\rho}$ induces for fundamental subspaces: $$ \begin{align} % \mathbf{C}^{n} &= \color{blue}{\mathcal{R} \left( \mathbf{A}^{*} \right)} \oplus \color{red}{\mathcal{N} \left( \mathbf{A} \right)} \\ % \mathbf{C}^{m} &= \color{blue}{\mathcal{R} \left( \mathbf{A} \right)} \oplus \color{red} {\mathcal{N} \left( \mathbf{A}^{*} \right)} % \end{align} $$

Because the matrix $\mathbf{A}$ has full row rank, we have a trivial null space: $$ \color{red}{\mathcal{N} \left( \mathbf{A} \right)} = \mathbf{0} $$

For this matrix the subspace decomposition takes the form $$ \begin{align} % \mathbf{C}^{3} &= \color{blue}{\mathcal{R} \left( \mathbf{A}^{*} \right)} \oplus \color{red}{\mathcal{N} \left( \mathbf{A} \right)} \\ % \mathbf{C}^{2} &= \color{blue}{\mathcal{R} \left( \mathbf{A} \right)} % \end{align} $$

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} $$


Resolve constants

The constants are listed in alphabetical order. But the fastest way to solve the problem, after a careful first reading, is $(a,b,c)$, then $(f,g)$, then $(d,e)$.

a, b, c

Just from dimensional considerations we know $$ \begin{align} % R A* \color{blue}{\mathcal{R} \left( \mathbf{A}^{*} \right)} &= \text{span} \left\{ \color{blue}{v_{1}}, \color{blue}{v_{2}} \right\} \\ % N A \color{red}{\mathcal{N} \left( \mathbf{A} \right)} &= \text{span} \left\{ \color{red}{v_{3}} \right\} \end{align} $$

The missing vector in the matrix $\mathbf{V}$ is the lone null space vector. The quickest way to find the solution is to use the cross product of the first two column vectors.

$$ \begin{align} % \color{blue}{v_{1}} \times \color{blue}{v_{2}} &= \color{red}{v_{3}} \\ % \frac{1}{3} \left[ \begin{array}{rrr} -2 \\ 1 \\ -2 \end{array} \right] \times \frac{1}{3} \left[ \begin{array}{rrr} -1 \\ 2 \\ -2 \end{array} \right] &= \frac{1}{9} \left[ \begin{array}{rrr} -6 \\ -6 \\ 3 \end{array} \right] % \end{align} $$ To be in a domain matrix, this vector must be normalized.

The constants are $$ \boxed{ (a, b, c) = \frac{1}{3} \left( -2, -2, 1 \right) } $$ The matrix for the row space is $$ \mathbf{V} = \frac{1}{3} \left[ \begin{array}{rrr} \color{blue}{-2} & \color{blue}{1} & \color{red}{-2} \\ \color{blue}{1} & \color{blue}{-2} & \color{red}{-2} \\ \color{blue}{-2} & \color{blue}{-2} & \color{red}{1} \\ \end{array} \right] $$

d e

Options abound for the second range space vector for $$ \mathbf{U} = \color{blue}{\mathbf{U}_{\mathcal{R}}} = \left[ \begin{array}{cc} \color{blue}{u_{1}} & \color{blue}{u_{2}} \end{array} \right] $$

Method 1: Since $\color{blue}{u_{1}}$ and $\color{blue}{u_{2}}$ are orthogonal we can write $$ \color{blue}{u_{2}} = \color{blue}{\left[ \begin{array}{rrr} 1 \\ 0 \end{array} \right]} $$ That is, $$ \boxed{ (d, e) = (1, 0) } $$

Method 2: Resolve the eigensystem for $$ \mathbf{W} = \mathbf{A}\mathbf{A}^{*} = \left[ \begin{array}{cc} 9 & 0 \\ 0 & 81 \\ \end{array} \right] $$

The first part of this task would be to find the eigenvalues. But they are sitting on the diagonal: $$ \lambda \left( \mathbf{W} \right) = \left\{ 9, 81 \right\} $$ The subtlety is to recall that the singular values are ordered: $$ \sigma = \sqrt{\left\{ 81, 9 \right\}} = \left\{ 9, 3 \right\} $$ This means that the eigenvector we seek, $\color{blue}{u_{2}}$, is associated with the smallest eigenvalue $\lambda = 9$.

Method 3: This method also involves an out of alphabetical order solution. Given the SVD, $$ \mathbf{A} = \mathbf{U} \, \Sigma \, \mathbf{V}^{*} \qquad \Rightarrow \qquad \mathbf{U}_{k} = \sigma^{-1}_{k} \mathbf{A} \mathbf{V}_{k}, \ k = 1, \ \rho $$ That is $$ \color{blue}{u_{2}} = \frac{1}{\sigma_{2}} \mathbf{A} \color{blue}{v_{2}} = \frac{1}{3} \left[ \begin{array}{rrr} 1 & -2 & -2 \\ -6 & 3 & -6 \\ \end{array} \right] \frac{1}{3} \left[ \begin{array}{r} 1 \\ -2 \\ -2 \\ \end{array} \right] = \color{blue}{\left[ \begin{array}{rrr} 1 \\ 0 \end{array} \right]} $$

f g

By construction the $\Sigma$ matrix has the form $$ \left[ \begin{array}{ccc} 9 & 0 & 0 \\ 0 & \sigma_{2} & 0 \\ \end{array} \right] $$ Immediately, $$ \boxed{g=0} $$ If you are solving for the constants out of alphabetical order as suggested earlier, then you would look for the second singular value by finding the eigenvalues of the product matrix $$ \mathbf{W} = \mathbf{A}\mathbf{A}^{*} = \left[ \begin{array}{cc} 9 & 0 \\ 0 & 81 \\ \end{array} \right] $$

The eigenvalues are the diagonal elements: $$ \lambda \left( \mathbf{W} \right) = \left\{ 9, 81 \right\} $$ Remember the singular values are ordered: $$ \sigma = \sqrt{\left\{ 81, 9 \right\}} = \left\{ 9, 3 \right\} $$ Therefore $$ \boxed{f=3} $$

$\endgroup$
  • $\begingroup$ In your "method 1 fpr $d,e$" paragraph, there's a blue $u_{12}$, is this supposed to be $u_2$? $\endgroup$ – Roland May 28 '17 at 9:01
  • $\begingroup$ @Roland: thank's for the careful proofread and your precise answer to the question. $\endgroup$ – dantopa May 28 '17 at 16:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.