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
aram@unimelb.edu.au

Last updated: 14 October 2014

Proof of the main result: Vdn=Tdn, d4

In this section we apply the machinery of sections 2, 3, and 4, to prove that Vdn=Tdn for d4. The proof is by induction on d, and is somewhat lengthy. The rough idea is as follows. We can show that Vdn<Tdn using the induction hypothesis and Theorems 2.9 and 3.11. The proof that Tdn<Qd,n is much more involved. Suppose (a,b,c)Tdn. Using Theorem 3.9, it is enough to show that Ω(a)·Ω(b)·Ω(c)0. We consider two cases:

1) For some k<d and some (u,v,w)Tkd, the triple (a,b,c)(u,v,w) is "sum-minimal";
2) Otherwise.

For case 1), one can apply the induction hypothesis, some intricate manipulation of sequences, plus the generalized pushing lemma to get the desired result. For case 2), we switched over from sequences in Qd,n to partitions in Πd using the function θ-1: λ = θ-1(a), μ = θ-1(b), ν = θ-1(c). We then show that (λ,μ,ν)= αi· (λi,μi,νi), where for each i, αi>0 and a (λi,μi,νi)-LRA exists (consequences of case 1)). It follows from Theorems 4.13 and 4.14 that a (λ,μ,ν)-LRA exists, and so (a,b,c)Vdn.

Notations and Conventions

At this point we introduce and review notation and conventions, mostly used to deal with sequences, subsequences, and sums.

Symbol Explanation

Qd,n The set of strictly increasing sequences of length d chosen from 1,2,,n. If aQd,n and a(a1,a2,,ad), then ai may also be written as a(i).
Πd The set of partitions (i.e. decreasing sequences of non-negative integers) of length at most d. By convention, Qd,n and Πd include the empty sequence .
,*, These symbols denote binary operators which map a pair of sequences into another sequence; they are defined as follows: For aQd,n and uQk,d, define au by (au)(i)= aui, (auQkn). For aQd,n and uQk,d, define a*u by (a*u)(i)= aui-ui+i, (a*uQk,n-d+k). For aQd,n and aQd,n, define aa by (aa)(i)= ai+ai-i, (aaQd,n+n-d). For λΠd and uQk,d, define λu by (λu)(i)= λui (λuΠk). By convention, (a,b,c) (u,v,w) = ( au, bv, cw ) , (a,b,c)* (u,v,w) = ( a*u,b*v,c*w ) , (a,b,c) (u,v,w) = (au,bv,cw).
a,aˆ,a These symbols denote unary operators defined on sequences, as given in section 1.
θd,n This is the map from Πd to Qd,n defined by θd,n(λ)= { , ifλ???/p, n-d+1-λ1, n-d+2-λ2,, n-λd, otherwise. By convention, θ=θn=θd,n.
θd,n-1 The inverse of θd,n: [θd,n-1(a)] (i)=n-d+i-ai.
Idn,Tdn These are sets defined in section 2.
sub-minimal An element (a,b,c)Tdn is called sub-minimal if (a,b,c)=2(n+1)d-d(d+1)2.
This symbol is used to denote the dictionary partial orders on the sets Qd,n and Qd,n3.

Special Features of Tdn.

The set Tdn consists of 3d-tuples which satisfy a complicated set of inequalities. Our intention is to show that Tdn=Vdn. We have previously shown that certain elements (a,b,c) belong to Vdn if a (θ-1(a),θ-1(b),θ-1(c))-LRA exists; that is, we switch from looking at sequences a,b,c in Qd,n and consider instead the images θ-1(a),θ-1(b),θ-1(c) in Πd. This suggests mapping the elements of Tdn into Πd and investigating the image set. It turns out that the image elements satisfy a simplified set of inequalities.

Id = { (λ,μ,ν)| 1) λ,μ,νare sequences of positive real numbers of lengthd, 2) i=1dλi+ μi-νi0 } , Td = { (λ,μ,ν)| 1) λ,μ,νΠd, 2) For anykdany any (u,v,w)Tkd, (λ,μ,ν) (u,v,w) Ik } .

It will be shown during the proof of the main theorem that Td=n=d θd,n-1 (Tdn).

For the moment, we limit ourselves to examining some convexity properties of Td. To do so, we define a slightly more general set.

