"Proof of Sum of Eigenvalues Inequality

[azizz]

Homework Statement

Proof: \lambda_{\max}(A+B) \leq \lambda_{\max}(A) + \lambda_{\max}(B)

Homework Equations

Hint from exercise: \lambda_{\max}(A)=\max_{\|x\|=1} x^*Ax

The Attempt at a Solution

The problem is that the equation on the left side can not be split. So I tried to write it as follows:

\max_{\|x\|=1} x^*(A+B)x \leq x^*(A+B)x = x^*Bx + x^*Ax

But that don't really helps me and I can't think of an other way to tackle this problem...

 

[aPhilosopher]

I think that \max_{\|x\|=1} x^*(A+B)x \leq x^*(A+B)x is a mistake. First of all, it's not right. Just consider 1x1 matrices over \mathbb{C} and then take ||x|| < 1 to see a counter example.

Also, you're going to want to leave everything in the\max_{\|x\|=1} because that's how you want it to end up and it can be hard to put it back.

The trick is to realize that max is operating on the set of numbers {{x^*(A+B)x : x \in V}. If you have two sets of numbers, S₁ and S₂, each of which has a maximum, m₁ and m₂, what can you say about the maximum of the set of sums s₁ + s₂ with each s coming from the respective S?

 

[azizz]

But if you state it this way, then it seems to me that the inequality holds with equality...

For example, if

S1 = {1,2}
S2 = {2,3}

then the set of sums S12 = s1+s2 is equal to

S12 = {3,4,5}

So if we consider max(S12) and max(S1)+max(S2), then aren't those equal to each other?

 

[aPhilosopher]

For the case of sets where you are allowed to add any two elements, yes you do have equality. This provides an upper bound. There are constraints in this situation that prevent that from being true for two arbitrary matrices.

What if x*Ax is maximum on a vector that is not that same as where x*Bx takes its maximum? Because x*Ax + x*Bx refers to the same x for both A and B, we cannot guarantee that the inequality as it relates to sets in general will become an equality. Does that make sense?

It's like finding the maximum of the ordered sets {1 2 3 4 5} and {5 4 3 2 1} where we have to add them in order.

 

[azizz]

So if I understand it correctly I can say that

\lambda_{\max} (A) + \lambda_{\max} (B) \geq \lambda_{\max} (A+B)

can be written as

\max_{||x_{1}||=1} x_{1}^*Ax_{1} + \max_{||x_{2}||=1} x_{2}^*Ax_{2} \geq \max_{||x_{3}||=1} (x_{3}^*Ax_{3} + x_{3}^*Bx_{3})

The terms on the left hand side are able to define the maximum value in the set, but this is not necessary the case for the right hand side since A might take its maximum on vector x3, but perhaps B does not. Thus that means that the first inequality holds.

Is that correct? It sounds, to me at least, quite logical :)

 

[aPhilosopher]

That's valid. You shouldn't have to put subscripts on the x's like that though: on the LHS, it's implicit that they're possibly different and there is only one on the LHS.

Your teacher might want you to prove the second equation in your last post. Start if off by letting

x_{A} be such that x_{A}^{*}Ax_{A} = \max_{||x_{1}||=1} x^{*}Ax and similarly for x_{B}.

Then x_{A}^{*}Ax_{A} + x_{B}^{*}Ax_{B} \geq x^{*}Ax + x^{*}Bx, \forall x, ||x|| = 1 (by adding two obvious inequalities)

Then the trick is to reintroduce the \max_{||x_{1}||=1} but we've engineered the situation to make it easy.

 

[azizz]

Ok thanks a lot for your time! It really helped me.

 

[aPhilosopher]

I'm sorry, while I was at work I realized that I made that last proof more complicated than we need it to be. I should sleep more.

We have the inequalities \max_{||x|| = 1} x^{*}Ax \geq x^{*}Ax, \forall x \ such\ that\ ||x|| = 1 by definition and similarly for B.

Then just add these two inequalities and apply the definition of max to finish the proof.

I should sleep more ;)