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$) ?
Best Answer
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 ...