## SVD – a simple proof

Every $m \times n$ real matrix $A$ can be decomposed as: $A=U \Sigma V^T$ where $U$ is a $m \times m$ orthogonal matrix, $\Sigma$ is a $m \times n$ matrix, having non-zero elements only on the diagonal, and  $V$ is a $n \times n$ orthogonal matrix.

We know from the previous post that a symmetric matrix is digonalisable, and can be diagonalised by a orthogonal matrix. In our case $A^{T}A$ happens to be a $n \times n$ symmetric matrix.

Therefore, $\exists v_i, \lambda _i, i=1..n$, and $A^TAv_i=\lambda _iv_i$. Real symmetric matrices have real eigenvalues and additionally $\lambda _i \geq 0$ because:

$== \lambda _i$

Because $$ is grater or equal to $0$ for some vector $x$, it follows that $\lambda _i=0$ when $Av_i=0$ (i.e. $v_i$ is in the null space of $A$) and $\lambda _i>0$ otherwise.

For $\lambda _i > 0$, multiplying $A^TAv_i=\lambda _iv_i$ by ${v_j}^T$ and considering that $v_i$ and $v_j$ are orthogonal unit vectors, we get:

${v_j}^TA^TAv_i=\lambda _i \delta _{i,j}$  =>

${(Av_j)}^TAv_i=\lambda _i \delta _{i,j}$ =>

${(\frac {Av_j} {\sqrt {\lambda _j}})}^T{(\frac {Av_i} {\sqrt {\lambda _i}})}=\delta _{i,j}$

Denoting $u_i=\frac {Av_i} {\sqrt {\lambda _i}}$ we get: $Av_i=\sqrt {\lambda _i}u_i$ =>

$A[v_1 ... v_r v'_{r+1} ... v'_{n}]=[u_1 ... u_r u'_{r+1} ... u'_{m}]\begin{bmatrix} {\sqrt \lambda_1} & \cdots & 0 & \cdots & 0 \\ \vdots & \ddots & \vdots & & \vdots \\ 0 & \cdots & {\sqrt \lambda_r} & \cdots & 0 \\ \vdots & & \vdots & & \vdots & \\ 0 & \cdots & 0 & \cdots & 0 \end{bmatrix}$

$r$ is the rank of the matrix.

The set of vectors $v_i$ is extended by the set of orthogonal vectors $v'_j$ to form a basis in $R^n$.

The set of vectors $u_i$ is extended by the set of orthogonal vectors $u'_j$ to form a basis in $R^m$.