Gleb Koshevoy
Combinatorial solution of Horn's problem

The talk is based on our joint work with V.Danilov (Discrete convexity and
Hermitian matrices, Proceedings of Steklov Institute, volume 241 (2003),
68-89). In the first part of the talk I will explain our combinatorial
solution of Horn's problem on spectrum of the sum $C=A+B$ of Hermitian
matrices $A$ and $B$ with spectra $\alpha$ and $\beta$, respectively.
Namely, we proved that a tuple $(\gamma_1\ge\ldots \ge \gamma_n)$ can be
spectrum of the Hermitian matrix $C=A+B$ if and only if there exists a
discrete concave function on the triangle grid $\Delta_n$ with the boundary
increments $\alpha$, $\beta$ and $\gamma$. The Horn inequalities can be
obtained from this solution by applying Farkas lemma. In the second part of
the talk, I will discuss a refinement of the Horn problem. Namely, our
conjecture states that there exists a bijection between pairs of $n\times n$
Hermitian matrices and discretely concave functions on the grid $\Delta_n$.
This conjecture is proven in several cases, but still open in general.