"Proof of Sum of Eigenvalues Inequality

In summary, the conversation discusses the proof for the inequality \lambda_{\max}(A+B) \leq \lambda_{\max}(A) + \lambda_{\max}(B) using the hint \lambda_{\max}(A)=\max_{\|x\|=1} x^*Ax. It is proven that the inequality holds with equality for certain cases, but not in general. The conversation also provides a simplified proof for the second equation in the post.
  • #1
azizz
38
0

Homework Statement



Proof: [tex] \lambda_{\max}(A+B) \leq \lambda_{\max}(A) + \lambda_{\max}(B) [/tex]

Homework Equations



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

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:

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

But that don't really helps me and I can't think of an other way to tackle this problem...
 
Physics news on Phys.org
  • #2
I think that [tex] \max_{\|x\|=1} x^*(A+B)x \leq x^*(A+B)x[/tex] is a mistake. First of all, it's not right. Just consider 1x1 matrices over [tex]\mathbb{C}[/tex] and then take ||x|| < 1 to see a counter example.

Also, you're going to want to leave everything in the[tex] \max_{\|x\|=1}[/tex] 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 {[tex]{x^*(A+B)x : x \in V[/tex]}. 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
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:
  • #4
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
So if I understand it correctly I can say that

[tex] \lambda_{\max} (A) + \lambda_{\max} (B) \geq \lambda_{\max} (A+B) [/tex]

can be written as

[tex] \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}) [/tex]

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

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

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

Then the trick is to reintroduce the [tex]\max_{||x_{1}||=1}[/tex] but we've engineered the situation to make it easy.
 
  • #7
Ok thanks a lot for your time! It really helped me.
 
  • #8
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 [tex] \max_{||x|| = 1} x^{*}Ax \geq x^{*}Ax, \forall x \ such\ that\ ||x|| = 1[/tex] 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 ;)
 

1. What is the "Proof of Sum of Eigenvalues Inequality"?

The "Proof of Sum of Eigenvalues Inequality" is a mathematical concept that states the sum of eigenvalues of a square matrix is always equal to its trace, which is the sum of the elements on its main diagonal.

2. Why is the "Proof of Sum of Eigenvalues Inequality" important?

This proof is important because it provides a simple and elegant way to calculate the sum of eigenvalues without having to explicitly find each individual eigenvalue. It also has many applications in fields such as physics, engineering, and computer science.

3. How is the "Proof of Sum of Eigenvalues Inequality" derived?

The proof is derived from the definition of eigenvalues and eigenvectors, and using properties of matrix operations and determinants. It involves using the characteristic polynomial of a matrix and its relationship with the trace and determinant.

4. Can the "Proof of Sum of Eigenvalues Inequality" be applied to non-square matrices?

No, this proof only applies to square matrices as the concept of trace and eigenvalues are only defined for square matrices. Non-square matrices do not have eigenvalues and therefore this proof is not applicable.

5. Are there any limitations to the "Proof of Sum of Eigenvalues Inequality"?

Yes, this proof only holds for finite-dimensional matrices and may not apply to infinite-dimensional matrices. It also assumes that the matrix is diagonalizable, meaning it has a full set of linearly independent eigenvectors.

Similar threads

  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
411
  • Calculus and Beyond Homework Help
Replies
24
Views
672
  • Calculus and Beyond Homework Help
Replies
1
Views
465
  • Calculus and Beyond Homework Help
Replies
1
Views
958
  • Calculus and Beyond Homework Help
Replies
12
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
674
  • Calculus and Beyond Homework Help
Replies
2
Views
62
  • Calculus and Beyond Homework Help
Replies
1
Views
518
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
Back
Top