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: $V_{d}^{n} = T_{d}^{n},$ $d \leq 4$

In this section we apply the machinery of sections 2, 3, and 4, to prove that $V_{d}^{n} = T_{d}^{n}$ for $d \leq 4 .$ The proof is by induction on $d,$ and is somewhat lengthy. The rough idea is as follows. We can show that $V_{d}^{n} < T_{d}^{n}$ using the induction hypothesis and Theorems 2.9 and 3.11. The proof that $T_{d}^{n} < Q_{d, n}$ is much more involved. Suppose $(a, b, c) \in T_{d}^{n} .$ Using Theorem 3.9, it is enough to show that $Ω (a) \cdot Ω (b) \cdot Ω (c) \neq 0 .$ We consider two cases:

1)	For some $k < d$ and some $(u, v, w) \in T_{k}^{d},$ the triple $(a, b, c) \circ (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 $Q_{d, n}$ to partitions in $Π_{d}$ using the function $θ^{- 1} :$ $\begin{array}{rcl} λ & = & θ^{- 1} (a), \\ μ & = & θ^{- 1} (b), \\ ν & = & θ^{- 1} (c) . \end{array}$ We then show that $(λ, μ, ν) = \sum α_{i} \cdot (λ^{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) \in V_{d}^{n} .$

Notations and Conventions

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

Symbol Explanation

$Q_{d, n}$	The set of strictly increasing sequences of length $d$ chosen from $1, 2, \dots, n .$ If $a \in Q_{d, n}$ and $a (a_{1}, a_{2}, \dots, a_{d}),$ then $a_{i}$ 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, $Q_{d, n}$ and $Π_{d}$ include the empty sequence $\emptyset .$
$\circ, *, \oplus$	These symbols denote binary operators which map a pair of sequences into another sequence; they are defined as follows: For $a \in Q_{d, n}$ and $u \in Q_{k, d},$ define $a \circ u$ by $(a \circ u) (i) = a_{u_{i}}, (a \circ u \in Q_{k}^{n}) .$ For $a \in Q_{d, n}$ and $u \in Q_{k, d},$ define $a * u$ by $(a * u) (i) = a_{u_{i}} - u_{i} + i, (a * u \in Q_{k, n - d + k}) .$ For $a \in Q_{d, n}$ and $a' \in Q_{d, n'},$ define $a \oplus a'$ by $(a \oplus a') (i) = a_{i} + a_{i}^{'} - i, (a \oplus a' \in Q_{d, n + n' - d}) .$ For $λ \in Π_{d}$ and $u \in Q_{k, d},$ define $λ \circ u$ by $(λ \circ u) (i) = λ_{u_{i}} (λ \circ u \in Π_{k}) .$ By convention, $\begin{array}{rcl} (a, b, c) \circ (u, v, w) & = & (a \circ u, b \circ v, c \circ w), \\ (a, b, c) * (u, v, w) & = & (a * u, b * v, c * w), \\ (a, b, c) \oplus (u, v, w) & = & (a \oplus u, b \oplus v, c \oplus w) . \end{array}$
$\overline{}, \hat{}, \tilde{}$	These symbols denote unary operators defined on sequences, as given in section 1.
$θ_{d, n}$	This is the map from $Π_{d}$ to $Q_{d, n}$ defined by $θ_{d, n} (λ) = {\begin{cases} \emptyset, & if λ \leq' ??? / p, \\ n - d + 1 - λ_{1}, n - d + 2 - λ_{2}, \dots, n - λ_{d}, & otherwise. \end{cases}$ By convention, $θ = θ_{n} = θ_{d, n} .$
$θ_{d, n}^{- 1}$	The inverse of $θ_{d, n} :$ $[θ_{d, n}^{- 1} (a)] (i) = n - d + i - a_{i} .$
$I_{d}^{n}, T_{d}^{n}$	These are sets defined in section 2.
sub-minimal	An element $(a, b, c) \in T_{d}^{n}$ is called sub-minimal if $\sum (a, b, c) = 2 (n + 1) d - \frac{d (d + 1)}{2} .$
$\leq$	This symbol is used to denote the dictionary partial orders on the sets $Q_{d, n}$ and $Q_{d, n}^{3} .$

Special Features of $T_{d}^{n} .$

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

$\begin{array}{rcl} I_{d} & = & {(λ, μ, ν) | \begin{array}{ll} 1) & λ, μ, ν are sequences of positive real numbers of length d, \\ 2) & \sum_{i = 1}^{d} λ_{i} + μ_{i} - ν_{i} \leq 0 \end{array}}, \\ T_{d} & = & {(λ, μ, ν) | \begin{array}{ll} 1) & λ, μ, ν \in Π_{d}, \\ 2) & For any k \leq d any any (u, v, w) \in T_{k}^{d}, \\ (λ, μ, ν) \circ (u, v, \overline{w}) \in I_{k} \end{array}} . \end{array}$

