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

## Problem 3

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

## Problem 3a

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

## Solution 3a

We want to show

${\displaystyle A=U\Sigma V^{T}\!\,}$

which is equivalent to

${\displaystyle AV=U\Sigma \!\,}$

### Decompose Lambda

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

${\displaystyle \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 ${\displaystyle \sigma _{1}\geq \sigma _{2}\geq \ldots \geq \sigma _{n}>0\!\,}$  since otherwise we could just rearrange the columns of ${\displaystyle V\!\,}$ .

### Define U

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

${\displaystyle \Sigma ^{-1}=\left({\begin{array}{ccccccc}{\frac {1}{\sqrt {\sigma _{1}}}}&&&&0&\cdots &0\\&{\frac {1}{\sqrt {\sigma _{2}}}}&&&0&&\\&&\ddots &&\vdots &&\\&&&{\frac {1}{\sqrt {\sigma _{m}}}}&0&\cdots &0\end{array}}\right),}$

### Verify U orthogonal

{\displaystyle {\begin{aligned}UU^{T}&=AV\Sigma ^{-1}\Sigma ^{-T}V^{T}A^{T}\\&=AV\Lambda ^{-1}V^{T}A^{T}\\&=AA^{-1}A^{-T}A^{T}\\&=I\\\\U^{T}U&=\Sigma ^{-T}V^{T}A^{T}AV\Sigma ^{-1}\\&=\Sigma ^{-T}V^{T}V\Lambda V^{T}V\Sigma ^{-1}\\&=I\end{aligned}}\!\,}