Last updated: 14 October 2014
In this section we apply the machinery of sections 2, 3, and 4, to prove that for The proof is by induction on and is somewhat lengthy. The rough idea is as follows. We can show that using the induction hypothesis and Theorems 2.9 and 3.11. The proof that is much more involved. Suppose Using Theorem 3.9, it is enough to show that We consider two cases:
|1)||For some and some the triple is "sum-minimal";|
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 to partitions in using the function We then show that where for each and a exists (consequences of case 1)). It follows from Theorems 4.13 and 4.14 that a exists, and so
At this point we introduce and review notation and conventions, mostly used to deal with sequences, subsequences, and sums.
|The set of strictly increasing sequences of length chosen from If and then may also be written as|
|The set of partitions (i.e. decreasing sequences of non-negative integers) of length at most By convention, and include the empty sequence|
|These symbols denote binary operators which map a pair of sequences into another sequence; they are defined as follows: For and define by For and define by For and define by For and define by By convention,|
|These symbols denote unary operators defined on sequences, as given in section 1.|
|This is the map from to defined by By convention,|
|The inverse of|
|These are sets defined in section 2.|
|sub-minimal||An element is called sub-minimal if|
|This symbol is used to denote the dictionary partial orders on the sets and|
The set consists of which satisfy a complicated set of inequalities. Our intention is to show that We have previously shown that certain elements belong to if a exists; that is, we switch from looking at sequences in and consider instead the images in This suggests mapping the elements of into and investigating the image set. It turns out that the image elements satisfy a simplified set of inequalities.
It will be shown during the proof of the main theorem that
For the moment, we limit ourselves to examining some convexity properties of To do so, we define a slightly more general set.
Note that is simply the set of integral elements belonging to Regarded as a subset of is a pointed convex cone, since it is defined by a set of homogeneous linear inequalities. From convexity theory, is the convex hull of its extreme rays.
Let If is an extreme ray of then there exists and such that
Let be an extreme ray of Set The theorem is true if We show that assuming the contrary leads to a contradiction. This is done by "nudging" in two directions. Let and be the lengths of and respectively, and let be the where the zeroes appear times. Then This expresses as a convex combination of two non-collinear elements of contradicting the assumption that is an extreme ray.
Let the linear inequalities defining be denoted by where each is a linear functional defined on Any extreme ray of lies in one dimensional subspace defined by linear equations of the form Since all coefficients of each such linear equation are rational (in fact, every coefficient is either or 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 may be expressed in the form where is a real number and is an integral extreme ray of (which means also belongs to All this leads to the following.
Any element of may be expressed as a
positive nonnegative real
linear combination of integral extreme rays.
In this section we establish several identities dealing with sequences, the unary operators and and the binary operators and
2) Recall that and note that Hence
4) Recall from Section 1 that if then Then since and we have and By definition, so
5) The basic statement is trivial; the special case follows by taking and and then nothing that
The result if trivial for We take as induction hypothesis that for all and
We first show that Let From Theorem 3.11, we have that Now let where By induction By Theorem 2.9, then again by induction, and so
The proof that is far more intricate. We shall step through the proof a lemma at a time. Throughout we assume that
Lemma 7 If and is sum-minimal, then
Lemma 8 Let and let Set Then and hence
The next lemma shows that the main theorem is true in certain cases.
Lemma 9 Let and If is sum-minimal, then
Lemma 9 shows that if and one of the "sub"-inequalities it satisfies is in fact equality, then If we switch our attention to elements of Lemma 9 implies that any element of which is an extreme ray of is the image of an element belonging to for some The next (and last!) lemma states this in a manner suitable for our final manipulations.
Lemma 10 If is an extreme ray of such that then there exists a
We can now prove that Let From Theorem 2.11, we may assume that is minimal in with respect to the ordering If there exists and such that is sum-minimal, then we are done by Lemma 9. If no such exists, then must be sum-minimal, for otherwise one could reduce some entry of by and still have a member of contradicting the minimality of Set Regard as an element of By Theorem 5.4, we may write where each is an integral extreme ray of and each From Lemma 8 and the sum-minimality of we must have Since each for each Then by Lemma 10, there exists a (which we will call for each Write By Theorem 4.12, is an LRD, and so by Theorem 4.1 there exists a Translating via Theorem 4.17, we have and this finishes the proof.
This is an excerpt from Steven Andrew Johnson's 1979 dissertation The Schubert Calculus and Eigenvalue Inequalities for Sums of Hermitian Matrices.