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

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: $\begin{array}{rcl} {}^{•}T_{1}^{n} & = & {(a, b, c) | \begin{array}{ll} 1) & a, b, c \in Q_{1, d n} \\ 2) & a + b \geq = c + 1 \end{array}}, \\ {}^{•}T_{d}^{n} & = & {(a, b, c) | \begin{array}{ll} 1) & a, b, c \in Q_{d, n}, \\ 2) & \sum_{i = 1}^{d} (a_{i} + b_{i}) \geq = \sum_{i = 1}^{d} c_{i} + \frac{d \cdot (d + 1)}{2}, \\ 3) & If (u, v, w) \in {}^{•}T_{d k}^{n d} (k < d), \\ \sum_{i = 1}^{d k} {(a \circ u)}_{i} + {(b \circ v)}_{i} \geq \leq \sum_{i = 1}^{d k} {(c \circ w)}_{i} + \frac{k \cdot (k + 1)}{2} \end{array}} . \end{array}$ Horn conjectured that ${}^{•}T_{d}^{n} < {}^{•}S_{d}^{n}$ for all $d$ and $n;$ 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};$ but further, that ${}^{•}S_{4}^{16} ≮ {}^{•}T_{4}^{16} .$ The following lemma was the key tool used.

(The "pushing" lemma for ${}^{•}S_{d}^{n})$ Let $(a, b, c) \in {}^{•}S_{d}^{n},$ and let $u, v, w,$ be three integers such that $1 \leq u \leq d + 1,$ $1 \leq v \leq d + 1,$ and $1 \leq w \leq d .$ Set $\begin{array}{rcl} a_{i}^{'} & = & a_{i} + δ_{u - 1} (i), \\ b_{i}^{'} & = & b_{i} + δ_{v - 1} (i), \\ c_{i}^{'} & = & c_{i} + δ_{w - 1} (i) . \end{array}$ If $a_{u} + b_{v} \geq c_{w - 1} + c_{d} + 2,$ then $(a', b', c') \in {}^{•}S_{d}^{n + 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) \in {}^{•}T_{d}^{n},$ there exists $(a', b', c') \in {}^{•}T_{d}^{n - 1}$ which can be "pushed" to $(a, b, c) .$ 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

$S_{d}^{n} = {(a, b, c) | \begin{array}{ll} 1) & a, b, c \in Q_{d, n}, \\ 2) & Given any three hermitian matrices A, B, C such that A + B + C = 0, \\ Σ_{a} (A) + Σ_{b} (B) + Σ_{c} (C) \leq 0 \end{array}} .$ There is a one-to-one correspondence between ${}^{•}S_{d}^{n}$ and $S_{d}^{n}$ given by $(\overline{a}, \overline{b}, c) \to (a, b, c) .$ That is, $(\overline{a}, \overline{b}, c) \in {}^{•}S_{d}^{n} iff (a, b, c) \in S_{d}^{n} .$ If the same correspondence is applied to ${}^{•}T_{d}^{n},$ one obtains

$\begin{array}{rcl} T_{1}^{n} & = & {(a, b, c) | a + b + c \geq = 2 n + 1}, \\ T_{d}^{n} & = & {(a, b, c) | \begin{array}{ll} 1) & a, b, c \in Q_{d, n}, \\ 2) & Σ (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}, \\ Σ (a, b, c) \circ (u, v, w) \geq 2 (d n + 1) k - \frac{k (k + 1)}{2} \end{array}} . \end{array}$ It can be shown that $(\overline{a}, \overline{b}, c) \in {}^{•}T_{d}^{n}$ iff $(a, b, c) \in T_{d}^{n} .$ Horn's conjecture is thus equivalent to the conjecture that $T_{d}^{n} < S_{d}^{n} .$

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

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

A tower is said to be of type $a$ if $a \in Q_{d, n}$ and $dim (A_{i}) = a_{i}$ for $i = 1, 2, \dots, d .$

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

$Ω (A) = {L | \begin{array}{ll} 1) & L is a subspace of dimension d in A^{n} (F), \\ 2) & dim (L \land A_{i}) \geq i for i = 1, 2, \dots, d \end{array}} .$ We call $Ω (A)$ a Schubert variety of type $a .$

$V_{d}^{n} (F) = {(a, b, c) | \begin{array}{ll} 1) & a, b, c < Q_{d, n}, \\ 2) & For any three (d, n, F) -towers A, B, C, of type a, b, c \\ Ω (A) \land Ω (B) \land Ω (C) \neq \emptyset \end{array}} .$ By convention, $V_{d}^{n} = V_{d}^{n} (ℂ),$ where $ℂ$ denotes the field of complex numbers.

(Hersch-Zwahlen) $V_{d}^{n} < S_{d}^{n}$

Thompson's result

Theorem 2.7 shows that Horn's conjecture would be true if $T_{d}^{n} < V_{d}^{n} .$ 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} .$ 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 $T_{3}^{n} < V_{3}^{n} (ℂ)$ for all $n,$ but that in general, $T_{3}^{n} ≮ V_{3}^{n} (?? maybe ℝ) .$ His approach started by establishing the following lemma.

