63
$\begingroup$

Is there a relationship between the eigenvalues of individual matrices and the eigenvalues of their sum? What about the special case when the matrices are Hermitian and positive definite?

I am investigating this with regard to finding the normalized graph cut under general convex constraints. Any pointers will be very helpful.

$\endgroup$
64
$\begingroup$

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 Notices AMS article by those two authors

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.

| cite | improve this answer | |
$\endgroup$
43
$\begingroup$

A simple estimate which is often useful is that, if $A$ and $B$ are Hermitian matrices with eigenvalues $a_1 > a_2 > \ldots > a_n$ and $b_1 > b_2 > \ldots > b_n$ and the eigenvalues of the sum are $c_1 > c_2 > \ldots > c_n$, then $$ c_{i+j-1} \le a_i + b_j \quad\text{and}\quad c_{n-i-j} \ge a_{n-i} + b_{n-j}. $$ 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.

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, \ldots, a_n, b_1, \ldots, b_n, c_1, \ldots, 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$.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Can you give a reference to your two inequalities ? $\endgroup$ – Sandeep Silwal Jan 7 '18 at 3:28
  • $\begingroup$ @SandeepSilwal: the two inequalities are given in equations (2) and (11) in a survey by Fulton arxiv.org/abs/math/9908012 $\endgroup$ – Wicher Mar 31 at 16:53
  • $\begingroup$ @Wicher I appreciate the reference but now I don't remember what I needed them for ... $\endgroup$ – Sandeep Silwal Apr 1 at 2:46
  • $\begingroup$ No worries, it seems to be a popular question so I think others may be interested in the reference. $\endgroup$ – Wicher Apr 1 at 13:57
14
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Can you give a reference? $\endgroup$ – David Spivak Apr 16 '16 at 1:58
  • $\begingroup$ @DavidSpivak: Commuting normal matrices are simultaneously diagonalizable. This is a version of the "spectral theorem." The link below is to lecture notes that look like a good reference, but if not, or that link dies, googling some of the terms spectral theorem commuting normal matrices should help. math.drexel.edu/~foucart/TeachingFiles/F12/M504Lect2.pdf $\endgroup$ – Jonas Meyer Jun 24 '16 at 20:17
  • 1
    $\begingroup$ No need for positivity or normality of any kind, actually. The following is true in general: If $a,b$ are elements of a unital abelian Banach algebra, then $spec(a+b)\subseteq spec(a)+spec(b)$ (Murphy - C*-Algebras and Operator Theory, exercise 1.5(a)). If $A,B$ commute, apply this to the matrix algebra generated by $A,B,I$ and all $(A-\lambda)^{-1}$ and $(B-\lambda)^{-1}$ for $\lambda\not\in spec(A)$ or $\lambda\not\in spec(B)$, respectively. $\endgroup$ – Luiz Cordeiro Aug 13 at 0:43
5
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Here is a trivial case with a simple solution. Applicable in Quantum Mechanics, for one.

Given two matrices of the form $A \otimes Id$, $Id \otimes B$, the eigenvalues of their sum are all combinations $a_i+b_j$, where $A\vec{a}_i=a_i\vec{a}_i$ and $B\vec{b}_i=b_i\vec{b}_i$. The eigenvectors are all tensor products of the individual eigenvectors of $A$ and $B$.

This is a one-liner to show:

$$(A \otimes Id + Id \otimes B) \,\vec{a}_i\otimes \vec{b}_j=(a_i+b_j)\,\vec{a}_i\otimes \vec{b}_j$$

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Ideally I would like to generalize this to a wider (but also degenerate) set of matrices, but so far this is the only conjectural working example that I can give for the moment:

Let the $N$ by $N$ lower triangular matrix $L$ be defined by the tetration:

$$\text{If } \text{ mod}(n,tk)=0 \text{ then } L(n,k)= \underbrace{e^{e^{\cdot^{\cdot^{e^{1}}}}}}_m \text{ else } L(n,k)=0$$ where:
$$n=1..N$$ $$k=1..N$$.