It will be shown during the proof of the main theorem that $T_{d} = ⋃_{n = d}^{\infty} θ_{d, n}^{- 1} (T_{d}^{n}) .$

For the moment, we limit ourselves to examining some convexity properties of $T_{d} .$ To do so, we define a slightly more general set.

$T_{d}^{*} = {(λ, ν, μ) | \begin{array}{ll} 1) & λ, μ, ν are real sequences of length d, \\ 2) & λ_{1} \geq λ_{2} \geq \dots \geq λ_{d} \geq 0, \\ μ_{1} \geq μ_{2} \geq \dots \geq μ_{d} \geq 0, \\ ν_{1} \geq ν_{2} \geq \dots \geq ν_{d} \geq 0, \\ 3) & For any k \leq d and any (u, v, w) \in T_{k}^{d}, \\ (λ, μ, ν) \circ (u, v, w) \in I_{k} \end{array}} .$ Note that $T_{d}$ is simply the set of integral elements belonging to $T_{d}^{*} .$ Regarded as a subset of $ℝ^{3 d},$ $T_{d}^{*}$ is a pointed convex cone, since it is defined by a set of homogeneous linear inequalities. From convexity theory, $T_{d}^{*}$ is the convex hull of its extreme rays.

Let $d > 1 .$ If $(λ, μ, ν)$ is an extreme ray of $T_{d}^{*},$ then there exists $k < d$ and $(u, v, w) \in T_{k}^{d}$ such that $\sum_{i = 1}^{k} λ_{μ_{i}} + μ_{v_{i}} - ν_{{\overline{w}}_{i}} = 0 .$

Proof.

Let $(λ, μ, ν)$ be an extreme ray of $T_{d}^{*} .$ Set $ξ = min_{(u, v, w) \in ⋃_{k = 1}^{d - 1} T_{k}^{d}} (\sum_{i = 1}^{k} λ_{μ_{i}} + μ_{v_{i}} - ν_{{\overline{w}}_{i}}) .$ 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} = {\frac{ξ}{l}, \frac{ξ}{l}, \dots, \frac{ξ}{l}, 0, 0, \dots, 0}, Notes indicate that the factions in this set may be subscript.$ where the zeroes appear $d - t$ times. Then $(λ, μ, ν) = \frac{(λ + ξ_{l}, μ - ξ_{m}, ν)}{2} + \frac{(λ - ξ_{l}, μ + ξ_{m}, ν)}{2} .$ This expresses $(λ, μ, ν)$ as a convex combination of two non-collinear elements of $T_{d}^{*},$ contradicting the assumption that $(λ, μ, ν)$ is an extreme ray.

$□$

Let the linear inequalities defining $T_{d}^{*}$ be denoted by $L_{i} (λ, μ, ν) \leq 0 (i = 1, 2, \dots),$ where each $L_{i}$ is a linear functional defined on $ℝ^{3 d} .$ Any extreme ray of $T_{d}^{*}$ lies in one dimensional subspace defined by $3 d - 1$ linear equations of the form $L_{i} (λ, μ, ν) = 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 $T_{d}^{*}$ may be expressed in the form $r \cdot (λ, μ, ν),$ where $r$ is a real number and $(λ, μ, ν)$ is an integral extreme ray of $T_{d}^{*}$ (which means $(λ, μ, ν)$ also belongs to $T_{d}).$ All this leads to the following.