Td*= { (λ,ν,μ)| 1) λ,μ,νare real sequences of lengthd, 2) λ1λ2λd0, μ1μ2μd0, ν1ν2νd0, 3) For anykdand any (u,v,w)Tkd, (λ,μ,ν) (u,v,w)Ik } . Note that Td is simply the set of integral elements belonging to Td*. Regarded as a subset of 3d, Td* is a pointed convex cone, since it is defined by a set of homogeneous linear inequalities. From convexity theory, Td* is the convex hull of its extreme rays.

Let d>1. If (λ,μ,ν) is an extreme ray of Td*, then there exists k<d and (u,v,w)Tkd such that i=1kλμi +μvi-νwi =0.

Proof.

Let (λ,μ,ν) be an extreme ray of Td*. Set ξ=min(u,v,w)k=1d-1Tkd ( i=1kλμi +μvi-νwi ) . The theorem is true if ξ=0. We show that assuming the contrary leads to a contradiction. This is done by "nudging" (λ,μ,ν) in two directions. Let l and n be the lengths of λ and μ, respectively, and let ξt be the d-sequence ξt= { ξl,ξl,, ξl,0,0,,0 } , Notes indicate that the factions in this set may be subscript. where the zeroes appear d-t times. Then (λ,μ,ν)= (λ+ξl,μ-ξm,ν)2+ (λ-ξl,μ+ξm,ν)2. This expresses (λ,μ,ν) as a convex combination of two non-collinear elements of Td*, contradicting the assumption that (λ,μ,ν) is an extreme ray.

Let the linear inequalities defining Td* be denoted by Li(λ,μ,ν)0 (i=1,2,), where each Li is a linear functional defined on 3d. Any extreme ray of Td* lies in one dimensional subspace defined by 3d-1 linear equations of the form Li(λ,μ,ν)=0. Since all coefficients of each such linear equation are rational (in fact, every coefficient is either 1,-1, or 0), the one-dimensional solution space has a rational basis vector, i.e. a basis vector all of whose components are rational numbers. This implies that any extreme ray of Td* may be expressed in the form r·(λ,μ,ν), where r is a real number and (λ,μ,ν) is an integral extreme ray of Td* (which means (λ,μ,ν) also belongs to Td). All this leads to the following.

Any element of Td* may be expressed as a positive nonnegative real linear combination of integral extreme rays.

Identities

In this section we establish several identities dealing with sequences, the unary operators A, aˆ, and a, and the binary operators , *, and .

Let a,b,cQd,n, d<n, u,v,wQk,d, k<d, x,y,zQ3,???? read the notes here, ????? Then

1) (au)i=n+1-(au)k+1-i,
2) (uˆxˆˆ)=(ux),
3) ((a*u)x)=[a*(ux)]x,
4) (a*ua*uˆ)=a,
5) (a,b,c)(u,v,w)= (a,b,c)- (a,b,c)(uˆ,vˆ,wˆ).
As a special case of 5), we note that
5.1) (a,b,c)= 3n(n+1)/d2- (aˆ,bˆ,cˆ).

Proofs.

1) Trivial.

2) Recall that u=uˆ=uˆ and note that ux=ux. Hence (ux)= (uˆxˆ)ˆ= (uˆxˆ)ˆ.

3) Compute: ((a*u)x)i = (a*u)xi = (au)xi- uxi+xi = (a(ux))i- (ux)i+i+xi-i = { [a*(ux)] x } i .

4) Recall from Section 1 that if aQd,n, then ai=d+i- t=1d δat-t (n-d+1-i). Then since a*uQk,n-d+k and a*uˆQd-k,n-k, we have (a*u)i = k+i-t=1k δa*ut-t (n-d+k-k+1-i) = k+i-t=1k δaut-ut (n-d+1-i) and (a*uˆ)i = (d-k)+i- t=1d-k δa*uˆt-t ((n-k)-(d-k)+1-i) = d-k+i- t=1d-k δauˆt-uˆt (n-d+1-i). By definition, [(a*u)(a*uˆ)]i= (a*u)i+ (a*uˆ)i-i, so [(a*u)(a*uˆ)]i = d+i-t=1d δat-t (n-d+1-i) = ai.

5) The basic statement is trivial; the special case follows by taking k=d and u=v=w=(1,2,3,,d), and then nothing that (a,b,c)+ (aˆ,bˆ,cˆ)= 3·i=1ni.

Proof of Horn's Conjecture

Tdn=Vdnford4.

Proof.

The result if trivial for d=1. We take as induction hypothesis that Tin=Vin for all ni and i<d.

