6
$\begingroup$

The $k^{\rm th}$ largest eigenvalue (arranged in decreasing order) of the sum of two $N \times N$ Hermitian (real symmetric) matrices $\bf{A}$ and $\bf{B}$ can be stated using the Weyl inequalities as

$L_k \leq \lambda_k({\bf A} + {\bf B}) \leq U_k$

with the lower and upper bounds given by

$L_k = {\rm max}\left[\lambda_i({\bf A}) + \lambda_j(\bf B)\right]$ with $i+j=k+N$

$U_k = {\rm min}\left[\lambda_i({\bf A}) + \lambda_j(\bf B)\right]$ with $i+j=k+1$.

The bounds on the largest eigenvalue $\lambda_1$ of the matrix sum ${\bf A}+{\bf B}$ are therefore

$L_1 = {\rm max}\left[\lambda_i({\bf A}) + \lambda_j(\bf B)\right]$ with $i+j=1+N$

$U_1 = {\rm min}\left[\lambda_i({\bf A}) + \lambda_j(\bf B)\right]$ with $i+j=2$.

Finding the upper bound is very simple; $U_1 = \lambda_1({\bf A})+\lambda_1({\bf B})$ since there is only one solution to the index equation $i+j=2$. However, finding the lower bound is much more difficult; the maximum of

$\left[\lambda_1({\bf A})+\lambda_N({\bf B}), \lambda_2({\bf A})+\lambda_{N-1}({\bf B}), \ldots, \lambda_N({\bf A})+\lambda_1({\bf B}) \right]$

must be found.

Are there any simplifications or theorems that can be applied to obtain a simpler expression for the lower bound (without restricting $\bf B$ to be a slight variation or permutation to $\bf A$) ?

$\endgroup$

1 Answer 1

8
$\begingroup$

Weyl's inequalities are not the full story. The characterization of the possible spectra of $A+B$, given the spectra of $A$ and $B$ is the object of A. Horn's conjecture. This is now a theorem, after hard works by Fulton, Klyachko, Knutson, Terry Tao and others. The conjecture consists in linear inequalities (the simplest of these being Weyl's) which are found recursively on the dimension $n$. After Weyl's inequalities, there are Ky Fan or Wielandt's inequalities, etc ...

$\endgroup$
3
  • $\begingroup$ I found this to be a nice introduction to the topic. ams.org/notices/200102/fea-knutson.pdf $\endgroup$ Commented May 25, 2012 at 3:30
  • $\begingroup$ The name is spelled in English as Klyachko. $\endgroup$
    – Misha
    Commented May 27, 2012 at 3:44
  • $\begingroup$ @Misha. I apologize, and edit. $\endgroup$ Commented May 27, 2012 at 14:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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