Any element of $T_{d}^{*}$ 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 $\overline{},$ $\hat{},$ and $\tilde{},$ and the binary operators $\circ,$ $*,$ and $\oplus .$

Let $\begin{array}{rcl} a, b, c \in Q_{d, n}, & d < n, \\ u, v, w \in Q_{k, d}, & k < d, \\ x, y, z \in Q_{3, ???? read the notes here}, & ????? \end{array}$ Then

1)	${(\overline{a \circ u})}_{i} = n + 1 - {(a \circ u)}_{k + 1 - i},$
2)	$(\hat{\hat{u} \circ \hat{x}}) = (\tilde{\tilde{u} \circ \tilde{x}}),$
3)	$((a * u) \circ x) = [a * (u \circ x)] \oplus x,$
4)	$(\tilde{a * u} \oplus \tilde{a * \hat{u}}) = \tilde{a},$
5)	$\sum (a, b, c) \circ (u, v, w) = \sum (a, b, c) - \sum (a, b, c) \circ (\hat{u}, \hat{v}, \hat{w}) .$

As a special case of 5), we note that

5.1)	$\sum (a, b, c) = 3 n (n + 1) / d 2 - \sum (\hat{a}, \hat{b}, \hat{c}) .$

Proofs.

1) Trivial.

2) Recall that $\tilde{u} = \hat{\overline{u}} = \overline{\hat{u}}$ and note that $\overline{u} \circ \overline{x} = \overline{u \circ x} .$ Hence $\tilde{(\tilde{u} \circ \tilde{x})} = \hat{\overline{(\hat{\overline{u}} \circ \hat{\overline{x}})}} = \hat{(\hat{u} \circ \hat{x})} .$

3) Compute: $\begin{array}{rcl} {((a * u) \circ x)}_{i} & = & {(a * u)}_{x_{i}} \\ = & {(a \circ u)}_{x_{i}} - u_{x_{i}} + x_{i} \\ = & {(a \circ (u \circ x))}_{i} - {(u \circ x)}_{i} + i + x_{i} - i \\ = & {[a * (u \circ x)] \oplus x}_{i} . \end{array}$

4) Recall from Section 1 that if $a \in Q_{d, n},$ then ${\tilde{a}}_{i} = d + i - \sum_{t = 1}^{d} δ_{a_{t} - t} (n - d + 1 - i) .$ Then since $a * u \in Q_{k, n - d + k}$ and $a * \hat{u} \in Q_{d - k, n - k},$ we have $\begin{array}{rcl} {(\tilde{a * u})}_{i} & = & k + i - \sum_{t = 1}^{k} δ_{a * u_{t} - t} (n - d + k - k + 1 - i) \\ = & k + i - \sum_{t = 1}^{k} δ_{a_{u_{t}} - u_{t}} (n - d + 1 - i) \end{array}$ and $\begin{array}{rcl} {(\tilde{a * \hat{u}})}_{i} & = & (d - k) + i - \sum_{t = 1}^{d - k} δ_{a * {\hat{u}}_{t} - t} ((n - k) - (d - k) + 1 - i) \\ = & d - k + i - \sum_{t = 1}^{d - k} δ_{a_{{\hat{u}}_{t}} - {\hat{u}}_{t}} (n - d + 1 - i) . \end{array}$ By definition, ${[(\tilde{a * u}) \oplus (a * \tilde{\hat{u}})]}_{i} = {(\tilde{a * u})}_{i} + {(\tilde{a * \hat{u}})}_{i} - i,$ so $\begin{array}{rcl} {[(\tilde{a * u}) \oplus (a * \tilde{\hat{u}})]}_{i} & = & d + i - \sum_{t = 1}^{d} δ_{a_{t} - t} (n - d + 1 - i) \\ = & {\tilde{a}}_{i} . \end{array}$

