# If $A,B$ Hermitian and $A-B$ has only nonnegative eigenvalues, show that $\lambda_i(A)\geq\lambda_i(B)$

Denote the sorted eigenvalues of an $n\times n$ matrix $C$ as $\lambda_1(C)\leq\dots\leq\lambda_n(C)$.

I want to show that the following statement holds for all $i=1,\dots,n$

If $A,B$ Hermitian and $A-B$ has only nonnegative eigenvalues, show that $\lambda_i(A)\geq\lambda_i(B)$

Let me state Weyl's Theorem (Thm. 4.3.1 in Horn and Johnson's Matrix Analysis book)

Let $A,B\in\mathbb{C}^{n\times n}$ be Hermitian and let the respective eigenvalues of $A$, $B$, and $A+B$ be $\{\lambda_i(A)\}_{i=1}^n$, $\{\lambda_i(B)\}_{i=1}^n$, and $\{\lambda_i(A+B)\}_{i=1}^n$, each algebraicly ordered as explained above (i.e. $\lambda_1(\dots)\leq\dots\leq\lambda_n(\dots)$). Then $$\lambda_i(A+B)\leq\lambda_{i+j}(A)+\lambda_{n-j}(B),\qquad j=0,\dots,n-i$$ for each $i=1,\dots,n$. Also, $$\lambda_{i-j+1}(A)+\lambda_{j}(B)\leq\lambda_i(A+B),\qquad j=1,\dots,i$$ for each $i=1,\dots,n$.

Let $\lambda_1'(B')\leq\dots\leq\lambda_n'(B')$ denote the sorted eigenvalues of $B'=-B$.

First, since $B$ Hermitian, then $B'$ is also Hermitian and if $(\lambda, \mathbf{x})$ is an eigenpair of $B$, then $(-\lambda, \mathbf{x})$ is an eigenpair of $B'$. Hence, if $\lambda_1(B)\leq\dots\leq\lambda_n(B)$ are the sorted eigenvalues of $B$, then $\lambda_1'(B')=-\lambda_n(B)\leq\dots\leq\lambda_n'(B')=-\lambda_1(B)$ are the sorted eigenvalues of $B'$.

Let's apply the first part of the theorem for matrices $A,B'$ for $j=0$ \begin{eqnarray*} \lambda_i(A+B')\leq\lambda_{i+j}(A)+\lambda_{n-j}'(B')&\Rightarrow&\lambda_{i}(A)+\lambda_{n}'(B')\geq\lambda_i(A+B')\\ &\Rightarrow&\lambda_{i}(A)+\lambda_{n}'(B')\geq0\qquad (A-B\text{ has nonnegative eigenvalues})\\ &\Rightarrow&\lambda_{i}(A)+\lambda_{n}'(-B)\geq0\\ &\Rightarrow&\lambda_{i}(A)-\lambda_{1}(B)\geq0\\ &\Rightarrow&\lambda_{i}(A)\geq\lambda_{1}(B) \end{eqnarray*}

But, this only shows that $\lambda_{1}(A)\geq\lambda_{1}(B)$ and I need $\lambda_{i}(A)\geq\lambda_{i}(B)$ for all values of $i$. What else can I do? I think I need to show that $\lambda_{1}(A)\geq\lambda_{n}(B)$ which would be enough.

• It is straightforward if you use en.wikipedia.org/wiki/Min-max_theorem – Orest Bucicovschi Mar 29 '18 at 8:40
• Generalizing your work, $$\lambda_{i+j}(A)+\lambda_{n-j}'(B)\geq\lambda_i(A+B')\geq 0\implies \lambda_{i+j}(A)-\lambda_{j+1}(B)\geq 0\implies\lambda_{i+j}(A)\geq\lambda_{j+1}(B)$$ Now, let $i=1$ and let $0\leq j\leq n-i=n-1$ to get the desired result. – Prasun Biswas Mar 29 '18 at 9:59

Put $j=i$ in the inequality $$\lambda_{i-j+1}(A)+\lambda_{j}(B)\leq\lambda_i(A+B),\qquad j=1,\dots,i,$$ we get $\lambda_1(X)+\lambda_i(Y)\leq\lambda_i(X+Y)$ for any two Hermitian matrices $X$ and $Y$. Now, put $X=A-B$ and $Y=B$ and we are done.