# Bound on sum of $n$th super-diagonal entries in a $2n$ by $2n$ PSD matrix

Let $A,B,C\in\mathbb{R}^{n\times n}$ be such that $\left(\begin{array}{} A & B \\ B^T & C \end{array}\right)\succeq 0$. I would like to prove that $$\mathrm{trace}\,B \le \sum_{i=1}^n \sqrt{\lambda_i(A)\lambda_i(C)},$$ where for any symmetric $M\in\mathbb{R}^{n \times n}$, $\lambda_1(M) \le \lambda_2(M) \le \cdots \le \lambda_n(M)$ denote the sorted eigenvalues of $M$.

Using SVD, Schur complement and Von-Neumann's trace inequality I am able to show that the above by is true if $$\mathrm{trace}\,\left(\left[\Sigma G^2 \Sigma\right]^{1/2} G^{-1}\right) \ge \mathrm{trace}\,\Sigma$$ for every $G\succ 0$ and diagonal $\Sigma \succeq 0$; according to simulations random matrices seem to satisfy this. This inequality follows from a simple symmetry argument if $f(G) = \mathrm{trace}\,\left(\left[\Sigma G^2 \Sigma\right]^{1/2} G^{-1}\right)$ happens to be operator-convex, but I have so far not been able to prove this.

If $\left(\begin{array}{} A & B \\ B^T & C \end{array}\right)\succeq 0$ then there exists a contraction $K$ (i.e. $\lambda_n(K)=\|K\| \leq 1$) such that $B = A^{1/2} K C^{1/2}$ (e.g. see Theorem IX.5.9 of Bhatia's book: Matrix Analysis). By Von-Neumann's trace inequality, we have $\newcommand{tr}{\mathrm{tr}}$ $$\tr(B) = \tr(A^{1/2} K C^{1/2}) \leq\sum_{i=1}^n \lambda_i(K)\lambda_i(C^{1/2}A^{1/2} ) \leq \sum_{i=1}^n \lambda_i(C^{1/2}A^{1/2} ) .$$

By the weak majorization property of the singular values of the product of matrices (e.g. see Theorem 3 of this paper of Horn), we have

$$\sum_{i=1}^n \lambda_i(C^{1/2}A^{1/2} ) \leq \sum_{i=1}^n \lambda_i(A^{1/2})\lambda_i(C^{1/2}).$$

Now, the result at hand.

Note that here $\lambda_i(\cdot)$ stands for the singular values, which is equal to the eigenvalues for positive semidefinite matrices.

• How do you justify the second inequality ? – Denis Serre May 28 '18 at 13:24
• @DenisSerre: I added more explanation. Right? – Mahdi May 28 '18 at 13:31
• Von Neumann's trace Inequality is in terms of singular values, not eigenvalues. Since $C^{1/2}A^{1/2}$ is not symmetric in general, its singular values do not equal its eigenvalues (they tend to be larger). Your second inequality is therefore false. – Denis Serre May 29 '18 at 6:30
• @DenisSerre: You are right. Let me see if I can fix this. – Mahdi May 29 '18 at 8:26
• @DenisSerre: I think I fixed it. – Mahdi May 29 '18 at 20:35

A slightly more precise result is noted below. You may like it given that you tried Schur complements, and convexity arguments.

Observation. $\DeclareMathOperator{tr}{tr}$ \begin{equation*} \max\{|\tr B| : A \succeq BC^{-1}B^T\} \le \min_{X \succ 0}\sqrt{\tr(AX)\tr(CX^{-1})}. \end{equation*}

From this inequality one sees that the maximum is attained when $B=(AC)^{1/2}$, and equals the value of the min on the right, yielding the value $\tr[(A^{1/2}CA^{1/2})^{1/2}]$.

As a corollary, we also obtain (which is the first set of inequalities in Mahdi's answer): \begin{equation*} |\tr B| \le \tr[(A^{1/2}CA^{1/2})^{1/2}] = \sum_i\lambda_i^{1/2}(A^{1/2}CA^{1/2})= \sum_i\lambda_i^{1/2}(AC), \end{equation*} where $\lambda_i(\cdot)$ denotes eigenvalues.