Eigenvalues of Matrix Sums - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T04:35:42Z http://mathoverflow.net/feeds/question/4224 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/4224/eigenvalues-of-matrix-sums Eigenvalues of Matrix Sums Jean-Pierre Gunman 2009-11-05T07:18:13Z 2010-09-27T15:18:25Z <p>Is there a relationship between the eigenvalues of individual matrices and the eigenvalues of their sum?</p> <p>What about the special case when they are Hermitian and positive-definite?</p> <p>I am investigating this with regard to finding the normalized graph cut under general convex constraints.</p> <p>Any pointers will be very helpful.</p> <p>Thanks. B.</p> http://mathoverflow.net/questions/4224/eigenvalues-of-matrix-sums/4231#4231 Answer by Jonas Meyer for Eigenvalues of Matrix Sums Jonas Meyer 2009-11-05T09:02:20Z 2009-11-05T09:02:20Z <p>If 2 positive matrices commute, than each eigenvalue of the sum is a sum of eigenvalues of the summands. This would be true more generally for commuting normal matrices. For arbitrary positive matrices, the largest eigenvalue of the sum will be less than or equal to the sum of the largest eigenvalues of the summands.</p> http://mathoverflow.net/questions/4224/eigenvalues-of-matrix-sums/4238#4238 Answer by Yemon Choi for Eigenvalues of Matrix Sums Yemon Choi 2009-11-05T09:55:00Z 2009-11-05T09:55:00Z <p>The problem of describing the possible eigenvalues of the sum of two hermitian matrices in terms of the spectra of the summands leads into deep waters. The most complete description was conjectured by Horn, and has now been proved by work of Knutson and Tao (and others?) - for a good discussion, see the <a href="http://www.ams.org/notices/200102/" rel="nofollow">Notices AMS article</a> by those two authors</p> <p>Depending on what you want, there should be simpler results giving estimates on the eigenvalues of the sum. A book like Bhatia's Matrix Analysis might have some helpful material.</p> http://mathoverflow.net/questions/4224/eigenvalues-of-matrix-sums/4255#4255 Answer by David Speyer for Eigenvalues of Matrix Sums David Speyer 2009-11-05T14:09:34Z 2009-11-05T14:09:34Z <p>A simple estimate which is often useful is that, if A and B are Hermitian matrices with eigenvalues a_1 > a_2 > ... > a_n and b_1 > b_2 > ... > b_n and the eigenvalues of the sum are c_1 > c_2 > ... > c_n, then </p> <p>c_{i+j-1} &le; a_i + b_j and c_{n-i-j} &ge; a_{n-i} + b_{n-j}.</p> <p>The above conditions are necessary but not sufficient for A+B=C to have a solution; see the Knutson-Tao article if you want sufficient conditions.</p> <p>If you do not impose that A and B are Hermitian then there are very few restrictions besides the trace being equal. More specifically, the 3n-tuples (a_1, ..., a_n, b_1, ..., b_n, c_1,...,c_n) which occur as eigenvalues of (A,B,C) with A+B=C are dense in the hyperplane \sum a_i + \sum b_i = \sum c_i.</p> http://mathoverflow.net/questions/4224/eigenvalues-of-matrix-sums/4336#4336 Answer by Chris Godsil for Eigenvalues of Matrix Sums Chris Godsil 2009-11-06T04:55:30Z 2009-11-06T04:55:30Z <p>If M is Hermitian then H + aI is positive semidefinite when a is large enough. So the Hermitian + positive semidefinite case is essentially the same as the Hermitian case</p>