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:

<A^TAv_i, v_i>=<Av_i, Av_i>= \lambda _i<v_i, v_i>

Because <x, x> 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.

Advertisements
This entry was posted in Math. Bookmark the permalink.

One Response to SVD – a simple proof

  1. Pingback: More on parity matrices « cartesian product

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s