If S,Z are positive semidefinite. We now know that $y^TSy=\sum_{i}\sum_{j}S_{ij}y_{i}y_{j}\geq 0 $, same goes for Z. We also know that we can write S as $S=\sum_{i}\lambda_{i}x_{i}x_{i}^{T}$, with $\lambda_{i}$ the eigenvalues and $x_{i}$ eigenvectors of the matrix S. In other words $S_{ij}=\sum_{k}\lambda_{k}x_{ik}x_{jk}$ by construction.

I want to show that $$\sum_{i}\sum_{j}S_{ij}Z_{ij}\geq0$$ Could anyone help me show this??

I would also like to know why the equality of this statement only holds if and only if $S \cdot Z=0$


Let $x_1, \dotsc, x_n$ be an orthonormal basis of eigenvectors for $Z$ with eigenvalues $\lambda_1, \dotsc, \lambda_n \geq 0$. Then

$$ \sum_{i, j}S_{ij}Z_{ij} = \operatorname{Trace}(SZ) = \sum_i\langle SZ x_i, x_i\rangle = \sum_i \lambda_i \langle Sx_i,x_i \rangle \geq 0. $$

In case of equality each term of the summand must be zero. So either $\lambda_i = 0$ and $Zx_i = 0$ or $\langle Sx_i, x_i \rangle = \langle S^{1/2}x_i, S^{1/2}x_i \rangle = 0$ and $Sx_i = 0$. This shows that $SZx_i = 0$ for all indices $i$ and so $SZ = 0$.

  • $\begingroup$ Okay, but how can I do it using $S=\sum_{i}\lambda_{i}x_{i}x_{i}^T$ ? I would prefer to not use the trace as I am not very familiar with it.. $\endgroup$ – Math Girl Nov 11 '12 at 14:53
  • $\begingroup$ The trace is just the sum of the diagonal elements (and also the sum of the eigenvalues). $\endgroup$ – Josephine Moeller Jan 22 '13 at 22:28
  • $\begingroup$ How to say the second equality? from $\operatorname{Trace}(SZ)$ $\endgroup$ – sleeve chen Sep 25 '16 at 21:05
  • 1
    $\begingroup$ @sleevechen In the basis $x_1, \ldots, x_n$ the matrix entry $(SZ)_{ij}$ equals $\langle SZ x_j, x_i \rangle$. $\endgroup$ – WimC Sep 26 '16 at 4:32

Note $S_i=\lambda_i x_i x^\top_i$, and so, $S=\sum S_i$. To show that the dot product between $Z$ and $S$ satisfies $Z\cdot S\geq 0$, it is enough to show that $Z\cdot S_i\geq 0$. For this, it is enough to show that $\lambda_i Z\cdot x_i x^\top_i\geq 0$. Since $S$ is positive semidefinite, $\lambda_i\geq 0$. We only need to prove $Z\cdot x_i x^\top_i\geq 0$, which is simply equivalent to $x_i^\top Z x_i\geq 0$, which is true for any $x$ because Z is positive semidefinite.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.