The Schubert Calculus and Eigenvalue Inequalities for Sums of Hermitian Matrices

Arun Ram
Department of Mathematics and Statistics
University of Melbourne
Parkville, VIC 3010 Australia

Last updated: 14 October 2014

Horn's Conjecture and the Hersch–Zwahlen Methods

Horn's Conjecture

The set Tdn introduced by Horn [Hor1962] is defined recursively as follows: T1n = { (a,b,c)| 1)a,b,cQ1,dn 2)a+b=c+1 } , Tdn = { (a,b,c)| 1) a,b,cQd,n, 2) i=1d (ai+bi) = i=1dci +d·(d+1)2, 3) If(u,v,w) Tdknd (k<d), i=1dk (au)i+ (bv)i i=1dk (cw)i+ k·(k+1)2 } . Horn conjectured that Tdn<Sdn for all d and n; he showed that for all n, T1n=S1n, T2n=S2n, and T3n<S3n; but further, that S416T416. The following lemma was the key tool used.

(The "pushing" lemma for Sdn) Let (a,b,c)Sdn, and let u,v,w, be three integers such that 1ud+1, 1vd+1, and 1wd. Set ai = ai+δu-1(i), bi = bi+δv-1(i), ci = ci+δw-1(i). If au+bvcw-1+cd+2, then (a,b,c)Sdn+1.

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 (a,b,c)Tdn, there exists (a,b,c)Tdn-1 which can be "pushed" to (a,b,c). This can be done except for one special case in T3n, 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,cQd,n, 2) Given any three hermitian matricesA,B,Csuch thatA+B+C=0, Σa(A)+ Σb(B)+ Σc(C)0 } . There is a one-to-one correspondence between Sdn and Sdn given by (a,b,c)(a,b,c). That is, (a,b,c) Sdniff (a,b,c)Sdn. If the same correspondence is applied to Tdn, one obtains

T1n = {(a,b,c)|a+b+c=2n+1}, Tdn = { (a,b,c)| 1) a,b,cQd,n, 2) Σ(a,b,c) =2(n+1)d- d(d+1)2, 3) Ifk<dand (u,v,w) Tkd, Σ(a,b,c) (u,v,w)2 (dn+1)k- k(k+1)2 } . It can be shown that (a,b,c)Tdn iff (a,b,c)Tdn. Horn's conjecture is thus equivalent to the conjecture that Tdn<Sdn.

In [HZw1962] J. Hersch and B. P. Zwahlen developed a new technique for establishing membership in Sdn. We introduce some notation relevant to their method. Let An(F) denote affine n-space over a field F.

A (d,n,F)-tower is a sequence (A1,A2,,Ad) of d nested subspaces A1<A2<Ad in An(F).

A tower is said to be of type a if aQd,n and dim(Ai)=ai for i=1,2,,d.

Let A be a (d,n,F)-tower.

Ω(A)= { L| 1) Lis a subspace of dimensiondin An(F), 2) dim(LAi)i fori=1,2,,d } . We call Ω(A) a Schubert variety of type a.

Vdn(F)= { (a,b,c)| 1) a,b,c<Qd,n, 2) For any three(d,n,F) -towersA,B,C, of type a,b,c Ω(A) Ω(B) Ω(C) } . By convention, Vdn=Vdn(), where denotes the field of complex numbers.

(Hersch-Zwahlen) Vdn<Sdn

Thompson's result

Theorem 2.7 shows that Horn's conjecture would be true if Tdn<Vdn. In [Zwa1966], Zwahlen investigated this possibility. He was able to show that T1n=V1n and T2n=V2n for all n, but could not quite verify that T3n<V3n. Zwahlen's methods were purely geometrical, and required no special properties of the group field F.

In [TTh1974], R. C. Thompson made clear the problem with Zwahlen's methods. Thompson showed that T3n<V3n() for all n, but that in general, T3nV3n(?? maybe). His approach started by establishing the following lemma.

(The "pushing" lemma for Vdn) Let (a,b,c)Vdn(F), where F is an arbitrary field. Let u,v,w be three integers chosen from {0,1,2,,d}. Set ai = ai+δu(i), bi = bi+δv(i), ci = ci+δw(i), a0=b0=c0=0. If au+bv+cwn, then (a,b,c)Vdn+1(F).

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 T3n can be obtained by pushing from elements of T3n-1 except for one special case. A difficult analysis of this special case showed that T3n<V3n(F) for all n if F is algebraically closed, but not otherwise.

Identities for Vdn and Tdn

The main assertion of the present work is that Tdn=Vdn() for all n if d4. 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.

(a,b,c)Vdn and (u,v,w)Vkd(a,b,c)(u,v,w)Vkn.

(a,b,c)Tdn and (u,v,w)Tkd(a,b,c)(u,v,w)Tkn.

Proof of 2.9.

Suppose (a,b,c)Vdn and (u,v,w)Vkd. Let A,B,C be arbitrary (k,n)-towers of type au,bv,cw, respectively. Then there exist (d,n)-towers A,B,C, of type a,b,c, respectively, such that Au(i) = Ai, Bv(i) = Bi, Cw(i) = Ci. By hypothesis, Ω(A)Ω(B)Ω(C)?? maybe. Hence there exists a d-dimensional subspace L such that dim(LAi)i, i=1,2,,d, dim(LBi)i, i=1,2,,d, dim(LCi)i, i=1,2,,d. Define (k,d)-towers U,V,W, by Ui = LAu(i), Vi = LBu(i), Wi = LCu(i). Define sequences u,v,w in Qk,d by ui = dim(Ui), vi = dim(Vi), wi = dim(Wi). Then u=u, v=v, and w=w, so there exist (k,d)-towers U,V,W, of type u,v,w, respectively such that Ui<Ui, Vi<Vi, and Wi<Wi for i=1,2,,k. Since (u,v,w)Vkd, there exists k-dimensional subspace L such that LΩ(U)Ω(V)Ω(w). In particular, L<L. Notice that for i=1,2,,k dim(LAi) = dim(LAu(i)) = dim(LLAu(i)) = dim(LUi) dim(LUi) i. Hence LΩ(A). Similarly, LΩ(B) and LΩ(C). Since A,B,C are arbitrary (k,n)-towers of type au, bv, and cw, the proof is complete.

We remark that Theorem 2.9 holds true if Vdn is replaced by Vdn(F), 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,cQd,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) Fork<dand (u,v,w)Tkd, (a,b,c) (u,v,w)Ikn } . The proof of 2.10 is by induction on d. The result is trivial for d=1. Assume the result holds for 1,2,,d-1 and let (a,b,c)Tdn and (u,v,w)Tkd. Then by definition, (a,b,c)(u,v,w)Ikn. Let (x,y,z)Tsk. 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, (u,v,w)(x,y,z)Tsd holds, and so (*) holds.

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

(a,b,c)<(a,b,c) and (a,b,c)Vdn(a,b,c)Vdn.

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.

page history