5) The basic statement is trivial; the special case follows by taking $k = d$ and $u = v = w = (1, 2, 3, \dots, d),$ and then nothing that $\sum (a, b, c) + \sum (\hat{a}, \hat{b}, \hat{c}) = 3 \cdot \sum_{i = 1}^{n} i .$

$□$

Proof of Horn's Conjecture

$T_{d}^{n} = V_{d}^{n} for d \leq 4 .$

Proof.

The result if trivial for $d = 1 .$ We take as induction hypothesis that $T_{i}^{n} = V_{i}^{n}$ for all $n \geq i$ and $i < d .$

We first show that $V_{d}^{n} < T_{d}^{n} .$ Let $(a, b, c) \in V_{d}^{n} .$ From Theorem 3.11, we have that $(a, b, c) \in I_{d}^{n} .$ Now let $(u, v, w) \in T_{k}^{d},$ where $k < d .$ By induction $(u, v, w) \in V_{k}^{d} .$ By Theorem 2.9, $(a, b, c) \circ (u, v, w) \in V_{k}^{n};$ then again by induction, $(a, b, c) \circ (u, v, w) \in T_{k}^{n};$ and so $(a, b, c) \circ (u, v, w) \in I_{k}^{n} .$

The proof that $T_{d}^{n} < V_{d}^{n}$ is far more intricate. We shall step through the proof a lemma at a time. Throughout we assume that $1 \leq k < d .$

Lemma 1

i)	Any element of $T_{k}^{d}$ which is minimal with respect to the order $\leq$ is sub-minimal.
ii)	If $(u, v, w) \in T_{k}^{d}$ and $(u, v, w) \leq (u', v', w'),$ then $(u', v', w') \in T_{k}^{d} .$

Proof.

By induction, $T_{k}^{d} = V_{k}^{d};$ the result then follows from Theorems 3.10 and 3.11.

$□$

Lemma 2 $(u, v, w) \in T_{k}^{d} \Rightarrow (\tilde{u}, \tilde{v}, \tilde{w}) \in T_{d - k}^{d} .$

Proof.

Again, use induction and Theorem 4.11.

$□$

Lemma 3 $\begin{matrix} (a, b, c) \in I_{k}^{n} and (a', b', c') \in I_{k}^{n'} \\ \Rightarrow (a, b, c) \oplus (a', b', c') \in I_{k}^{n + n' - k} \end{matrix}$

Proof.

$\begin{array}{rcl} \sum (a, b, c) \oplus (a', b', c') & = & \sum (a, b, c) + \sum (a', b', c') - 3 \sum_{i = 1}^{k} i \\ \geq & 2 (n + 1) k - \frac{k (k + 1)}{2} + 2 (n' + 1) k - \frac{k (k + 1)}{2} - 3 \frac{k (k + 1)}{2} \\ = & 2 (n + n' + 2) k - 2 (k + 1) k - \frac{k (k + 1)}{2} \\ = & 2 (n + n' - k + 1) k - \frac{k (k + 1)}{2} . \end{array}$

$□$

Lemma 4 $\begin{matrix} (a, b, c) \in T_{d}^{n} and (u, v, w) \in T_{k}^{d} \\ \Rightarrow (a, b, c) * (u, v, w) \in I_{k}^{n - d + k} \end{matrix}$

Proof.

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

Since $(a, b, c) \circ (u, v, w) \in T_{k}^{n},$ we may compute that $\begin{array}{rcl} \sum (a, b, c) * (u, v, w) & = & \sum (a, b, c) \circ (u, v, w) - \sum (u, v, w) + 3 \sum_{i = 1}^{k} i \\ \geq & [2 (n + 1) k - \frac{k (k + 1)}{2}] - [2 (d + 1) k - \frac{k (k + 1)}{2}] + \frac{3 k (k + 1)}{2} \\ = & 2 (n - d) k + 2 k (k + 1) - \frac{k (k + 1)}{2} \\ = & 2 (n - d + k + 1) k - \frac{k (k + 1)}{2} . \end{array}$

$□$

Lemma 5 $\begin{matrix} (a, b, c) \in T_{d}^{n} and (u, v, w) \in T_{k}^{d} \\ \Rightarrow (a, b, c) * (u, v, w) \in T_{k}^{n - d + k} \end{matrix}$

Proof.

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

$□$

Lemma 6 $T_{d}^{n} = {(a, b, c) | \begin{array}{ll} 1) & a, b, c \in Q_{d, n}, \\ 2) & \sum (a, b, c) \geq 2 (n + 1) d - \frac{d (d + 1)}{2}, \\ 3) & If k < d and (u, v, w) \in T_{k}^{d}, \\ \sum (a, b, c) * (u, v, w) \in I_{k}^{n - d + k} \end{array}} .$

