# Upper bound of the largest eigenvalue of a PSD block matrix in terms of blocks

Let $\mathbf A=\left[\begin{matrix}\mathbf A_{11}&\mathbf A_{12}\\ \mathbf A_{21}&\mathbf A_{22}\end{matrix}\right]$ be a positive semi-definite matrix, $\mathbf A_{ij}\in\mathbb C^{n\times n}$ and $rank(\mathbf A)=n$.

Prove or disprove that $$\lambda_{max}(\mathbf A) + \lambda_{max}(\mathbf A_{11}+\mathbf A_{22}) \leq \lambda_{max}\left(\left[\begin{matrix}tr(\mathbf A_{11})&tr(\mathbf A_{12})\\ tr(\mathbf A_{21})&tr(\mathbf A_{22})\end{matrix}\right]\right) + tr(\mathbf A_{11}+\mathbf A_{22}),$$ where $\lambda_{max}$ denotes the largest eigenvalue and $tr$ denotes the trace.

I tried small values of $n$. For $n=1$ we have "$=$" (the same terms in the LHS and RHS). I have a rather long proof for $n=2$ (in my proof I also replaced $\mathbb C$ by $\mathbb R$).

It seems that some results on (completely) positive maps are somehow related to the inequality ( indeed, all the maps $$\mathbf A\rightarrow \mathbf A_{11}+\mathbf A_{22},\qquad \mathbf A\rightarrow \left[\begin{matrix}tr(\mathbf A_{11})&tr(\mathbf A_{12})\\ tr(\mathbf A_{21})&tr(\mathbf A_{22})\end{matrix}\right],\qquad \mathbf A\rightarrow tr(\mathbf A_{11}+\mathbf A_{22})$$ are positive). By Theorem 2.3.7 (The Russo-Dye Theorem) from the book R. Bhatia, Positive definite matrices, $$\lambda_{max}\left(\left[\begin{matrix}tr(\mathbf A_{11})&tr(\mathbf A_{12})\\ tr(\mathbf A_{21})&tr(\mathbf A_{22})\end{matrix}\right]\right)\leq n\lambda_{max}(\mathbf A),$$ which is useless since we need inequality of the type $\lambda_{max}(\mathbf A)\leq\dots$

• If the off diagonal blocks are also postive definite then the claims holds "easily". Have to still think about the general case. Sep 5, 2016 at 21:40
• @Suvrit In my application the off diagonal blocks are not positive definite (even not symmetric/hermitian). It would be nice to see your "easy" solution for this particular case because I guess that a more general inequality holds (I will update the question soon) probably your "easy" can be valid for it. Sep 6, 2016 at 9:48
• The "easy" solution was based on proving a stronger inequality that holds when everything is PSD, and by noting that $\|A\| \le \left\Vert \begin{bmatrix}\|A_{11}\| & \|A_{12}\|\\ \|A_{21}\| & \|A_{22}\|\end{bmatrix}\right\Vert$. Since in the meanwhile you already have an answer to the original question, this special case has been obviated. Sep 6, 2016 at 18:28

Write $A=\sum w_i\otimes w_i$ where $w_i$ are orthogonal and $\|w_1\|=\max_i\|w_i\|$. Also write $w_i=(u_i,v_i)$. Then the inequality in question is just $$\|u_1\|^2+\|v_1\|^2+\max_{e:\|e\|=1}\sum_i[|(u_i,e)|^2+|(v_i,e)|^2] \\ \le \left\|\begin{pmatrix}\sum_i\|u_i\|^2&\sum_i(u_i,v_i)\\\sum_i(v_i,u_i)&\sum_i\|v_i\|^2\end{pmatrix}\right\|+\sum_i(\|u_i\|^2+\|v_i\|^2)$$ Now, cancel the first term with the corresponding term on the RHS and estimate $\sum_{i\ge 2}[|(u_i,e)|^2+|(v_i,e)|^2]$ by $\sum_{i\ge 2}(\|u_i\|^2+\|v_i\|^2)$. Also, note that the norm of the sum of several positive definite matrices is not less than the norm of each of them, so we can remove all $i\ge 2$ in the matrix and reduce the problem to showing that $$|(u_1,e)|^2+|(v_1,e)|^2\le \left\|\begin{pmatrix}\|u_1\|^2&(u_1,v_1)\\(v_1,u_1)&\|v_1\|^2\end{pmatrix}\right\|$$ However, we can write the matrix on the right as the sum of positive definite matrices of the kind $\begin{pmatrix}|(u_1,e_j)|^2& (u_1,e_j)(e_j,v_1)\\(v_1,e_j)(e_j,u_1)&|(v_1,e_j)|^2\end{pmatrix}$ where $e_j$ is an orthonormal basis with $e_1=e$. Again, we can remove all matrices with $j\ge 2$, after which we get an identity.
• Thank you for your nice solution. If am not mistaken, you derivation also implies that if "=" holds, then $A_{11}$ is a rank-$1$ matrix. I think the last inequality is just $|(u_1,e)|^2 + |(v_1,e)|^2\leq \|u_1\|^2+\|v_1\|^2=\|\text{matrix}\|$ (since the matrix is rank-1, its norm equals to trace). I will also try to extend your proof for $k\times k$ block matrices. Sep 6, 2016 at 9:57
• @Ignat Not quite. It becomes rank 1 only when you replace norms by scalar products with $e$. Before the very last step it is not necessarily rank $1$ because Cauchy inequality is strict more often than not. Sep 6, 2016 at 12:25