## The Schubert Calculus and Eigenvalue Inequalities for Sums of Hermitian Matrices

Last updated: 14 October 2014

## Horn's Conjecture and the Hersch–Zwahlen Methods

### Horn's Conjecture

The set ${}^{•}T_{d}^{n}$ introduced by Horn [Hor1962] is defined recursively as follows: $T1n• = { (a,b,c) | 1)a,b,c∈Q1,dn 2)a+b≥=c+1 } , Tdn• = { (a,b,c) | 1) a,b,c∈Qd,n, 2) ∑i=1d (ai+bi) ≥= ∑i=1dci +d·(d+1)2, 3) If (u,v,w) ∈Tdknd• (k Horn conjectured that ${}^{•}T_{d}^{n}<{}^{•}S_{d}^{n}$ for all $d$ and $n\text{;}$ he showed that for all $n,$ ${}^{•}T_{1}^{n}={}^{•}S_{1}^{n},$ ${}^{•}T_{2}^{n}={}^{•}S_{2}^{n},$ and ${}^{•}T_{3}^{n}<{}^{•}S_{3}^{n}\text{;}$ but further, that ${}^{•}S_{4}^{16}\nless {}^{•}T_{4}^{16}\text{.}$ The following lemma was the key tool used.

(The "pushing" lemma for ${}^{•}S_{d}^{n}\text{)}$ Let $\left(a,b,c\right)\in {}^{•}S_{d}^{n},$ and let $u,v,w,$ be three integers such that $1\le u\le d+1,$ $1\le v\le d+1,$ and $1\le w\le d\text{.}$ Set $ai′ = ai+δu-1(i), bi′ = bi+δv-1(i), ci′ = ci+δw-1(i).$ If ${a}_{u}+{b}_{v}\ge {c}_{w-1}+{c}_{d}+2,$ then $\left(a\prime ,b\prime ,c\prime \right)\in {}^{•}S_{d}^{n+1}\text{.}$

Horn proved this lemma using the Cauchy inequalities relating the eigenvalues of a hermitian matrix to those of a principal submatrix. Briefly, one shows that given $\left(a,b,c\right)\in {}^{•}T_{d}^{n},$ there exists $\left(a\prime ,b\prime ,c\prime \right)\in {}^{•}T_{d}^{n-1}$ which can be "pushed" to $\left(a,b,c\right)\text{.}$ This can be done except for one special case in ${}^{•}T_{3}^{n},$ which is treated by a separate argument. For $d=4,$ the number of special cases becomes unmanageable.

### Hersch-Zwahlen Method

The problem addressed by Horn may be reformulated as follows

$Sdn= { (a,b,c) | 1)a,b,c∈Qd,n, 2) Given any three hermitian matrices A,B,C such that A+B+C=0, Σa(A)+ Σb(B)+ Σc(C)≤0 } .$ There is a one-to-one correspondence between ${}^{•}S_{d}^{n}$ and ${S}_{d}^{n}$ given by $\left(\stackrel{‾}{a},\stackrel{‾}{b},c\right)\to \left(a,b,c\right)\text{.}$ That is, $(a‾,b‾,c) ∈Sdn• iff (a,b,c)∈Sdn.$ If the same correspondence is applied to ${}^{•}T_{d}^{n},$ one obtains

$T1n = {(a,b,c) | a+b+c≥=2n+1}, Tdn = { (a,b,c) | 1) a,b,c∈Qd,n, 2) Σ(a,b,c) ≥=2(n+1)d- d(d+1)2, 3) If k It can be shown that $\left(\stackrel{‾}{a},\stackrel{‾}{b},c\right)\in {}^{•}T_{d}^{n}$ iff $\left(a,b,c\right)\in {T}_{d}^{n}\text{.}$ Horn's conjecture is thus equivalent to the conjecture that ${T}_{d}^{n}<{S}_{d}^{n}\text{.}$

In [HZw1962] J. Hersch and B. P. Zwahlen developed a new technique for establishing membership in ${S}_{d}^{n}\text{.}$ We introduce some notation relevant to their method. Let ${A}^{n}\left(F\right)$ denote affine $n\text{-space}$ over a field $F\text{.}$

A $\left(d,n,F\right)\text{-tower}$ is a sequence $\left({A}_{1},{A}_{2},\dots ,{A}_{d}\right)$ of $d$ nested subspaces ${A}_{1}<{A}_{2}<\dots {A}_{d}$ in ${A}^{n}\left(F\right)\text{.}$