Proof.

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

$□$

Lemma 7 If $(a, b, c) \in T_{d}^{n},$ $(u, v, w) \in T_{k}^{d},$ and $(a, b, c) * (u, v, w)$ is sum-minimal, then $(a, b, c) * (\hat{u}, \hat{v}, \hat{w}) \in T_{d - k}^{n - k} .$

Proof.

This is a tough one. We begin by showing that $(a, b, c) * (\hat{u}, \hat{v}, \hat{w}) \in I_{d - k}^{n - k} :$ we have $\begin{array}{rcl} \sum (a, b, c) * (\hat{u}, \hat{v}, \hat{w}) & = & \sum (a, b, c) \circ (\hat{u}, \hat{v}, \hat{w}) - \sum (\hat{u}, \hat{v}, \hat{w}) + 3 \sum_{i = 1}^{d - k} i . \end{array}$ Apply Theorem 5.5(v): $\begin{array}{rcl} = & [\sum (a, b, c) - \sum (a, b, c) \circ (u, v, w)] - [\frac{3 d (d + 1)}{2} - \sum (u, v, w)] + \frac{3 (d - k) (d - k + 1)}{2} \\ = & \sum (a, b, c) - [\sum (a, b, c) * (u, v, w) - \frac{3 k (k + 1)}{2}] - \frac{3 d (d + 1)}{2} + \frac{3 (d - k) d - k + 1}{2} \end{array}$ Use the sum-minimality of $(a, b, c) * (u, v, w)$ and the fact that $(a, b, c) \in T_{d}^{n} :$ $\begin{array}{rcl} = & [2 (n + 1) d - \frac{d (d + 1)}{2} - [2 (n - d + k + 1) k - \frac{k (k + 1)}{2} - \frac{3 k (k + 1)}{2}] - \frac{3 d (d + 1)}{2} + \frac{3 (d - k) (d - k + 1)}{2}] \end{array}$ Simplify: $\begin{array}{rcl} = & 2 (n + 1) d - 2 (d + 1) d - 2 (n - d + k + 1) k + 2 k (k + 1) + \frac{3 (d - k) (d - k + 1)}{2} \\ = & 2 (n - d) d - 2 (n - d) k + \frac{3 (d - k) (d - k + 1)}{2} \\ = & 2 (n - d) (d - k) + 2 (d - k) (d - k + 1) - \frac{(d - k) (d - k + 1)}{2} \\ = & 2 (n - k + 1) (d - k) - \frac{(d - k) (d - k + 1)}{2} . \end{array}$ Now let $(x, y, z) \in T_{s}^{d - k},$ where $1 \leq s < d - k .$ We must show that $[(a, b, c) * (\hat{u}, \hat{v}, \hat{w})] \circ (x, y, z) \in I_{s}^{n - k} .$ First note that by Lemma 2, $(\tilde{u}, \tilde{v}, \tilde{w}) \in T_{d - k}^{d}$ and $(\tilde{x}, \tilde{y}, \tilde{z}) \in T_{d - k - s}^{d - k} .$ Hence $(\tilde{u}, \tilde{v}, \tilde{w}) \circ (\tilde{x}, \tilde{y}, \tilde{z}) \in T_{d - k - s}^{d}$ and $\tilde{(\tilde{u}, \tilde{v}, \tilde{w}) \circ (\tilde{x}, \tilde{y}, \tilde{z})} \in T_{d - k - s}^{d} .$ Let $(p, q, r) = \tilde{(\tilde{u}, \tilde{v}, \tilde{w}) \circ (\tilde{x}, \tilde{y}, \tilde{z})};$ by Theorem 5.5(ii), $(p, q, r) = \hat{(\hat{u}, \hat{v}, \hat{w}) \circ (\hat{x}, \hat{y}, \hat{z})};$ or $(\hat{p}, \hat{q}, \hat{r}) = (\hat{u}, \hat{v}, \hat{w}) \circ (\hat{x}, \hat{y}, \hat{z}) .$ Compute: $\begin{array}{rcl} \sum [(a, b, c) * (\hat{u}, \hat{v}, \hat{w})] \circ (x, y, z) & = & \sum (a, b, c) \circ (\hat{u}, \hat{v}, \hat{w}) \circ (x, y, z) - \sum (\hat{u}, \hat{v}, \hat{w}) \circ (x, y, z) + \sum (x, y, z) \end{array}$ Apply Theorem 5.5(v): $\begin{array}{rcl} = & [\sum (a, b, c) \circ (\hat{u}, \hat{v}, \hat{w}) - \sum (a, b, c) \circ (\hat{u}, \hat{v}, \hat{w}) \circ (\hat{x}, \hat{y}, \hat{z})] \\ - [\sum (\hat{u}, \hat{v}, \hat{w}) - \sum (\hat{u}, \hat{v}, \hat{w}) \circ (\hat{x}, y ˆ, z ˆ)] + \sum (x, y, z) \end{array}$ Substitute $(\hat{p}, \hat{q}, \hat{r}) :$ $\begin{array}{rcl} = & \sum (a, b, c) \circ (\hat{u}, \hat{v}, \hat{w}) - \sum (a, b, c) \circ (\hat{p}, \hat{q}, \hat{r}) - [\sum (\hat{u}, \hat{v}, \hat{w}) - \sum (\hat{p}, \hat{q}, \hat{r})] + \sum (x, y, z) \end{array}$ Apply Theorem 5.5(v): $\begin{array}{rcl} = & [\sum (a, b, c) - \sum (a, b, c) \circ (u, v, w)] - [\sum (a, b, c) - \sum (a, b, c) \circ (p, q, r)] \\ - [\frac{3 d (d + 1)}{2} - \sum (u, v, w)] + [\frac{3 d (d + 1)}{2} - \sum (p, q, r)] + \sum (x, y, z) \\ = & [\sum (a, b, c) \circ (p, q, r) - \sum (p, q, r)] - [\sum (a, b, c) \circ (u, v, w) - \sum (u, v, w)] + \sum (x, y, z) \\ = & [\sum (a, b, c) * (p, q, r) - \frac{3 (k + s) (k + s + 1)}{2}] - [\sum (a, b, c) * (u, v, w) - \frac{3 k (k + 1)}{2}] + \sum (x, y, z) \end{array}$ By assumption, $(a, b, c) * (u, v, w)$ is sum-minimal and $(a, b, c) * (p, q, r) \in T_{k + s}^{n - d + k + s} .$

