Question came up on singular value decomposition topic.
Prove that for all symmetric positive semi-definite matrices $A$, there exists an orthonormal matrix $U$ such that $$D=U^TAU$$ is a diagonal matrix such that all diagonal entries are non-negative.
$$ D = \left[ {\begin{array}{c} u_{1}^T\\ \vdots \\ u_{n}^T\\ \end{array} } \right] A \left[ u_1 \dots u_n \right] $$
$u_i$ is an orthonormal vector of $U$. Expanding I'm getting $D_{i,j} = u_i^TAu_j$. This is non-negative if $i = j$, from the definition we were given for positive semi-definite matrices. I understand that $u_i^Tu_{j\neq i} = 0$, but I'm not sure how to show $u_i^TAu_{j\neq i} = 0$. Also I am not sure if I'm on the right track, since if $u_i^TAu_{j\neq i} = 0$ is true, this proves true for all orthonormal $U$, which is a much stronger statement than there exist an $U$.
Another thought I had was to make the $D$ the $\Sigma$ in some singular value decomposition of $A$, but it doesn't sound right since $A$ is now restricted to $v^TAv\geq0 \; \forall\;v\neq 0$ (the only property of positive semi-definite matrices that was given.)
Edit: After some search, I understand that for orthonormal matrices, $U^T = U^{-1}$. So my second approach yields $UDU^T = A$. The problem set has not made use of this property of orthonormal matrices, so I am not sure if we can use that, plus it sounds like circular logic.
You need to use the fact that the columns of $\ U\ $ are unit eigenvectors of $\ A\ $: $$ Au_i=\lambda_iu_i $$ with $\ \|u_i\|=1\ $ and $\ \lambda_i\in\mathbb{R}\ $. That $\ \lambda_i\ge0\ $ follows from \begin{align} 0&\le u_i^TAu_i\ \ \text{(because $\ A\ $ is non-negative semi-definite)}\\ &=\lambda_iu_i^Tu_i\\ &=\lambda_i\ . \end{align} The columns of $\ AU\ $ are therefore $\ \lambda_1u_1, \lambda_2u_2,\dots,\lambda_nu_n\ $, where $\ \lambda_1,\lambda_2,\dots,\lambda_n\ $ are the eigenvalues of $\ A\ $, and the rows of $\ U^T\ $ are $\ u_1^T,u_2^T,\dots,u_n^T\ $. Therefore the entry in the $\ i^\text{th}\ $ row and $\ j^\text{th}\ $ column of $\ U^TAU\ $ is $$ \lambda_ju_i^Tu_j=\lambda_j\delta_{ij}\ . $$ That is, $\ D\ $ is a diagonal matrix whose non-zero entries are the eigenvalues of $\ A\ $.