A tower is said to be of type $a$ if $a\in {Q}_{d,n}$ and $\text{dim}\left({A}_{i}\right)={a}_{i}$ for $i=1,2,\dots ,d\text{.}$

Let $A$ be a $\left(d,n,F\right)\text{-tower.}$

$Ω(A)= { L | 1) L is a subspace of dimension d in An(F), 2) dim(L∧Ai)≥i for i=1,2,…,d } .$ We call $\mathrm{\Omega }\left(A\right)$ a Schubert variety of type $a\text{.}$

$Vdn(F)= { (a,b,c) | 1) a,b,c By convention, ${V}_{d}^{n}={V}_{d}^{n}\left(ℂ\right),$ where $ℂ$ denotes the field of complex numbers.

(Hersch-Zwahlen) $Vdn

### Thompson's result

Theorem 2.7 shows that Horn's conjecture would be true if ${T}_{d}^{n}<{V}_{d}^{n}\text{.}$ In [Zwa1966], Zwahlen investigated this possibility. He was able to show that ${T}_{1}^{n}={V}_{1}^{n}$ and ${T}_{2}^{n}={V}_{2}^{n}$ for all $n,$ but could not quite verify that ${T}_{3}^{n}<{V}_{3}^{n}\text{.}$ Zwahlen's methods were purely geometrical, and required no special properties of the group field $F\text{.}$

In [TTh1974], R. C. Thompson made clear the problem with Zwahlen's methods. Thompson showed that ${T}_{3}^{n}<{V}_{3}^{n}\left(ℂ\right)$ for all $n,$ but that in general, ${T}_{3}^{n}\nless {V}_{3}^{n}\left({\text{?? maybe}} {ℝ}\right)\text{.}$ His approach started by establishing the following lemma.

(The "pushing" lemma for ${V}_{d}^{n}\text{)}$ Let $\left(a,b,c\right)\in {V}_{d}^{n}\left(F\right),$ where $F$ is an arbitrary field. Let $u,v,w$ be three integers chosen from $\left\{0,1,2,\dots ,d\right\}\text{.}$ Set $ai′ = ai+δu(i), bi′ = bi+δv(i), ci′ = ci+δw(i), a0=b0=c0=0.$ If ${a}_{u}+{b}_{v}+{c}_{w}\le n,$ then $\left(a\prime ,b\prime ,c\prime \right)\in {V}_{d}^{n+1}\left(F\right)\text{.}$

Lemma 2.8 is directly analogous to lemma 2.1, Horn's "pushing" lemma. Using 2.8, Thompson was able to follow Horn's approach and show that all elements of ${T}_{3}^{n}$ can be obtained by pushing from elements of ${T}_{3}^{n-1}$ except for one special case. A difficult analysis of this special case showed that ${T}_{3}^{n}<{V}_{3}^{n}\left(F\right)$ for all $n$ if $F$ is algebraically closed, but not otherwise.

### Identities for ${V}_{d}^{n}$ and ${T}_{d}^{n}$

The main assertion of the present work is that ${T}_{d}^{n}={V}_{d}^{n}\left(ℂ\right)$ for all $n$ if $d\le 4\text{.}$ The proof presented required the machinery of algebraic geometry. This machinery, specifically the Schubert Calculus, is discussed in Section 3. We close Section 2 with some results which first suggested the plausibility of our assertion.

$\left(a,b,c\right)\in {V}_{d}^{n}$ and $\left(u,v,w\right)\in {V}_{k}^{d}⇒\left(a,b,c\right)\circ \left(u,v,w\right)\in {V}_{k}^{n}\text{.}$

