# Homework Help: Sum of eigenvalues

1. Sep 25, 2009

### azizz

1. The problem statement, all variables and given/known data

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

2. Relevant equations

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

3. 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 dont really helps me and I cant think of an other way to tackle this problem...

2. Sep 25, 2009

### 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, S1 and S2, each of which has a maximum, m1 and m2, what can you say about the maximum of the set of sums s1 + s2 with each s coming from the respective S?

3. Sep 27, 2009

### 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?

Last edited: Sep 27, 2009
4. Sep 27, 2009

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

5. Sep 28, 2009

### 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 :)

6. Sep 28, 2009

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

7. Sep 28, 2009

### azizz

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

8. Sep 28, 2009

### 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 ;)