Why is a matrix $Z = (<u_iu_i^T,u_ju_j^T>)_{i,j\in [n+1]}$ with $\{u_i\}_{i\in[n]}$ orthonormal representation of a graph positive semi-definite?

Question

I am trying to prove that a matrix which is a orthonormal representation of a graph $G$ is PSD. I've defined my matrix as follows $Z_{ij} = <U_{i-1},U_{j-1}>$ for all $i,j\in[n+1]$ where $$\begin{cases}U_0 = I_d\\ U_i = u_iu_i^T \text{ for all } i\in[n] \end{cases}$$

So, I've shown that $$\begin{cases}Z_{0,0} = d\\ Z_{0,i} = 1 = Z_{i,i} \forall i\in[n] \\ Z_{i,j} = 0 \quad \forall \{i,j\}\in E^c \text{ ($E^c$ being the complement of the edges of $G$)}\\ Z_{i,j} \leq 1 \quad \forall \{i,j\}\in E \end{cases}$$

I've tried writing out the product $x^TZx$ for arbitrairy $x\in\mathbb{R}^{n+1}$, but that does not seem to get me anywhere. How do I show $Z$ is PSD?

Answer 1

$Z$ is necessarily PSD because it's a Grammian matrix. For a direct proof, note that $$ \left \langle \sum_{i=0}^n x_iU_i,\sum_{i=0}^n x_iU_i\right \rangle = \sum_{i,j = 1}^n x_ix_j\langle U_i, U_j \rangle, $$ which is exactly what you get if you expand $x^TZx$.