$\left(a,b,c\right)\in {T}_{d}^{n}$ and $\left(u,v,w\right)\in {T}_{k}^{d}⇒\left(a,b,c\right)\circ \left(u,v,w\right)\in {T}_{k}^{n}\text{.}$

 Proof of 2.9. Suppose $\left(a,b,c\right)\in {V}_{d}^{n}$ and $\left(u,v,w\right)\in {V}_{k}^{d}\text{.}$ Let $A,B,C$ be arbitrary $\left(k,n\right)\text{-towers}$ of type $a\circ u,b\circ v,c\circ w,$ respectively. Then there exist $\left(d,n\right)\text{-towers}$ $A\prime ,B\prime ,C\prime ,$ of type $a,b,c,$ respectively, such that $Au(i)′ = Ai, Bv(i)′ = Bi, Cw(i)′ = Ci.$ By hypothesis, $\mathrm{\Omega }\left(A\prime \right)\wedge \mathrm{\Omega }\left(B\prime \right)\wedge \mathrm{\Omega }\left(C\prime \right)\ne {\text{?? maybe}} {\varnothing }\text{.}$ Hence there exists a $d\text{-dimensional}$ subspace $L\prime$ such that $dim(L′∧Ai′)≥i, i=1,2,…,d, dim(L′∧Bi′)≥i, i=1,2,…,d, dim(L′∧Ci′)≥i, i=1,2,…,d.$ Define $\left(k,d\right)\text{-towers}$ $U\prime ,V\prime ,W\prime ,$ by $Ui′ = L′∧Au(i)′, Vi′ = L′∧Bu(i)′, Wi′ = L′∧Cu(i)′.$ Define sequences $u\prime ,v\prime ,w\prime$ in ${Q}_{k,d}$ by $ui′ = dim(Ui′), vi′ = dim(Vi′), wi′ = dim(Wi′).$ Then $u\overline{){=}}{\le }u\prime ,$ $v\overline{){=}}{\le }v\prime ,$ and $w\overline{){=}}{\le }w\prime ,$ so there exist $\left(k,d\right)\text{-towers}$ $U,V,W,$ of type $u,v,w,$ respectively such that ${U}_{i}\overline{){<}}{\le }{U}_{i}^{\prime },$ ${V}_{i}\overline{){<}}{\le }{V}_{i}^{\prime },$ and ${W}_{i}\overline{){<}}{\le }{W}_{i}^{\prime }$ for $i=1,2,\dots ,k\text{.}$ Since $\left(u,v,w\right)\in {V}_{k}^{d},$ there exists $k\text{-dimensional}$ subspace $L$ such that $L\in \mathrm{\Omega }\left(U\right)\wedge \mathrm{\Omega }\left(V\right)\wedge \mathrm{\Omega }\left(w\right)\text{.}$ In particular, $L Notice that for $i=1,2,\dots ,k$ $dim(L∧Ai) = dim(L∧Au(i)′) = dim(L∧L′∧Au(i)′) = dim(L∧Ui′) ≥ dim(L∧Ui) ≥ i.$ Hence $L\in \mathrm{\Omega }\left(A\right)\text{.}$ Similarly, $L\in \mathrm{\Omega }\left(B\right)$ and $L\in \mathrm{\Omega }\left(C\right)\text{.}$ Since $A,B,C$ are arbitrary $\left(k,n\right)\text{-towers}$ of type $a\circ u,$ $b\circ v,$ and $c\circ w,$ the proof is complete. $\square$

We remark that Theorem 2.9 holds true if ${V}_{d}^{n}$ is replaced by ${V}_{d}^{n}\left(F\right),$ where $F$ is any field.

 Proof of 2.10. We introduce notation for use in this and subsequent proofs. Let $Idn= { (a,b,c) | 1) a,b,c∈Qd,n, 2) SUM(a,b,c)≥ 2(n+1)d- d(d+1)2 } .$ Then $Tdn= { (a,b,c) | 1) (a,b,c)∈Idn, 2) For k The proof of 2.10 is by induction on $d\text{.}$ The result is trivial for $d=1\text{.}$ Assume the result holds for $1,2,\dots ,d-1$ and let $\left(a,b,c\right)\in {T}_{d}^{n}$ and $\left(u,v,w\right)\in {T}_{k}^{d}\text{.}$ Then by definition, $\left(a,b,c\right)\circ \left(u,v,w\right)\in {I}_{k}^{n}\text{.}$ Let $\left(x,y,z\right)\in {T}_{s}^{k}\text{.}$ We must show $[(a,b,c)∘(u,v,w)]∘(x,y,z) ∈Isn. (*)$ But $[(a,b,c)∘(u,v,w)]∘(x,y,z)= (a,b,c)∘[(u,v,w)∘(x,y,z)].$ By induction, $\left(u,v,w\right)\circ \left(x,y,z\right)\in {T}_{s}^{d}$ holds, and so (*) holds. $\square$

We conclude this section by noting that the proof of 2.9 yields the following

$\left(a,b,c\right)<\left(a\prime ,b\prime ,c\prime \right)$ and $\left(a,b,c\right)\in {V}_{d}^{n}⇒\left(a\prime ,b\prime ,c\prime \right)\in {V}_{d}^{n}\text{.}$

## Notes and References

This is an excerpt from Steven Andrew Johnson's 1979 dissertation The Schubert Calculus and Eigenvalue Inequalities for Sums of Hermitian Matrices.