(The "pushing" lemma for $V_{d}^{n})$ Let $(a, b, c) \in V_{d}^{n} (F),$ where $F$ is an arbitrary field. Let $u, v, w$ be three integers chosen from ${0, 1, 2, \dots, d} .$ Set $\begin{array}{rcl} a_{i}^{'} & = & a_{i} + δ_{u} (i), \\ b_{i}^{'} & = & b_{i} + δ_{v} (i), \\ c_{i}^{'} & = & c_{i} + δ_{w} (i), \\ a_{0} = b_{0} = c_{0} = 0 . \end{array}$ If $a_{u} + b_{v} + c_{w} \leq n,$ then $(a', b', c') \in V_{d}^{n + 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 $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} (F)$ 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} (ℂ)$ for all $n$ if $d \leq 4 .$ 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) \in V_{d}^{n}$ and $(u, v, w) \in V_{k}^{d} \Rightarrow (a, b, c) \circ (u, v, w) \in V_{k}^{n} .$

$(a, b, c) \in T_{d}^{n}$ and $(u, v, w) \in T_{k}^{d} \Rightarrow (a, b, c) \circ (u, v, w) \in T_{k}^{n} .$

Proof of 2.9.

Suppose $(a, b, c) \in V_{d}^{n}$ and $(u, v, w) \in V_{k}^{d} .$ Let $A, B, C$ be arbitrary $(k, n) -towers$ of type $a \circ u, b \circ v, c \circ w,$ respectively. Then there exist $(d, n) -towers$ $A', B', C',$ of type $a, b, c,$ respectively, such that $\begin{array}{rcl} A_{u (i)}^{'} & = & A_{i}, \\ B_{v (i)}^{'} & = & B_{i}, \\ C_{w (i)}^{'} & = & C_{i} . \end{array}$ By hypothesis, $Ω (A') \land Ω (B') \land Ω (C') \neq ?? maybe \emptyset .$ Hence there exists a $d -dimensional$ subspace $L'$ such that $\begin{array}{rcl} dim (L' \land A_{i}^{'}) \geq i, & i = 1, 2, \dots, d, \\ dim (L' \land B_{i}^{'}) \geq i, & i = 1, 2, \dots, d, \\ dim (L' \land C_{i}^{'}) \geq i, & i = 1, 2, \dots, d . \end{array}$ Define $(k, d) -towers$ $U', V', W',$ by $\begin{array}{rcl} U_{i}^{'} & = & L' \land A_{u (i)}^{'}, \\ V_{i}^{'} & = & L' \land B_{u (i)}^{'}, \\ W_{i}^{'} & = & L' \land C_{u (i)}^{'} . \end{array}$ Define sequences $u', v', w'$ in $Q_{k, d}$ by $\begin{array}{rcl} u_{i}^{'} & = & dim (U_{i}^{'}), \\ v_{i}^{'} & = & dim (V_{i}^{'}), \\ w_{i}^{'} & = & dim (W_{i}^{'}) . \end{array}$ Then $u = \leq u',$ $v = \leq v',$ and $w = \leq w',$ so there exist $(k, d) -towers$ $U, V, W,$ of type $u, v, w,$ respectively such that $U_{i} < \leq U_{i}^{'},$ $V_{i} < \leq V_{i}^{'},$ and $W_{i} < \leq W_{i}^{'}$ for $i = 1, 2, \dots, k .$ Since $(u, v, w) \in V_{k}^{d},$ there exists $k -dimensional$ subspace $L$ such that $L \in Ω (U) \land Ω (V) \land Ω (w) .$ In particular, $L < L' .$ Notice that for $i = 1, 2, \dots, k$ $\begin{array}{rcl} dim (L \land A_{i}) & = & dim (L \land A_{u (i)}^{'}) \\ = & dim (L \land L' \land A_{u (i)}^{'}) \\ = & dim (L \land U_{i}^{'}) \\ \geq & dim (L \land U_{i}) \\ \geq & i . \end{array}$ Hence $L \in Ω (A) .$ Similarly, $L \in Ω (B)$ and $L \in Ω (C) .$ Since $A, B, C$ are arbitrary $(k, n) -towers$ of type $a \circ u,$ $b \circ v,$ and $c \circ w,$ the proof is complete.

$□$

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

Proof of 2.10.

We introduce notation for use in this and subsequent proofs. Let $I_{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} \end{array}} .$ Then $T_{d}^{n} = {(a, b, c) | \begin{array}{ll} 1) & (a, b, c) \in I_{d}^{n}, \\ 2) & For k < d and (u, v, w) \in T_{k}^{d}, \\ (a, b, c) \circ (u, v, w) \in I_{k}^{n} \end{array}} .$ The proof of 2.10 is by induction on $d .$ The result is trivial for $d = 1 .$ Assume the result holds for $1, 2, \dots, d - 1$ and let $(a, b, c) \in T_{d}^{n}$ and $(u, v, w) \in T_{k}^{d} .$ Then by definition, $(a, b, c) \circ (u, v, w) \in I_{k}^{n} .$ Let $(x, y, z) \in T_{s}^{k} .$ We must show $\begin{matrix} [(a, b, c) \circ (u, v, w)] \circ (x, y, z) \in I_{s}^{n} . & (*) \end{matrix}$ But $[(a, b, c) \circ (u, v, w)] \circ (x, y, z) = (a, b, c) \circ [(u, v, w) \circ (x, y, z)] .$ By induction, $(u, v, w) \circ (x, y, z) \in T_{s}^{d}$ 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) \in V_{d}^{n} \Rightarrow (a', b', c') \in V_{d}^{n} .$

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