Using this, we have $\begin{array}{rcl} \geq & [2 (n - d + k + s + 1) (k + s) - \frac{(k + s) (k + s + 1)}{2} - \frac{3 (k + s) (k + s + 1)}{2}] \\ - [2 (n - d + k + 1) k - \frac{k (k + 1)}{2} - \frac{3 k (k + 1)}{2}] + [2 (d - k + 1) s - \frac{s (s + 1)}{2}] \\ = & 2 (n - d + k + s + 1) (k + s) - 2 (k + s) (k + s + 1) \\ - 2 (n - d + k + 1) k + 2 k (k + 1) + 2 (d - k + 1) s - \frac{s (s + 1)}{2} \end{array}$ Fidget a little: $\begin{array}{rcl} = & 2 (n - d) (k + s) - 2 (n - d) k + 2 (d - k + 1) s - \frac{s (s + 1)}{2} \\ = & 2 (n - d) s + 2 (d - k + 1) s - \frac{s (s + 1)}{2} \\ = & 2 (n - k + 1) s - \frac{s (s + 1)}{2} . \end{array}$ DONE!

$□$

Lemma 8 Let $(u, v, w) \in T_{k}^{d}$ $(1 \leq k < d),$ and let $a, b, c \in Q_{d, n} .$ Set $\begin{array}{rcl} λ & = & θ_{d, n}^{- 1} (a), \\ μ & = & θ_{d, n}^{- 1} (b), \\ ν & = & θ_{d, n}^{- 1} (\overline{c}) . \end{array}$ Then $\sum_{i = 1}^{k} λ (μ_{i}) + μ (v_{i}) - ν ({\overline{w}}_{i}) = 2 (n - d + k + 1) k - \frac{k (k + 1)}{2} - \sum (a, b, c) * (u, v, w)$ and hence $(λ, μ, ν) \in T_{d} ⟺ (a, b, c) \in T_{d}^{n} .$

