Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

Thanks for any helpful answers.

share|improve this question
    
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
1  
Seva: you would need to restrict your attention to pairs of positive definite matrices –  Yemon Choi Mar 20 '11 at 9:43

2 Answers 2

The answer to both your questions are yes. Let me start with the first question, which more straightforward.

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$.

share|improve this answer
    
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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.