Largest eigenvalue of a positive semi-definite matrix is less than or equal to sum of eigenvalues of its diagonal blocks

Question

This question is very similar to this one.

---

Let

$$B = \begin{bmatrix} B_{11} & B_{12} \\ B_{12}' & B_{22} \end{bmatrix}$$

be a positive semidefinite matrix, where block $B_{11}$ is $p \times p$. Then

$$\lambda_1(B) \le \lambda_1(B_{11}) + \lambda_1(B_{22})$$

where $\lambda_1$ is the largest eigenvalue of the matrix in the argument.

How can I show it using extremal representation of the maximum eigenvalue of a symmetric matrix?

$$ \lambda_1(B) = \max_{||x||=1} x'Bx \\ = \max_{||x||=1} [x_1' x_2']\begin{bmatrix} B_{11} & B_{12} \\ B_{12}' & B_{22}\end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \\ = \max_{||x||=1} [x_1' x_2']\begin{bmatrix} B_{11}x_1 + B_{12}x_2 \\ B_{12}'x_1 + B_{22}x_2\end{bmatrix} \\ = \max_{||x||=1} { x_1'B_{11}x_1 + x_1'B_{12}x_2 + x_2'B_{12}'x_1 + x_2'B_{22}x_2 } $$

If $x_1'B_{12}x_2 + x_2'B_{12}'x_1 $ can go to zero then I am done. But this is certainly not the case.

Where am I making a mistake?

Answer 1

Write $x=c_1u_1+c_2u_2$ with unit vectors $u_1$ and $u_2$ that are non-zero only in the first and second block, respectively. Then

$$x'Bx=c'Ac$$

with

$$A=\pmatrix{u_1'Bu_1&u_1'Bu_2\\u_1'Bu_2&u_2'Bu_2}$$

symmetric and positive-(semi)definite. Since $u_1'Bu_1\le\lambda_1(B_{11})$ and $u_2'Bu_2\le\lambda_1(B_{22})$, we have $\operatorname{tr}A\le\lambda_1(B_{11})+\lambda_1(B_{22})$. Since the eigenvalues of $A$ are non-negative, this implies $\lambda_1(A)\le\lambda_1(A)+\lambda_2(A)=\operatorname{tr}A\le\lambda_1(B_{11})+\lambda_1(B_{22})$. Since any unit vector $x$ can be written in the above form with $c$ a unit vector, $x'Bx=c'Ac\le\lambda_1(B_{11})+\lambda_1(B_{22})$ for $x$ a unit vector, so

$$\lambda_1(B)=\max_{\lVert x\rVert=1}x'Bx\le\lambda_1(B_{11})+\lambda_1(B_{22})\;.$$