Proof.

Recall that if $x \in Q_{d, n},$ then ${\overline{x}}_{i} = n + 1 - x_{d + 1 - i}$ and ${[θ_{d, n}^{- 1} (x)]}_{i} = n - d + i - x_{i} .$ So $\begin{array}{rcl} {\overline{c}}_{i} & = & n + 1 - c_{d + 1 - i}, \\ {\overline{w}}_{i} & = & n d + 1 - w_{d k + 1 - i} \end{array}$ and $\begin{array}{rcl} ν_{{\overline{w}}_{i}} & = & {[θ_{d, n}^{- 1} (\overline{c})]}_{{\overline{w}}_{i}} \\ = & n - d + {\overline{w}}_{i} - {\overline{c}}_{{\overline{w}}_{i}} \\ = & n - d + (d + 1 - w_{k + 1 - i}) - (n + 1 - c_{d + 1 - {\overline{w}}_{i}}) \\ = & c_{d + 1 - {\overline{w}}_{i}} - w_{k + 1 - i} \\ = & c_{w_{k + 1 - i}} - w_{k + 1 - i} . \end{array}$ Compute: $\begin{array}{rcl} \sum_{i = 1}^{k} λ (μ_{i}) + μ (v_{i}) - ν ({\overline{w}}_{i}) & = & \sum_{i = 1}^{k} (n - d + u_{i} - a_{u_{i}}) + (n - d + v_{i} - b_{v_{i}}) - (c_{w_{k + 1 - i}} - w_{k + 1 - i}) \\ = & 2 (n - d) k + \sum_{i = 1}^{d} (u_{i} + v_{i} + w_{i}) - \sum_{i = 1}^{d} (a_{u_{i}} + b_{v_{i}} + c_{w_{i}}) \\ = & 2 (n - d) k - \sum (a, b, c) \circ (u, v, w) + \sum (u, v, w) \\ = & 2 (n - d) k - [\sum (a, b, c) * (u, v, w) - \frac{3 k (k + 1)}{2}] \\ = & 2 (n - d) k + \frac{3 k (k + 1)}{2} - \sum (a, b, c) * (u, v, w) \\ = & 2 (n - d) k + 2 k (k + 1) - \frac{k (k + 1)}{2} - \sum (a, b, c) * (u, v, w) \\ = & 2 (n - d + k + 1) k - \frac{k (k + 1)}{2} - \sum (a, b, c) * (u, v, w) . \end{array}$ This shows that $(λ, μ, ν) \circ (u, v, \overline{w}) \in I_{k} ⟺ (a, b, c) * (u, v, w) \in I_{k}^{n - d + k},$ and so $(λ, μ, ν) \in T_{d} ⟺ (a, b, c) \in T_{d}^{n} .$

$□$

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

Lemma 9 Let $(a, b, c) \in T_{d}^{n}$ and $(u, v, w) \in T_{k}^{d}$ $(1 \leq k < d) .$ If $(a, b, c) * (u, v, w)$ is sum-minimal, then $(a, b, c) \in V_{d}^{n} .$

Proof.

