Proof that left singular vectors in SVD are orthogonal, and proof of low-rank approximation

Question

I've been reading about SVDs and have a couple questions. First, let $A\in \mathbb{R}^{n\times d}$ be a matrix with SVD $U\Sigma V^T$. Let $\sigma_i$ denote the $i$'th singular value, with corresponding right singular vector $v_i$. Is there a simple proof, using elementary linear algebra, for why the left singular vectors, $Av_i$'s, are orthogonal. Secondly, is it true that $A_k=\sum_{i=1}^kAv_iv_i^T$ is always of rank $k$, where $k\le \text{rank}(A)$?

Answer 1

left singular vectors is by definition a unit vector $v_i$ such that : $$ Av_i=s_i w_i \qquad A^tw_i=s_i v_i $$ then : $$ AA^tw_i=s_i A v_i= s_i^2 w_i $$ so $s_i^2$ are the eigenvalues of the hermitian matrix $AA^t$ with corresponding eigenvectors $w_i$ so $w_i$ will be orthonormal, in fact it suffices to show that $w_i$ are orthogonal, let $s_i\neq s_j$ : $$ s_i^2\langle w_i , w_j \rangle =\langle s_i^2 w_i , w_j \rangle = \langle AA^tw_i , w_j \rangle=\langle w_i , AA^tw_j \rangle=\langle w_i ,s_j^2 ww_j \rangle=s_j^2\langle w_i , w_j \rangle $$ so $\langle w_i , w_j\rangle =0$ this implies that $$ \langle Av_i , Av_j\rangle=\langle s_i w_i , s_jw_j\rangle=s_i s_j\langle w_i , w_j\rangle=0 $$ for the second question of rank we will use some simple fact about rank, which you can see them here : $$ rank(Ab)\leq \min(rank(A),rank(B))\\ rank(A+B)\leq rank(A)+rank(B) $$ so we know that the matrix $v_iv_i^t$ is of rank one (because $(v_iv_i^t)x=\langle v_i , x \rangle v_i$ forall $x$) and then for all $i$ the matrix $Av_i v_i^t$ is of rank one (if we assume surly that $A\neq 0$), so $$ rank(A_k)=rank(\sum_{i=1}^k A v_i v_i^t ) \leq \sum_{i=1}^k rank(A v_i v_i^t)=k $$ to verify the equality we can use this question (because the answer of the question remain true for $n\times d$ matrix) and to see that $$ Ran(Av_iv_i^t)=\mathbb{R}(Av_i)\\ Ran((Av_iv_i^t)^t)=Ran(v_iv_i^t A^t )=\mathbb{R} v_i $$ (because $Ran(v_i v_i^t)=\mathbb{R} v_i $)

so for $i\neq j$ : $$ Ran(Av_iv_i^t)\cap Ran(Av_jv_j^t)= \mathbb{R}(Av_i) \cap \mathbb{R}(Av_j)=\{0\} \;\textrm{Orthogonality from the first question }\\ Ran((Av_iv_i^t)^t)\cap Ran((Av_jv_j^t)^t)=\mathbb{R} v_i \cap \mathbb{R} v_j =\{0\} \; \textrm{Orthogonality with the same argument } $$ so $Rank(A_k)=k$.