# Question on eigenvalue square root subadditivity

ORIGINAL QUESTION

Let $\lambda_{1}\left(\cdot\right)$ be the larger eigenvalue of a $2\times2$ matrix and $\lambda_{2}\left(\cdot\right)$ the smaller eigenvalue of a $2\times2$ matrix. Is it true that $$\left|\sqrt{\lambda_{1}\left(A+B\right)}-\sqrt{\lambda_{1}\left(B\right)}\right|+\left|\sqrt{\lambda_{2}\left(A+B\right)}-\sqrt{\lambda_{2}\left(B\right)}\right|\leq\sqrt{\lambda_{1}\left(A\right)}+\sqrt{\lambda_{2}\left(A\right)}$$ for any two $2\times2$ positive-definite symmetric real matrices $A$ and $B$?

EDITED QUESTION (after Mikael de la Salle's original answer)

If $A$ is not positive definite, does one have $$\left|\sqrt{\left|\lambda_{1}\left(A+B\right)\right|}-\sqrt{\left|\lambda_{1}\left(B\right)\right|}\right|+\left|\sqrt{\left|\lambda_{2}\left(A+B\right)\right|}-\sqrt{\left|\lambda_{2}\left(B\right)\right|}\right|\leq\sqrt{\left|\lambda_{1}\left(A\right)\right|}+\sqrt{\left|\lambda_{2}\left(A\right)\right|}$$ for any $2\times2$ symmetric real matrices $A$ and $B$, where $\lambda_{1}\left(\cdot\right)$ is the larger absolute value eigenvalue and $\lambda_{2}\left(\cdot\right)$ is the smaller absolute value eigenvalue?

-
On the right-hand side, do you really mean $\lambda_1$ both times? –  Yemon Choi Mar 20 '11 at 6:52
Presumably you have tried (and solved) the case where $A$ and $B$ commute... –  Yemon Choi Mar 20 '11 at 6:53
It should be $\lambda_2$ for the second term in the right-hand side. –  user13773 Mar 20 '11 at 7:11
I would start with checking, using Maple or Mathematica, all pairs of matrices with integer entries between, say, -$10$ and $10$. If no counterexample is found, this is a string indication that your inequality is, indeed, true. –  Seva Mar 20 '11 at 8:07
Seva: you would need to restrict your attention to pairs of positive definite matrices –  Yemon Choi Mar 20 '11 at 9:43

A first remark: since $A$ is positive-definite, $\lambda_i(A+B) \geq \lambda_i(B)$ for $i=1,2$. (to check this, use the formulas $\lambda_1(X) = \max_{\xi} \langle X\xi,\xi\rangle$ and $\lambda_2(X) = \min_{\xi} \langle X\xi,\xi\rangle$ where the min and max run over all unit vectors $\xi$. This formulas hold whenever $X$ is a symmetric $2 \times 2$ matrix.)

Your question is therefore whether $Tr(\sqrt{A+B})\leq Tr(\sqrt A)+ Tr(\sqrt B)$ for any symmetric positive definite matrices $A$ and $B$, or equivalently $Tr( \sqrt{X X^{T} + Y Y^{T} } ) \leq Tr(\sqrt{X X^{T} })+Tr(\sqrt{Y Y^{T} })$ for any matrices $X$ and $Y$, where $X^{T}$ denotes the transpose of $X$, or hermitian tranpose if you work with complex matrices. This inequality is true in any dimension (not just 2), and it is just the triangle inequality for the Schatten 1-norm given by $\|X\|_1 = Tr(\sqrt{X X^{T} })$. The expression $Tr(\sqrt{X X^{T} + Y Y^{T} })$ is indeed the 1-norm of the matrix $\begin{pmatrix}X&Y \\\\ 0&0\end{pmatrix}$.

EDIT: It seems from the comments that my answer to your second question was far from clear. Let me try to explain differently the proof I had in mind.

For 6 real numbers $\alpha_1 \geq \alpha_2$, $\beta_1\geq \beta_2$ and $\gamma_1 \geq \gamma_2$, denote by $f(\alpha_1,\alpha_2,\beta_1 , \beta_2,\gamma_1,\gamma_2)$ the quantity $\sqrt{|\alpha_1|} + \sqrt{|\alpha_2|} - |\sqrt{\max(|\gamma_1|,|\gamma_2|)} - \sqrt{\max(|\beta_1|,|\beta_2|)}| - |\sqrt{\min(|\gamma_1|,|\gamma_2|)} - \sqrt{\min(|\beta_1|,|\beta_2|)}|$.

You are asking whether $f \geq 0$ provided that $\alpha,\beta,\gamma$ are the ordered eigenvalues of respectively $A,B,A+B$ for symmetric $2 \times 2$ matrices $A$ and $B$. The answer is yes, and I am sketching a proof. Denote by $D$ the possible values for $(\alpha_1,\alpha_2,\beta_1 , \beta_2,\gamma_1,\gamma_2)$.

$D$ is exactly described by Horn's inequalities. These inequalities are $$\alpha_1 \geq \alpha_2 \ \ , \ \ \beta_1\geq \beta_2,$$ $$\gamma_1 + \gamma_2= \alpha_1 + \alpha_2+\beta_1+\beta_2,$$ $$\alpha_2+\beta_2 \leq\gamma_2 \leq \min(\alpha_1+\beta_2,\alpha_2+\beta_1).$$

In particular, $D$ is a convex subset of dimension $5$ of $\mathbb R^6$, and one easily checks that its boundary corresponds to the case when $A$ and $B$ commute. Since the inequality is true when $A$ and $B$ commute (this is eay to check, see the other answer), your question reduces to whether $\inf_D f = \inf_{\partial D} f$. This transforms your eigenvalue question to a purely calculus question.

Notice now that $\beta,\gamma$ and $\alpha_1+\alpha_2$ being fixed, $f(\alpha,\beta,\gamma)$ decreases as $\min(|\alpha_1|,|\alpha_2|)$ decreases. Moreover, if you started with $\alpha,\beta,\gamma$ in the interior of $D$, you stay in $D$ if you make $\min(|\alpha_1|,|\alpha_2|)$ decrease, until you reach the boundary of $D$, or $\min(|\alpha_1|,|\alpha_2|)=0$. You are therefore left to prove that $f(\alpha,\beta,\gamma) \geq \inf_{\partial D} f$ if $(\alpha,\beta,\gamma) \in D$ with $\min(|\alpha_1|,|\alpha_2|)=0$.

In the same way, fixing $\alpha,\beta$ and $\gamma_1+\gamma_2$, you reduce the question to proving that $f(\alpha,\beta,\gamma) \geq \inf_{\partial D} f$ if $(\alpha,\beta,\gamma) \in D$ with $\min(|\alpha_1|,|\alpha_2|)=0$ and $\min(|\gamma_1|,|\gamma_2|)=0$.

Last, fixing $\alpha, \gamma$ and $\beta_1+\beta_2$ with $\min(|\alpha_1|,|\alpha_2|)=0$ and $\min(|\gamma_1|,|\gamma_2|)=0$, you see that $f(\alpha,\beta,\gamma)$ decreases as $\min(|\beta_1|,|\beta_2|)$ increases, until you reach the boundary of $D$. This proves that $\inf_D f = \inf_{\partial D} f$.

-
What do you mean by the matrix $(X\,Y\,0\,0)$? Don't one need $Tr(\sqrt{(X+Y)t(X+Y)})$ in the left-hand side for the triangle inequality? –  user13773 Mar 20 '11 at 16:31
There was a problem with the formatting. What appears as $(X\ Y\ 0\ 0)$ should be the square matrix $Z$ with $X\ Y$ as first row and $(0\ 0)$ as first column. And then $Z t(Z)$ is the matrix with zeros except in the upper-left corner, when there is $X t(X)+ Y t(Y)$. –  Mikael de la Salle Mar 20 '11 at 17:40
What if $A$ is not positive-definite? Thanks. –  user13773 Mar 20 '11 at 21:43
How do you get $\|\begin{pmatrix}X&Y \\\\ 0&0\end{pmatrix}|_1\le\|X\|_1 +\|Y\|_1$? –  user13773 Mar 21 '11 at 17:06
Apply the triangle inequality, and the equalities $\|\begin{pmatrix} X & 0 \\\\ 0 & 0 \end{pmatrix}\|_1=\|X\|_1$ and $\|\begin{pmatrix} 0 & Y \\\\ 0 & 0 \end{pmatrix}\|_1=\|Y\|_1$. –  Mikael de la Salle Mar 21 '11 at 17:21

As mentioned by Choi, the inequality is true when $A$ and $B$ commute (since $A$ and $B$ can be simultaneously diagonalized).

Using Rayleigh quotient we can see that $\left|\sqrt{\lambda_{1}\left(A+B\right)}-\sqrt{\lambda_{1}\left(B\right)}\right|\leq\sqrt{\lambda_{1}\left(A\right)}$ holds. But unfortunately the counterpart is not true for $\lambda_{2}$.

Could you explain how you got the inequality? Hope we will get some clue from Seva's work.

EDIT: Salle's answer is very instructive to me. I would like to sketch here an elementary proof of the inequality $Tr(\sqrt{A+B})\leq Tr(\sqrt A)+ Tr(\sqrt B)$ he gave above.

Noticing that $Tr(\sqrt{A})=\sqrt{Tr(A)+2\sqrt{det(A)}}$ and $det(A+B)\leq det(A)+det(B)+Tr(A)Tr(B)$, for any positive definite $A$ and $B$ in dimension $2$, one applies $\sqrt{a+b}\leq \sqrt{a}+\sqrt{b}$ and then get the inequality.

For your edited question, again I've only checked the case where $A$ and $B$ commute, and the answer is yes. But I failed to decipher the subtlety arises in the general case. Hope we will see a conclusive answer soon.

I guess you are considering B as a fixed vector and A a perturbation, which makes the inequality interesting.

EDIT II: I guess you can change the title into "A generalized Hoffman-Wielandt inequality" and add the tag "Numerical Analysis".

The Hoffman-Wielandt inequality states the following:

Let $A$ and $B$ be real symmetric matrices, $a_i$, $b_i$, $c_i$ the eigenvalues of $A$, $B$, $A+B$ respectively with $a_i\leq a_{i+1}$, etc. Then we have $(\sum_i |c_i-b_i|^2)^{1/2} \leq (\sum_i |a_i|^2)^{1/2}$.

A proof in spirit similar to Mikael's can be found in "The Algebraic Eigenvalue Problem" by Wilkinson. The $L^p$ variant can be found in a paper by Rajendra Bhatia and Ludwig. It seems here your taking the square root inside and $L^1$ norm outside somewhat make things tougher.

-
Xianghong, how do you obtain $det(A+B)\leq det(A)+det(B)$? For instance, it doesn't seem to hold $A=B={{2,0}, {0,1}}$. –  user13773 Mar 21 '11 at 15:52
$A=B=\begin{pmatrix}2&0 \\\\ 0&1\end{pmatrix}$ –  user13773 Mar 21 '11 at 15:53
I am sorry, I made a mistake. I have corrected it. The argument still works. Mikael's interpolation argument is interesting, although it has not been completely verified. –  Syang Chen Mar 22 '11 at 4:25