We first show that Vdn<Tdn. Let (a,b,c)Vdn. From Theorem 3.11, we have that (a,b,c)Idn. Now let (u,v,w)Tkd, where k<d. By induction (u,v,w)Vkd. By Theorem 2.9, (a,b,c)(u,v,w)Vkn; then again by induction, (a,b,c)(u,v,w)Tkn; and so (a,b,c)(u,v,w)Ikn.

The proof that Tdn<Vdn is far more intricate. We shall step through the proof a lemma at a time. Throughout we assume that 1k<d.

Lemma 1

i) Any element of Tkd which is minimal with respect to the order is sub-minimal.
ii) If (u,v,w)Tkd and (u,v,w)(u,v,w), then (u,v,w)Tkd.

Proof.

By induction, Tkd=Vkd; the result then follows from Theorems 3.10 and 3.11.

Lemma 2 (u,v,w)Tkd (u,v,w) Td-kd.

Proof.

Again, use induction and Theorem 4.11.

Lemma 3 (a,b,c)Ikn and (a,b,c) Ikn (a,b,c) (a,b,c) Ikn+n-k

Proof.

(a,b,c) (a,b,c) = (a,b,c)+ (a,b,c)- 3i=1ki 2(n+1)k- k(k+1)2+ 2(n+1)k- k(k+1)2- 3k(k+1)2 = 2(n+n+2)k-2 (k+1)k- k(k+1)2 = 2(n+n-k+1)k- k(k+1)2.

Lemma 4 (a,b,c)Tdn and (u,v,w)Tkd (a,b,c)* (u,v,w) Ikn-d+k

Proof.

From Lemma 1, we may assume that (u,v,w) is sum-minimal.

Since (a,b,c)(u,v,w)Tkn, we may compute that (a,b,c)* (u,v,w) = (a,b,c)(u,v,w) -(u,v,w)+3 i=1ki [ 2(n+1)k- k(k+1)2 ] - [ 2(d+1)k- k(k+1)2 ] +3k(k+1)2 = 2(n-d)k+ 2k(k+1)- k(k+1)2 = 2(n-d+k+1)k -k(k+1)2.

Lemma 5 (a,b,c)Tdn and(u,v,w) Tkd (a,b,c)* (u,v,w) Tkn-d+k

Proof.

The first part of the required argument is taken care of by Lemma 4. For the second part, let (x,y,z)Tsk; we need to show that [(a,b,c)*(u,v,w)] (x,y,z) Isn-d+k. We know that (u,v,w)(x,y,z)Tsd. From Theorem 5.5(iii), [(a,b,c)*(u,v,w)] (x,y,z)= [(a,b,c)]* [(u,v,w)(x,y,z)] (x,y,z). By Lemma 4, the quantity in braces belongs to Isn-d+s; applying Lemma 3 yields the desired result.

Lemma 6 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) Ikn-d+k } .

Proof.

The inclusion < follows from Lemma 5. The reverse inclusion follows from Lemma 3 and the fact that (a,b,c)(u,v,w)= [(a,b,c)*(u,v,w)] (u,v,w).

Lemma 7 If (a,b,c)Tdn, (u,v,w)Tkd, and (a,b,c)*(u,v,w) is sum-minimal, then (a,b,c)*(uˆ,vˆ,wˆ)Td-kn-k.

Proof.

