# Numerical Methods Qualification Exam Problems and Solutions (University of Maryland)/January 2009

## Problem 3

 Let $A \in R^{n\times m} \!\,$ with $n \geq m \!\,$. Assume $rank(A) =m \!\,$

## Problem 3a

 It is known that the symmetric matrix $A^TA \!\,$ can be factored as $A^TA=V \Lambda V^T \!\,$ where the columns of $V \!\,$ are orthonormal eigenvectors of $A^TA\!\,$ and $\Lambda \!\,$ is the diagonal matrix containing the corresponding eigenvalues. Using this as a starting point, derive the singular value decomposition of $A \!\,$. That is show that there is a real orthogonal matrix $U \!\,$ and a matrix $\Sigma \in R^{n \times m} \!\,$ which is zero except for its diagonal entries $\sigma_1 \geq \sigma_2 \geq \ldots \geq \sigma_m >0 \!\,$ such that $A=U \Sigma V^T \!\,$

## Solution 3a

We want to show

$A=U \Sigma V^T \!\,$

which is equivalent to

$AV= U \Sigma \!\,$

### Decompose Lambda

Decompose $\Lambda \!\,$ into $\Sigma^T\Sigma \!\,$ i.e.

$\underbrace{ \begin{bmatrix} \sigma_1 & & & \\ & \sigma_2 & & \\ & &\ddots & \\ & & & \sigma_m \end{bmatrix}}_{\Lambda \in R^{m \times m}}= \underbrace{\begin{bmatrix} \sqrt{\sigma_1} & & & &0&\cdots&0\\ & \sqrt{\sigma_2} & & &0&&\\ & &\ddots & &\vdots&&\\ & & & \sqrt{\sigma_m} &0&\cdots&0 \end{bmatrix}}_{\Sigma^T \in R^{m \times n}} \underbrace{ \begin{bmatrix} \sqrt{\sigma_1} & & & \\ & \sqrt{\sigma_2} & & \\ & &\ddots & \\ & & & \sqrt{\sigma_m} \\ 0 & \cdots & & 0 \\ \vdots & \vdots & & \vdots \\ 0 & \cdots & 0 & 0 \end{bmatrix} }_{\Sigma \in R^{n \times m}} \!\,$

We can assume $\sigma_1 \geq \sigma_2 \geq \ldots \geq \sigma_n >0 \!\,$ since otherwise we could just rearrange the columns of $V \!\,$.

### Define U

Let $U=AV\Sigma^{-1} \!\,$ where

$\Sigma^{-1}= \left(\begin{array}{ccccccc} \frac1\sqrt{\sigma_1} & & & &0&\cdots&0\\ & \frac1\sqrt{\sigma_2} & & &0&&\\ & &\ddots & &\vdots&&\\ & & & \frac1\sqrt{\sigma_m} &0&\cdots&0 \end{array}\right) ,$

### Verify U orthogonal

\begin{align} UU^T &= AV\Sigma^{-1}\Sigma^{-T}V^TA^T \\ &= AV\Lambda^{-1}V^TA^T \\ &= AA^{-1}A^{-T}A^T \\ &= I \\ \\ U^TU &= \Sigma^{-T}V^TA^TAV\Sigma^{-1} \\ &= \Sigma^{-T}V^T V \Lambda V^T V \Sigma^{-1} \\ &= I \end{align} \!\,