and let the $N$ by $N$ upper triangular matrix $U$ be defined as:

$$\text{If } \text{ mod}(k,tn)=0 \text{ then } U(n,k)= \mu(n) \text{ else } U(n,k)=0$$ where:
$$n=1..N$$ $$k=1..N$$.

and let the square $N$ by $N$ matrix $A=L.U$ when $t=1$,
and let the square $N$ by $N$ matrix $B=L.U$ when $t=2$,
and let the square $N$ by $N$ matrix $C=A+B$.

Denote the eigenvalues of $A$ with $\lambda_A(n)$ and
denote the eigenvalues of $B$ with $\lambda_B(n)$ and
denote the eigenvalues of $C$ with $\lambda_C(n)$.

It then appears that for $m$ pieces of natural logarithms of the eigenvalues $\lambda_A(n),\lambda_B(n)$ and $\lambda_C(n)$, the following holds:

$$\text{sgn}(\lambda_A(n))\underbrace{\log(\log(...\log(}_m |\lambda_A(n)|)...))+\text{sgn}(\lambda_B(n))\underbrace{\log(\log(...\log(}_m |\lambda_B(n)|)...))=\text{sgn}(\lambda_C(n))\underbrace{\log(\log(...\log(}_m |\lambda_C(n)|)...))$$ as $m \rightarrow \infty$.

Associated Mathematica program to demonstrate the conjecture:

(*start*)
(*Mathematica 8.0.1*)
Clear[C1, C2, A, B, s, nn, i];
mm = 32;

"Counts to 32"
t = 1;
Monitor[Table[
  A = Table[
     Table[If[Mod[n, t*k] == 0, Exp[Exp[Exp[1]]], 0], {k, 1, nn}], {n,
       1, nn}].Table[
     Table[If[Mod[k, t*n] == 0, MoebiusMu[n], 0], {k, 1, nn}], {n, 1, 
      nn}];
  a = Eigenvalues[A];
  N[Sum[Sign[a[[i]]] If[a[[i]] == 0, 0, 
      Log[Log[Log[Abs[a[[i]]]]]]], {i, 1, nn}], 6], {nn, 1, mm}], nn]
sumA = Round[%]

"Counts to 32"
t = 2;
Monitor[Table[
  B = Table[
     Table[If[Mod[n, t*k] == 0, Exp[Exp[Exp[1]]], 0], {k, 1, nn}], {n,
       1, nn}].Table[
     Table[If[Mod[k, t*n] == 0, MoebiusMu[n], 0], {k, 1, nn}], {n, 1, 
      nn}];
  b = Eigenvalues[B];
  N[Sum[Sign[b[[i]]] If[b[[i]] == 0, 0, 
      Log[Log[Log[Abs[b[[i]]]]]]], {i, 1, nn}], 6], {nn, 1, mm}], nn]
sumB = Round[%]

"Counts to 32"
C1 = A + B;
Monitor[Table[C2 = Table[Table[C1[[n, k]], {k, 1, nn}], {n, 1, nn}];
  c = Eigenvalues[C2];
  N[Sum[Sign[c[[i]]] If[c[[i]] == 0, 0, 
      Log[Log[Log[Abs[c[[i]]]]]]], {i, 1, nn}], 6], {nn, 1, mm}], nn]
sumC1 = Round[%]

sumA + sumB
Sum[Table[
  Sum[If[Mod[n, k] == 0, MoebiusMu[n/k], 0], {n, 1, nn}], {nn, 1, 
   mm}], {k, 1, t}]
%%% - %%
%%% - %%

t = 1;
muA = Table[
  Sum[If[Mod[n, t] == 0, MoebiusMu[n/t], 0], {n, 1, nn}], {nn, 1, mm}]
t = 2;
muB = Table[
  Sum[If[Mod[n, t] == 0, MoebiusMu[n/t], 0], {n, 1, nn}], {nn, 1, mm}]
muC = muA + muB
(*end*)
| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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