This is a tough one. We begin by showing that (a,b,c)*(uˆ,vˆ,wˆ)Id-kn-k: we have (a,b,c)*(uˆ,vˆ,wˆ) = (a,b,c) (uˆ,vˆ,wˆ)- (uˆ,vˆ,wˆ)+ 3i=1d-ki. Apply Theorem 5.5(v): a = [ (a,b,c)- (a,b,c)(u,v,w) ] - [ 3d(d+1)2- (u,v,w) ] + 3(d-k)(d-k+1)2 = (a,b,c)- [ (a,b,c)* (u,v,w)- 3k(k+1)2 ] -3d(d+1)2+ 3(d-k)d-k+12 Use the sum-minimality of (a,b,c)*(u,v,w) and the fact that (a,b,c)Tdn: a = [ 2(n+1)d- d(d+1)2- [ 2(n-d+k+1)k -k(k+1)2- 3k(k+1)2 ] -3d(d+1)2+ 3(d-k)(d-k+1)2 ] Simplify: a = 2(n+1)d- 2(d+1)d- 2(n-d+k+1)k+ 2k(k+1)+ 3(d-k)(d-k+1)2 = 2(n-d)d- 2(n-d)k+ 3(d-k)(d-k+1)2 = 2(n-d)(d-k)+ 2(d-k)(d-k+1)- (d-k)(d-k+1)2 = 2(n-k+1)(d-k)- (d-k)(d-k+1)2. Now let (x,y,z)Tsd-k, where 1s<d-k. We must show that [(a,b,c)*(uˆ,vˆ,wˆ)] (x,y,z)Isn-k. First note that by Lemma 2, (u,v,w) Td-kd and (x,y,z) Td-k-sd-k. Hence (u,v,w) (x,y,z) Td-k-sd and (u,v,w)(x,y,z) Td-k-sd. Let (p,q,r)= (u,v,w)(x,y,z); by Theorem 5.5(ii), (p,q,r)= (uˆ,vˆ,wˆ)(xˆ,yˆ,zˆ)ˆ ; or (pˆ,qˆ,rˆ)= (uˆ,vˆ,wˆ) (xˆ,yˆ,zˆ). Compute: [(a,b,c)*(uˆ,vˆ,wˆ)](x,y,z) = (a,b,c)(uˆ,vˆ,wˆ)(x,y,z)- (uˆ,vˆ,wˆ)(x,y,z)+ (x,y,z) Apply Theorem 5.5(v): a = [ (a,b,c)(uˆ,vˆ,wˆ)- (a,b,c)(uˆ,vˆ,wˆ)(xˆ,yˆ,zˆ) ] - [ (uˆ,vˆ,wˆ)- (uˆ,vˆ,wˆ)(xˆ,yˆ,zˆ) ] + (x,y,z) Substitute (pˆ,qˆ,rˆ): a = (a,b,c)(uˆ,vˆ,wˆ)- (a,b,c)(pˆ,qˆ,rˆ)- [ (uˆ,vˆ,wˆ)- (pˆ,qˆ,rˆ) ] + (x,y,z) Apply Theorem 5.5(v): a = [ (a,b,c)- (a,b,c)(u,v,w) ] - [ (a,b,c)- (a,b,c)(p,q,r) ] - [ 3d(d+1)2- (u,v,w) ] + [ 3d(d+1)2- (p,q,r) ] + (x,y,z) = [ (a,b,c)(p,q,r)- (p,q,r) ] - [ (a,b,c)(u,v,w)- (u,v,w) ] + (x,y,z) = [ (a,b,c)*(p,q,r)- 3(k+s)(k+s+1)2 ] - [ (a,b,c)*(u,v,w)- 3k(k+1)2 ] + (x,y,z) By assumption, (a,b,c)*(u,v,w) is sum-minimal and (a,b,c)*(p,q,r)Tk+sn-d+k+s.

Using this, we have [ 2(n-d+k+s+1)(k+s)- (k+s)(k+s+1)2- 3(k+s)(k+s+1)2 ] - [ 2(n-d+k+1)k- k(k+1)2- 3k(k+1)2 ] + [ 2(d-k+1)s- s(s+1)2 ] = 2(n-d+k+s+1)(k+s)- 2(k+s)(k+s+1) - 2(n-d+k+1)k+ 2k(k+1)+ 2(d-k+1)s- s(s+1)2 Fidget a little: a = 2(n-d)(k+s)- 2(n-d)k+ 2(d-k+1)s- s(s+1)2 = 2(n-d)s+ 2(d-k+1)s- s(s+1)2 = 2(n-k+1)s- s(s+1)2. DONE!

Lemma 8 Let (u,v,w)Tkd (1k<d), and let a,b,cQd,n. Set λ = θd,n-1(a), μ = θd,n-1(b), ν = θd,n-1(c). Then i=1k λ(μi)+ μ(vi)- ν(wi)= 2(n-d+k+1)k- k(k+1)2- (a,b,c)*(u,v,w) and hence (λ,μ,ν)Td (a,b,c)Tdn.

Proof.

