positive semi-definiteness of the difference of positive semi-definite matrices Let $h, \tilde{h} \in \mathcal{H}$ be two discrete random variables that take values from the finite space $\mathcal{H}$. Also let $N = |\mathcal{H}|$ be the cardinality of $\mathcal{H}$.
 Let $p(h_j)$ denote the probability of $h_j$ and $p(h_j|{\tilde{h}}_i)$ be the probability of $h_j$ given $\tilde{h}_i$.
I want to show (or find a counter example) that the matrix $\boldsymbol{S}_i$, defined as:
\begin{equation}
\boldsymbol{S}_i = \boldsymbol{D}_i - \boldsymbol{u}_i \boldsymbol{u}^T_i
\end{equation}
is positive semi-definite $\forall i$, where
$\boldsymbol{D}_i = \text{diag}\left(\frac{p(h_1)}{p(\tilde{h}_i|h_1)}, \frac{p(h_2)}{p(\tilde{h}_i|h_2)}, \dots, \frac{p(h_N)}{p(\tilde{h}_i|h_N)}\right)$,
and $\boldsymbol{u}_i = \frac{1}{\sqrt{p(\tilde{h}_i)}}\left[p(h_1), p(h_2), \dots, p(h_N) \right]^T$
I tried to prove that $\boldsymbol{x}^T \boldsymbol{S}_i \boldsymbol{x} \geq 0$ $\forall \boldsymbol{x} \in \mathbb{R}^N$, which resulted in the following inequality
\begin{equation}
\sum_{j = 1}^N x_j^2 \frac{p^2(h_j)}{p(h_j|\tilde{h}_i)} \geq \left( \sum_{j = 1}^N x_j p(h_j)\right)^2
\end{equation}
but I still couldn't show that this inequality holds. I tried several numerical examples and it seems to hold but I'm struggling to come up with a proof.
 A: For completeness, I will derive the above inequality.
\begin{align}
\boldsymbol{x}^T \boldsymbol{S}_i \boldsymbol{x} &= \boldsymbol{x}^T \left( \boldsymbol{D}_i - \boldsymbol{u}\boldsymbol{u}^T \right) \boldsymbol{x}\\
&= \boldsymbol{x}^T \boldsymbol{D}_i \boldsymbol{x} - \boldsymbol{x}^T \boldsymbol{u}\boldsymbol{u}^T  \boldsymbol{x}\\
&= \boldsymbol{x}^T \boldsymbol{D}_i \boldsymbol{x} - (\boldsymbol{x}^T \boldsymbol{u})^2\\
&= \sum_{j=1}^N x_j^2 \frac{p(h_j)}{p(\tilde{h}_i|h_j)} - \left(\sum_{j=1}^N x_j \frac{p(h_j)}{\sqrt{p(\tilde{h}_i)}}\right)^2\\
&= \sum_{j=1}^N x_j^2 \frac{p(h_j)}{\frac{p(h_j|\tilde{h}_i)p(\tilde{h}_i)}{p(h_j)}} - 
\frac{1}{p(\tilde{h_i})} \left(\sum_{j=1}^N x_j p(h_j)\right)^2\\
&= \frac{1}{p(\tilde{h_i})}  \sum_{j=1}^N x_j^2 \frac{p^2(h_j)}{p(h_j|\tilde{h}_i)} - 
\frac{1}{p(\tilde{h_i})} \left(\sum_{j=1}^N x_j p(h_j)\right)^2.
\end{align}
Thus, $\boldsymbol{x}^T \boldsymbol{S}_i \boldsymbol{x} \geq 0$ is equivalent to
\begin{align}
\frac{1}{p(\tilde{h_i})}  \sum_{j=1}^N x_j^2 \frac{p^2(h_j)}{p(h_j|\tilde{h}_i)} - 
\frac{1}{p(\tilde{h_i})} \left(\sum_{j=1}^N x_j p(h_j)\right)^2 &\geq 0 \\
\Longleftrightarrow \sum_{j=1}^N x_j^2 \frac{p^2(h_j)}{p(h_j|\tilde{h}_i)} - 
\left(\sum_{j=1}^N x_j p(h_j)\right)^2 &\geq 0 \quad\quad\quad\quad\quad \longrightarrow (1) 
\end{align}
Now set $a_j = \frac{x_j p(h_j)}{\sqrt{p(h_j|\tilde{h}_i)}}$, and set $b_j = \sqrt{p(h_j|\tilde{h}_i)}$. Then, by Cauchy Schwartz inequality, we have that
\begin{equation}
\left( \sum_{j=1}^N a_j^2\right) \cdot \left( \sum_{j=1}^N b_j^2\right) \geq \left( \sum_{j=1}^N a_j \cdot b_j\right)^2
\end{equation}
which gives us
\begin{equation}
\left( \sum_{j=1}^N \left(\frac{x_j p(h_j)}{\sqrt{p(h_j|\tilde{h}_i)}}\right)^2\right) \cdot \left( \sum_{j=1}^N \left( \sqrt{p(h_j|\tilde{h}_i)}\right)^2\right) \geq \left( \sum_{j=1}^N \frac{x_j p(h_j)}{\sqrt{p(h_j|\tilde{h}_i)}} \cdot \sqrt{p(h_j|\tilde{h}_i)} \right)^2
\end{equation}
\begin{equation}
\Longleftrightarrow \left( \sum_{j=1}^N \frac{x_j^2 p^2(h_j)}{p(h_j|\tilde{h}_i)}\right) \cdot \underbrace{\left( \sum_{j=1}^N p(h_j|\tilde{h}_i)\right)}_{ = 1} \geq \left( \sum_{j=1}^N x_j p(h_j) \right)^2
\end{equation}
Hence, (1) follows.