By Lemma 5 and induction, $(a, b, c) * (u, v, w) \in T_{k}^{n - d + k} = V_{k}^{n - d + k} .$ By Lemma 7 and induction, $(a, b, c) * (\hat{u}, \hat{v}, \hat{w}) \in T_{d - k}^{n - k} = V_{d - k}^{n - k} .$ By Theorem 4.11, $\tilde{(a, b, c) * (\hat{u}, \hat{v}, \hat{w})} \in V_{n - d}^{n - k},$ $\tilde{(a, b, c) * (u, v, w)} \in V_{n - d}^{n - d + k} .$ By Theorem 5.5(iv) and Theorem 4.18, $\tilde{(a, b, c) * (u, v, w)} \oplus \tilde{(a, b, c) * (\hat{u}, \hat{v}, \hat{w})} \in V_{n - d}^{n} .$ Hence by duality (Theorem 4.11), $(a, b, c) \in V_{d}^{n} .$

$□$

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

Lemma 10 If $(λ, μ, ν) \in T_{d}$ is an extreme ray of $T_{d}^{*}$ such that $\sum_{i = 1}^{d} λ_{i} + μ_{i} - ν_{i} = 0,$ then there exists a $(λ, μ, ν) -LRA.$

Proof.

Let $n = max (λ_{1}, μ_{1}, ν_{1}) - d + 1 .$ Set $\begin{array}{rcl} a & = & θ_{d, n} (λ), \\ b & = & θ_{d, n} (μ), \\ \overline{c} & = & θ_{d, n} (ν) . \end{array}$ If $(λ, μ, ν)$ is an extreme ray of $T_{d}^{*},$ then by Theorem 5.3 there exists $(u, v, w) \in T_{k}^{d}$ such that $\sum_{i = 1}^{k} λ_{u_{i}} + μ_{v_{i}} - ν_{{\overline{w}}_{i}} = 0 .$ Then Lemma $98$ implies that $(a, b, c) * (u, v, w)$ is sub-minimal, so $(a, b, c) \in V_{d}^{n}$ by Lemma 9, and hence the theorem holds by Theorem 4.17.

$□$

We can now prove that $T_{d}^{n} < V_{d}^{n} .$ Let $(a, b, c) \in T_{d}^{n} .$ From Theorem 2.11, we may assume that $(a, b, c)$ is minimal in $T_{d}^{n}$ with respect to the ordering $\leq .$ If there exists $k < d$ and $(u, v, w) \in T_{k}^{d}$ 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 $T_{d}^{n},$ contradicting the minimality of $(a, b, c) .$ Set $\begin{array}{rcl} λ & = & θ_{d, n}^{- 1} (a), \\ μ & = & θ_{d, n}^{- 1} (b), \\ ν & = & θ_{d, n}^{- 1} (\overline{c}) . \end{array}$ Regard $(λ, μ, ν)$ as an element of $T_{d}^{*} .$ By Theorem 5.4, we may write $(λ, μ, ν) = \sum_{j} r_{j} (λ^{j}, μ^{j}, ν^{j}),$ where each $(λ^{j}, μ^{j}, ν^{j})$ is an integral extreme ray of $T_{d}^{*}$ and each $r_{i} > 0 .$ From Lemma 8 and the sum-minimality of $(a, b, c),$ we must have $\sum_{i = 1}^{d} λ_{i} + μ_{i} - ν_{i} = 0 .$ Since each $r_{i} > 0,$ $\sum_{i = 1}^{k} λ_{i}^{j} + μ_{i}^{j} - ν_{i}^{j} = 0$ for each $j .$ Then by Lemma 10, there exists a $(λ^{j}, μ^{j}, ν^{j}) -LRA$ (which we will call $N^{j})$ for each $j .$ Write $\sum_{j} r_{j} \cdot (λ^{j}, μ^{j}, ν^{j}, N^{j}) = (λ, μ, ν, \sum r_{j} N^{j}) .$ By Theorem 4.12, $(λ, μ, ν, \sum r_{j} N^{j})$ is an LRD, and so by Theorem 4.1 $34$ there exists a $(λ, μ, ν) -LRA.$ Translating via Theorem 4.17, we have $(a, b, c) \in V_{d}^{n},$ 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