# How we can proof SVD : $M = U\sigma V^T = \sum_{i=1}^r \sigma_i u_i v_i^T$

How we can prove in SVD this equation: $$M = U\sigma V^T = \sum_{i=1}^r \sigma_i u_i v_i^T = \sigma_1 u_1 v_1^T + \sigma_2 u_2 v_2^T + \cdots + \sigma_r u_r v_r^T$$?

I don't see it...

I know that: The SVD $$M = U\sigma V^T$$: $$U$$ - $$m \times r$$ matrix whose columns are the left singular vectors of $$M$$, $$V$$ - $$n \times r$$ matrix whose columns are the right singular vectors of $$M$$, and $$\sigma$$ - $$r \times r$$ diagonal matrix whose diagonal entries are the singular values of $$M$$.

1. Convince yourself this is true for $$\sigma = I$$ (the identity matrix); in fact, for any two matrices $$U,V$$ with the same number of columns, $$U V^T$$ may be written as the sum $$\sum_i u_i v_i^T$$. This is just another way of rewriting the usual matrix product, and the trick is explained e.g. in this link - see "#3 Columns and rows". I'll try to sketch out how this works: a general entry of $$U V^T$$ is $$\left[ U V^T \right]_{ij} = \sum_k u_{ik} v_{jk}$$, so it is computed by taking the (real) inner product of the $$i$$th row of $$U$$ with the $$j$$th row of $$V$$. However, this shows we can write: $$U V^T = \sum_k A^{(k)}$$ where $$A^{(k)}$$ is a matrix the same size as $$U V^T$$, with entries $$\left[ A^{(k)} \right]_{ij} = u_{ik} v_{jk}$$. Thus, $$A^{(k)}$$ is a rank-one matrix, which we can write as: $$A^{(k)} = \vec{u}_k \vec{v}_k^T$$ where $$\vec{u}_k$$ is the column vector comprised of the $$k$$th column of $$U$$, and $$\vec{v}_k$$ is defined analogously. So all we really did here was just changing the order of arithmetic operations when computing $$U V^T$$: rather than computing each entry using an inner product (which consists of both addition and multiplication), we compute each $$A^{(k)}$$ using only multiplication and then we add them all up.
1. It is not hard to see that when multiplying any matrix $$A$$ from the right by a diagonal matrix $$D$$, the $$i$$th column of $$A$$ simply gets multiplied by the $$i$$th diagonal entry of $$D$$.
Use the second step to compute $$U \sigma$$, and then use the first one to compute $$U \sigma V^T$$.