Recall that if xQd,n, then xi=n+1- xd+1-i and [θd,n-1(x)]i= n-d+i-xi. So ci = n+1-cd+1-i, wi = nd+1-wdk+1-i and νwi = [θd,n-1(c)]wi = n-d+wi- cwi = n-d+ (d+1-wk+1-i)- (n+1-cd+1-wi) = cd+1-wi- wk+1-i = cwk+1-i- wk+1-i. Compute: i=1k λ(μi)+ μ(vi)- ν(wi) = i=1k (n-d+ui-aui)+ (n-d+vi-bvi)- (cwk+1-i-wk+1-i) = 2(n-d)k+ i=1d(ui+vi+wi)- i=1d(aui+bvi+cwi) = 2(n-d)k- (a,b,c)(u,v,w)+ (u,v,w) = 2(n-d)k- [ (a,b,c)*(u,v,w)- 3k(k+1)2 ] = 2(n-d)k+ 3k(k+1)2- (a,b,c)*(u,v,w) = 2(n-d)k+ 2k(k+1)- k(k+1)2- (a,b,c)*(u,v,w) = 2(n-d+k+1)k- k(k+1)2- (a,b,c)*(u,v,w). This shows that (λ,μ,ν)(u,v,w)Ik (a,b,c)*(u,v,w)Ikn-d+k, and so (λ,μ,ν)Td (a,b,c)Tdn.

The next lemma shows that the main theorem is true in certain cases.

Lemma 9 Let (a,b,c)Tdn and (u,v,w)Tkd (1k<d). If (a,b,c)*(u,v,w) is sum-minimal, then (a,b,c)Vdn.

Proof.

By Lemma 5 and induction, (a,b,c)*(u,v,w) Tkn-d+k= Vkn-d+k. By Lemma 7 and induction, (a,b,c)*(uˆ,vˆ,wˆ) Td-kn-k= Vd-kn-k. By Theorem 4.11, (a,b,c)*(uˆ,vˆ,wˆ) Vn-dn-k, (a,b,c)*(u,v,w) Vn-dn-d+k. By Theorem 5.5(iv) and Theorem 4.18, (a,b,c)*(u,v,w) (a,b,c)*(uˆ,vˆ,wˆ) Vn-dn. Hence by duality (Theorem 4.11), (a,b,c)Vdn.

Lemma 9 shows that if (a,b,c)Tdn and one of the "sub"-inequalities it satisfies is in fact equality, then (a,b,c)Vdn. If we switch our attention to elements of Td, Lemma 9 implies that any element of Td which is an extreme ray of Td* is the image of an element (a,b,c) belonging to Vdn for some n. The next (and last!) lemma states this in a manner suitable for our final manipulations.

Lemma 10 If (λ,μ,ν)Td is an extreme ray of Td* such that i=1dλi+ μi-νi=0, then there exists a (λ,μ,ν)-LRA.

Proof.

Let n=max(λ1,μ1,ν1)-d+1. Set a = θd,n(λ), b = θd,n(μ), c = θd,n(ν). If (λ,μ,ν) is an extreme ray of Td*, then by Theorem 5.3 there exists (u,v,w)Tkd such that i=1kλui +μvi-νwi=0. Then Lemma 98 implies that (a,b,c)*(u,v,w) is sub-minimal, so (a,b,c)Vdn by Lemma 9, and hence the theorem holds by Theorem 4.17.

We can now prove that Tdn<Vdn. Let (a,b,c)Tdn. From Theorem 2.11, we may assume that (a,b,c) is minimal in Tdn with respect to the ordering . If there exists k<d and (u,v,w)Tkd such that (a,b,c)*(u,v,w) is sum-minimal, then we are done by Lemma 9. If no such (u,v,w) exists, then (a,b,c) must be sum-minimal, for otherwise one could reduce some entry of (a,b,c) by 1 and still have a member of Tdn, contradicting the minimality of (a,b,c). Set λ = θd,n-1(a), μ = θd,n-1(b), ν = θd,n-1(c). Regard (λ,μ,ν) as an element of Td*. By Theorem 5.4, we may write (λ,μ,ν)=j rj(λj,μj,νj), where each (λj,μj,νj) is an integral extreme ray of Td* and each ri>0. From Lemma 8 and the sum-minimality of (a,b,c), we must have i=1dλi +μi-νi=0. Since each ri>0, i=1k λij+ μij- νij=0 for each j. Then by Lemma 10, there exists a (λj,μj,νj)-LRA (which we will call Nj) for each j. Write jrj· (λj,μj,νj,Nj) =(λ,μ,ν,rjNj). By Theorem 4.12, (λ,μ,ν,rjNj) is an LRD, and so by Theorem 4.134 there exists a (λ,μ,ν)-LRA. Translating via Theorem 4.17, we have (a,b,c)Vdn, and this finishes the proof.

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