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

The Symmetric Algebra and Schur Functions

The formulae and rules making up the Schubert Calculus appear in numerous other setting, many of which provide additional computational rules. These other settings include:

1)	Representation theory of the symmetric group;
2)	Representation theory of the full linear group;
3)	Multiplication of Schur functions in the algebra of symmetric polynomials.

In this section we consider topic 3), show the relationships between it and the Schubert calculus, and derive some new results which give another characterization of the set $V_d^n\text{.}$

Partitions, Young Diagrams

By a partition we mean a sequence of integers $$\lambda =({\lambda }_1,{\lambda }_2,\dots )$$ satisfying $${\lambda }_1\ge {\lambda }_2\ge \dots \ge 0\text{.}$$ We say $\lambda$ is a partition of $w,$ or has weight $w,$ if $$\sum _{i=1}^{\infty }{\lambda }_i=w\text{.}$$ The length of $\lambda$ is the number of nonzero integers among ${\lambda }_1,{\lambda }_2,\dots \text{.}$ If $\lambda$ has length $r,$ we write $$\lambda =({\lambda }_1,{\lambda }_2,\dots ,{\lambda }_r)\text{.}$$ We let $\mathrm{\Pi }$ denote the set of all partitions, and ${\mathrm{\Pi }}_d$ the set of partitions of length at most $d\text{.}$ The set $\mathrm{\Pi }$ may be given a partial ordering $\le ,$ defined as follows: $$\mu \le \lambda ⟺{\mu }_i\le {\lambda }_i\hspace{0.17em}\text{for}\hspace{0.17em}i=1,2,3,\dots \text{.}$$

The diagram $Y\left(\lambda \right)$ associated with a partition $\lambda$ is a left-justified array of squares with ${\lambda }_i$ squares in the $i^{\text{th}}$ row.

Example: $$\lambda =(4,2,1)$$ $$Y\left(\lambda \right)=\begin{array}{c} \end{array}$$ If $\mu$ and $\lambda$ are partitions with $\mu \le \lambda ,$ then the skew-diagram $Y\left(\frac{\lambda }{\mu }\right)$ is obtained by removing $Y\left(\mu \right)$ from $Y\left(\lambda \right)\text{.}$ For example, if $\lambda =(5,4,3,1,1)$ and $\mu =(4,3,1,1,0)$ then $Y\left(\frac{\lambda }{\mu }\right)$ looks like $$\begin{array}{c} \end{array}$$

Lastly, the partition dual to $\lambda ,$ denoted by $\stackrel{\sim }{\lambda },$ is the partition whose diagram is obtained from $Y\left(\lambda \right)$ by interchanging rows and columns. The "jump" function ${\delta }_X$ can be used to express the components of $\stackrel{\sim }{\lambda }$ in terms of the components of $\lambda \text{:}$ $${\stackrel{\sim }{\lambda }}_j=\sum _{i=1}^{\infty }{\delta }_{{\lambda }_i}\left(j\right)\text{.}$$

Symmetric functions

Let $A$ denote the ring of symmetric polynomials (also called symmetric functions) in an infinite number of variables $x_1,x_2,\dots$ with integer coefficients (properly called symmetric formal power series). We review some basis results about this ring (see [Sta1976] and [Lid1950]).

1)	Let $$a_r=\sum _{\sigma \in Q_{r,\infty }}\prod _{i=1}^r{x}_{\sigma \left(i\right)}\text{;}$$ $a_r$ is called the $r^{\text{th}}$ elementary symmetric function. The "fundamental theorem of symmetric functions" states that the elementary symmetric functions are algebraically independent and that $A=Z[a_1,a_2,\dots ],$ i.e. every symmetric function in $A$ may be expressed uniquely as a polynomial in $a_1,a_2,\dots$ with integer coefficients.
2)	Let $G_{r,\infty }$ denote the set of all non-decreasing sequences of $r$ integers chosen from $1,2,\dots \text{.}$ Define $$h_r=\sum _{\sigma \in G_{r,\infty }}\prod _{i=1}^r{x}_{\sigma \left(i\right)}\text{;}$$ $h_r$ is called the $r^{\text{th}}$ complete homogeneous product. It is the sum of all monomials in $A$ of degree $r\text{.}$
3)	Let $$S_r=\sum _{i=1}^{\infty }{x}_i^r\text{;}$$ $S_r$ is called the $r^{\text{th}}$ power symmetric function. By convention, $a_0=h_0=S_0=1,$ and $a_r=h_r=S_r=0$ for $r<0\text{.}$

The $a_r$ and $S_r$ are connected by the classical

Newton's identities:

$$\begin{array}{rcl}{\displaystyle S_1-a_1}& =& {\displaystyle 0,}\\ {\displaystyle S_2-S_1{a}_1+2a_2}& =& {\displaystyle 0,}\\ {\displaystyle S_3-S_2{a}_1+S_1{a}_2-3a_3}& =& {\displaystyle 0,}\\ {\displaystyle }& ⋮& {\displaystyle }\\ {\displaystyle S_N-S_{N-1}{a}_1+\cdots +{(-1)}^{N}N{a}_N}& =& {\displaystyle 0,}\\ {\displaystyle }& ⋮& {\displaystyle }\end{array}$$

If one solves for the $a_r\text{'s}$ in terms of the $S_r\text{'s,}$ one obtains $$r!·a_r=\text{det}\left(Z_r\right),$$ where $$\begin{array}{cc}{Z}_r=\left(\begin{array}{ccccccccc}{S}_1& 1& 0& 0& \cdots & \phantom{0}& \phantom{0}& \phantom{0}& 0\\ S_2& S_1& 2& 0& \cdots & \phantom{0}& \phantom{0}& \phantom{0}& 0\\ S_3& S_2& S_1& 3& 0& \cdots & \phantom{0}& \phantom{0}& 0\\ ⋮& & & & & & & & ⋮\\ & & & & & & & & r-1\\ S_r& S_{r-1}& & & & & & & S_1\end{array}\right)& \text{(*)}\end{array}$$ The $S_r\text{'s}$ may be expressed in a similar fashion in terms of the $a_r\text{'s;}$ hence the power sums $S_1,S_2,\dots$ are also algebraically independent and $A=Z[S_1,S_2,\dots ]\text{.}$

The following relations (due to Brioschi) connect the $S_r\text{'s}$ and the $h_r\text{'s:}$ $$\begin{array}{rcl}{\displaystyle S_1-h_1}& =& {\displaystyle 0,}\\ {\displaystyle S_2+S_1{h}_1-h_2}& =& {\displaystyle 0,}\\ {\displaystyle S_3+S_2{h}_1+S_1{h}_2-h_3}& =& {\displaystyle 0,}\\ {\displaystyle }& ⋮& {\displaystyle }\\ {\displaystyle S_N+S_{N-1}{h}_1+\cdots -h_N}& =& {\displaystyle 0,}\\ {\displaystyle }& ⋮& {\displaystyle }\end{array}$$

If one solves for the $h_r\text{'s}$ in terms of the $S_r\text{'s,}$ one obtains $$\begin{array}{rclr}r!·h_r& =& \text{det}\mid \begin{array}{ccccccccc}{S}_1& -1& 0& 0& \cdots & \phantom{0}& \phantom{0}& \phantom{0}& 0\\ S_2& S_1& -2& 0& \cdots & \phantom{0}& \phantom{0}& \phantom{0}& 0\\ S_3& S_2& S_1& -3& 0& \cdots & \phantom{0}& \phantom{0}& 0\\ ⋮& & & & & & & & ⋮\\ & & & & & & & & -r+1\\ S_r& S_{r-1}& & & & & & & S_1\end{array}\mid & \text{(**)}\\ & =& {\displaystyle \text{permanent}\hspace{0.17em}\left(Z_r\right)\text{.}}\end{array}$$ Again, the complete homogeneous product sums are algebraically independent, and $A=Z[h_1,h_2,\dots ]\text{.}$

Another class of symmetric functions, the Schur symmetric functions, is also of particular interest. Let $\lambda$ be a partition. The Schur symmetric function $e_{\lambda }$ may be defined in numerous ways. We give the definition originally used by Schur. Let $S_r$ denote the symmetric group on $r$ symbols, and let $k^{\left(\lambda \right)}$ be the character of $S_r$ corresponding to $\lambda ,$ as given in Young diagram theory. The $\lambda \text{-immanent}$ of an $r\text{-by-}r$ matrix $A=\left(A_{ij}\right),$ denoted by ${\mid A\mid }^{\left(\lambda \right)},$ is defined as follows: $${\mid A\mid }^{\left(\lambda \right)}=\sum _{\sigma \in S_r}{k}^{\left(\lambda \right)}\left(\sigma \right)·\prod _{i=1}^r{A}_{i,\sigma \left(i\right)}\text{.}$$ The Schur function $e_{\lambda }$ is then defined by $$r!·e_{\lambda }={\mid Z_r\mid }^{\left(\lambda \right)},$$ where $Z_r$ is the matrix of power sums defined previously. We immediately note two special cases:

1)	If $\lambda =(1,1,1,\dots ,1)$ has weight $r,$ then ${\mid A\mid }^{\left(\lambda \right)}=\text{det}\left(A\right),$ so $e_{(1,1,1,\dots ,1)}=\text{det}\left(Z_r\right)/r!=a_r\text{.}$
2)	If $\lambda =(r,0,0,\dots ,0),$ then ${\mid A\mid }^{\left(\lambda \right)}=\text{per}\left(A\right),$ so $e_{(r,0,0,\dots ,0)}=\text{per}\left(Z_r\right)/r!=h_r\text{.}$

We list some classical theorems concerning Schur functions.

The set $\left\{e_{\lambda }\hspace{0.17em}\right|\hspace{0.17em}\lambda \in \mathrm{\Pi }\}$ forms a $Z\text{-basis}$ for the $Z\text{-module}$ $A\text{.}$

(Jacobi-Trudi) If $\lambda$ is a partition of length $r,$ then $$e_{\lambda }=\text{det}\left(H_{ij}\right),$$ where $H_{ij}$ is the $r\text{-by-}r$ matrix given by $$H_{ij}=h_{{\lambda }_i-i+j}\text{.}$$

(Naegelsbach, Aitken) If $\lambda$ is a partition of length $r,$ then $$e_{\lambda }=\text{det}\left(A_{ij}\right),$$ where $A_{ij}$ is the $r\text{-by-}r$ matrix given by $$A_{ij}=a_{{\stackrel{\sim }{\lambda }}_i-i+j},$$ and $\stackrel{\sim }{\lambda }$ is the dual of $\lambda \text{.}$

As the reader might infer, identities 4.2 and 4.3 were proved for a definition of Schur functions other than that given by Schur. Classically, these results were obtained in the ring $A_N$ of symmetric polynomials in $N$ variables $x_1,x_2,\dots ,x_N\text{.}$ In the ring $A_N,$ definitions exist for the elementary symmetric functions, complete homogeneous symmetric functions, power sums, and Schur functions which are analogous to the definitions of $a_r,h_r,S_r,$ and $e_{\lambda }$ in the ring $A\text{.}$ We will use the symbols $a_r,h_r,S_r,$ and $e_{\lambda }$ to denote elements of $A_N$ as well as $A\text{.}$

In the ring $A_N,$ another definition of $e_{\lambda }$ is possible (and in fact was the one used in the classical proofs of 4.2 and 4.3). Let $\lambda$ be a partition of length at most $N,$ and define $${\mathrm{\Delta }}_{\lambda }=\text{det}\left(X_{ij}\right),$$ where $$X_{ij}=x_j^{{\lambda }_i+N-i}\text{.}$$ We then have

(Jacobi) $$e_{\lambda }=\frac{{\mathrm{\Delta }}_{\lambda }}{\mathrm{\Delta }(0,0,\dots ,0)}$$

The quotients $\frac{{\mathrm{\Delta }}_{\lambda }}{\mathrm{\Delta }(0,0,\dots ,0)}$ are referred to by Muir as bi-alternants.

Identity 4.4 holds in the ring $A_N$ but has no meaning for $A\text{.}$ Identities 4.2 and 4.3 hold in $A_N$ as well as $A\text{.}$ Statement 4.1 holds as stated for $A\text{;}$ but in $A_N,$ $e_{\lambda }=0$ if $\lambda$ has length more than $N\text{.}$ However, the set $\left\{e_{\lambda }\hspace{0.17em}\right|\hspace{0.17em}\text{weight}\hspace{0.17em}\lambda \le N\}$ is a basis for $A_N\text{.}$

The mapping $h_r\to a_r$ extends to a ring automorphism $D$ of $A$ for which $D\left(e_{\lambda }\right)=e_{\stackrel{\sim }{\lambda }}\text{.}$

		Proof.
	Since $$A\cong Z[h_1,h_2,\dots ]\cong Z[a_1,a_2,\dots ],$$ any bijection from $\{h_1,h_2,\dots \}$ to $\{a_1,a_2,\dots \}$ extends to an automorphism of $A\text{.}$ From identities 4.2 and 4.3, $$\begin{array}{rcl}{\displaystyle D\left(e_{\lambda }\right)}& =& {\displaystyle D\left(\text{det}\left(h_{{\lambda }_i-i+j}\right)\right)}\\ & =& {\displaystyle \text{det}\left(D\left(h_{{\lambda }_i-i+j}\right)\right)}\\ & =& {\displaystyle \text{det}\left(a_{{\lambda }_i-i+j}\right)}\\ & =& {\displaystyle e_{\stackrel{\sim }{\lambda }}\text{.}}\end{array}$$ $\square$

The Littlewood-Richardson Rule

The Schur functions constitute a $Z\text{-basis}$ for $A\text{;}$ hence any product $e_{\lambda }·e_{\mu }$ may be expressed as a sum $$\sum _{\nu \in \mathrm{\Pi }}{c}_{\lambda \mu \nu }·e_{\nu }\text{.}$$ There is a certain well-studied rule for determining the integers $c_{\lambda ,\mu ,\nu }\text{.}$ Before describing the rule, we make a definition.

Let the sequence consisting of ${\mu }_1$ $1\text{'s,}$ ${\mu }_2$ $2\text{'s,}$ $\dots ,$ ${\mu }_k$ $k\text{'s,}$ $\dots$ be denoted by $$(1^{{\mu }_1},2^{{\mu }_2},\dots ,k^{{\mu }_k})\text{.}$$ Suppose $({\alpha }_1,{\alpha }_2,\dots )$ is a rearrangement of the sequence $(1^{{\mu }_1},2^{{\mu }_2},\dots )$ such that for any pair of indices $i,i+1$ the number of $i\text{'s}$ appearing among ${\alpha }_1,{\alpha }_2,\dots ,{\alpha }_j$ is not less than the number of $(i+1)\text{'s}$ appearing among ${\alpha }_1,{\alpha }_2,\dots ,{\alpha }_j\text{.}$ Then $({\alpha }_1,{\alpha }_2,\dots )$ is called a lattice permutation of $(1^{{\mu }_1},2^{{\mu }_2},\dots )\text{.}$

Example: $(1,2,3,1,4,2)$ is a lattice permutation of $(1^2,2^2,3,4),$ but $(1,2,3,2,1,4)$ is not.

(The Littlewood-Richardson (LR) rule) Let $\lambda ,\mu ,$ and $\nu$ be partitions. The coefficient of $e_{\nu }$ in the product $e_{\lambda }·e_{\mu }$ is equal to zero unless $\lambda \le \nu \text{.}$ If $\lambda \le \nu ,$ it is equal to the number of ways of filling the squares of the skew-diagram $Y\left(\frac{\nu }{\lambda }\right)$ if ${\mu }_1$ $1\text{'s,}$ ${\mu }_2$ $\text{'s,}$ $\dots$ subject to the following two conditions:

LR1:	The inserted numbers are non-decreasing in each row and strictly increasing in each column.
LR2:	The sequence $({\alpha }_1,{\alpha }_2,\dots )$ obtained by reading from right to left across the first row, next right to left across the second row, etc., must be a lattice permutation of $(1^{{\mu }_1},2^{{\mu }_2},\dots )\text{.}$

Example: Using the LR rule, one can compute that $$e_{(2,1)}·e_{(2,1)}=2e_{(3,2,1)}+e_{(4,2)}+e_{(2,2,1,1)}+e_{(3,3)}\text{.}$$

The LR rule was first stated in 1934 by D. E. Littlewood and A. R. Richardson ([Ll-R (Not included in Bibliography)]). The first proof is attributed to G. de B. Robinson in 1938, but that presentation is difficult to follow. Littlewood has offered proofs in [L1 (Not included in Bibliography)] and [L2 (Not included in Bibliography)] which seem nearly correct, but McConnell [McC1975] has pointed out problems in those efforts. Schutzenberger [Sch1976] has developed elegant (but non-elementary) combinatorial machinery which yields the LR rule as a corollary of a more general result. G. D. James has recently obtained the LR rule as a generalization of a well known result in the representation theory of the symmetric group [Jam1973]. The methods to be developed later in this section can be used to "fix" Littlewood's original argument and provide a fairly simple proof of the LR rule.

As a consequence of 4.7, we have the following

Let $\lambda =({\lambda }_1,{\lambda }_2,\dots ,{\lambda }_k)$ be a partition of weight $N\text{.}$ Then $$e_{\lambda }·h_r=\sum _{\nu }{e}_{\nu },$$ where $\nu$ ranges over all partitions of weight $N+r$ and length at most $k+1$ which satisfy $$\begin{array}{cc}{\nu }_1\ge {\lambda }_1\ge {\nu }_2\ge {\lambda }_2\ge \cdots \ge {\nu }_k\ge {\lambda }_k\ge {\nu }_{k+1},& \text{(*)}\end{array}$$ i.e. $\lambda$ must interlace $\nu \text{.}$

		Proof.
	Recall that $h_r=e_{(r,0,\dots ,0)}\text{.}$ By the LR rule, $$e_{\lambda }·h_r=\sum c_{\nu }{e}_{\nu },$$ where $c_{\nu }$ equals the number of ways of inserting $r$ $1\text{'s}$ into the skew diagram $Y\left(\frac{\nu }{\lambda }\right),$ subject to the LR conditions. We must show that $c_{\nu }=1$ if $\nu$ is of the form (*) and zero otherwise. i) If $\lambda \nleqq \nu$ or $\text{weight}\left(\nu \right)\ne N+r,$ then $c_{\nu }=0$ is automatic. ii) If the skew diagram $Y\left(\frac{\nu }{\lambda }\right)$ has more than one square in any column, then any placement of $r$ 1's into $Y\left(\frac{\nu }{\lambda }\right)$ must violate condition LR1. This is the case if $\nu$ has length greater than $k+1$ or if $\lambda$ does interlace $\nu \text{;}$ hence in these cases, $c_{\nu }=0\text{.}$ iii) If cases i) and ii) are excluded, then $\lambda \le \nu ,$ $\text{weight}\left(\nu \right)=N+r$ and $\lambda$ interlaces $\nu \text{.}$ Then the obvious (and only) placement of $r$ 1's into $Y\left(\frac{\nu }{\lambda }\right)$ satisfies LR1 because all columns have one square only and this placement satisfies LR2 because only one symbol ("1") is involved. Hence $c_{\nu }=1\text{.}$ $\square$

We are ready to present a theorem which connects the multiplication of Schubert cycles in $A\left(G_{d,n}\right)$ with the multiplication of Schur functions in $A\text{.}$ The connection is made with the help of a certain ideal in $A\text{.}$ Given $1\le d<n,$ let $p$ be the partition of $(n-d)d$ with $d$ parts equal to $n-d,$ and let $I_{dn}$ be the $Z\text{-submodule}$ of $A$ generated by all $e_{\mu }$ for which $\mu \nleqq p\text{.}$ In other words, either ${\mu }_1>n-d$ or $\mu$ has more than $d$ parts. It is easy to verify using the LR rule that $I_{dn}$ is an ideal in $A\text{.}$ The quotient $A/I_{dn}$ is generated freely as a $Z\text{-module,}$ with basis $\left\{e_{\lambda }\hspace{0.17em}\right|\hspace{0.17em}\lambda \le p\}\text{.}$ Products in $A/I_{dn}$ may be computed using the LR rule and ignoring terms involving those $e_{\mu }$ in $I_{dn}\text{.}$ The reader may now anticipate that $A\left(G_{d,n}\right)$ and $A/I_{dn}$ are isomorphic. We can describe an isomorphism using the map $${\theta }_{d,n}:\mathrm{\Pi }⟶Q_{d,n}$$ defined by $${\theta }_{d,n}\left(\lambda \right)=\{\begin{array}{ll}\varnothing ,& \text{if}\hspace{0.17em}\lambda \nleqq p,\\ n-d+1-{\lambda }_1,n-d+2-{\lambda }_2,\dots ,n-{\lambda }_d,& \text{otherwise.}\end{array}$$ We note that in this instance $\varnothing$ refers to the empty sequence belonging to $Q_{d,n}\text{.}$ By convention, we shorten ${\theta }_{d,n}$ to $\theta$ where no ambiguity exists.

The rings $A/I_{dn}$ and $A\left(G_{d,n}\right)$ are isomorphic. An isomorphism is given by $$e_{\lambda }+I_{dn}⟶\mathrm{\Omega }\left(\theta \left(\lambda \right)\right)$$ and linear extension.

		Proof.
	Let $T$ be the map from $A$ to $A\left(G_{d,n}\right)$ defined by $T\left(e_{\lambda }\right)=\mathrm{\Omega }\left(\theta \left(\lambda \right)\right)$ and linear extension. We need only show that $T$ is a ring homomorphism onto $A\left(G_{d,n}\right)$ with kernel $I_{dn}\text{.}$ Since $\theta$ is a map onto $Q_{d,n},$ $T$ maps onto $A\left(G_{d,n}\right)\text{.}$ It is easy to see that the kernel of $T$ is $I_{dn}\text{.}$ Since the special Schur functions $h_1,h_2,\dots$ freely generated $A$ as a ring, $T$ is multiplicative if for each pair $i,j$ $$T(h_i·h_j)=T\left(h_i\right)·T\left(h_j\right)\text{.}$$ Let $${\mathrm{\Pi }}_{ij}=\{\nu \in \mathrm{\Pi }\hspace{0.17em}|\hspace{0.17em}\begin{array}{ll}\text{1)}& \text{length}\left(\nu \right)=2,\\ \text{2)}& {\nu }_1\ge i\ge {\nu }_2,\\ \text{3)}& \text{weight}\left(\nu \right)=i+j\end{array}\}\text{.}$$ We have $$\begin{array}{rcl}{\displaystyle T(h_i·h_j)}& =& {\displaystyle T\left(\sum _{\nu \in {\mathrm{\Pi }}_{ij}}{e}_{\nu }\right)}\\ & =& {\displaystyle \sum _{\nu \in {\mathrm{\Pi }}_{ij}}\mathrm{\Omega }\left(\theta \left(\nu \right)\right)}\\ & =& {\displaystyle \sum _{a\in \theta \left({\mathrm{\Pi }}_{ij}\right)}\mathrm{\Omega }\left(a\right)}\\ & =& {\displaystyle \sigma \left(i\right)·\sigma \left(j\right)}\\ & =& {\displaystyle T\left(h_i\right)·T\left(h_j\right)\text{.}}\end{array}$$ $\square$

The connection described in Theorem 4.9 was first noticed by Lesieur [Le (Not included in Bibliography)] in 1947.

The rings $A\left(G_{d,n}\right)$ and $A\left(G_{n-d,n}\right)$ are isomorphic. An isomorphism is given by $\mathrm{\Omega }\left(a\right)\to \mathrm{\Omega }\left(\stackrel{\sim }{a}\right)$ and linear extension.

		Proof.
	This follows from Theorem 4.5 and the fact that $\stackrel{\sim }{\theta \left(\lambda \right)}=\theta \left(\stackrel{\sim }{\lambda }\right)\text{.}$ $\square$

(Duality for $V_d^n\text{)}$ $$(a,b,c)\in V_d^n\cong (\stackrel{\sim }{a},\stackrel{\sim }{b},\stackrel{\sim }{c})\in V_{n-d}^n$$

		Proof.
	This follows from Theorems 4.10 and 3.9. $\square$

Array formulation of the LR Rule

The Littlewood-Richardson rule, as originally states, requires deft combinatorial reasoning in applications. In this section we present a new formulation of the LR rule which facilitates a more geometrical type of argument.

Let $$e_{\lambda }·e_{\mu }=\sum c_{\lambda \mu \nu }{e}_{\nu }$$ and set $$d=\text{max}(\text{length}\left(\lambda \right),\text{length}\left(\mu \right),\text{length}\left(\nu \right))\text{.}$$ Then $c_{\lambda ,\mu ,\nu }$ equals the number of $d\text{-by-}d$ integer matrices $\left[n_{ij}\right]$ satisfying the following system of linear inequalities:

LRA1:	$n_{ij}\ge 0$ for $1\le i,j\le d\text{.}$
LRA2:	${\displaystyle \sum _{i=1}^d{n}_{ij}}={\mu }_i,$ $i=1,2,\dots ,d\text{.}$
LRA3:	${\displaystyle \sum _{i=1}^d{n}_{ij}}={\nu }_j-{\lambda }_j,$ $j=1,2,\dots ,d\text{.}$
LRA4:	${\lambda }_j+{\displaystyle \sum _{i=1}^t{n}_{ij}}\ge {\lambda }_{j+1}+{\displaystyle \sum _{i=1}^{t+1}{n}_{i,j+1},}$ $1\le i\le d-1,$ $0\le t\le d-1\text{.}$
LRA5:	${\displaystyle \sum _{j=1}^t{n}_{ij}}\ge {\displaystyle \sum _{j=1}^{t+1}{n}_{i+1,j},}$ $1\le i\le d-1,$ $0\le t\le d-1\text{.}$

$$\begin{array}{ccc}& \begin{array}{cccccc}{\lambda }_{1\phantom{1}}& {\lambda }_{2\phantom{2}}& \phantom{{\lambda }_{22}}& \cdots & \phantom{{\lambda }_{22}}& {\lambda }_{d\phantom{d}}\end{array}& \\ \begin{array}{c}0\\ 0\\ 0\\ ⋮\\ ⋮\\ 0\end{array}& \begin{array}{|cccccc|}\hline n_{11}& \phantom{n_{11}}& \phantom{n_{11}}& \phantom{n_{11}}& \phantom{n_{11}}& \phantom{n_{11}}\\ \phantom{n_{11}}& \ddots & \phantom{n_{11}}& \phantom{n_{11}}& n_{ij}& \phantom{n_{11}}\\ \phantom{n_{11}}& \phantom{n_{11}}& n_{ii}& \phantom{n_{11}}& \phantom{n_{11}}& \phantom{n_{11}}\\ \phantom{n_{11}}& \phantom{n_{11}}& \phantom{n_{11}}& \ddots & \phantom{n_{11}}& \phantom{n_{11}}\\ \phantom{n_{11}}& \phantom{n_{11}}& \phantom{n_{11}}& \phantom{n_{11}}& \ddots & \phantom{n_{11}}\\ \phantom{n_{11}}& 0& \phantom{n_{11}}& \phantom{n_{11}}& \phantom{n_{11}}& n_{dd}\\ \hline\end{array}& \begin{array}{c}{\mu }_1\\ {\mu }_2\\ ⋮\\ ⋮\\ ⋮\\ {\mu }_d\end{array}\\ & \begin{array}{cccccc}{\nu }_{1\phantom{1}}& {\nu }_{2\phantom{2}}& \phantom{{\nu }_{22}}& \cdots & \phantom{{\nu }_{22}}& {\nu }_{d\phantom{d}}\end{array}& \end{array}$$

		Proof.
	First we dispose of the case $\lambda \nleqq \nu \text{.}$ By the LR rule, $c_{\lambda \mu \nu }=0\text{;}$ this agrees with the theorem, since there are no integer matrices which could satisfy LRA1 and LRA3. Next suppose $\text{weight}\left(\lambda \right)+\text{weight}\left(\mu \right)\ne \text{weight}\left(\nu \right)\text{.}$ By the LR rule, $c_{\lambda \mu \nu }=0\text{;}$ this agrees with the theorem, since there are no matrices satisfying conditions LRA2 and LRA3 for which $\text{weight}\left(\lambda \right)+\text{weight}\left(\mu \right)\ne \text{weight}\left(\nu \right)\text{.}$ Now suppose $\lambda \le \nu$ and $\text{weight}\left(\lambda \right)+\text{weight}\left(\mu \right)=\text{weight}\left(\nu \right)\text{.}$ The theorem will be verified if we can establish a one-to-one correspondence between the ways of filling the squares of $Y\left(\frac{\nu }{\lambda }\right)$ with ${\mu }_1$ 1's, ${\mu }_2$ 2's, $\dots$ which conform to the LR restrictions, and the integer matrices $\left[n_{ij}\right]$ satisfying LRA1 through LRA5. The following is such a correspondence. Given a way of filling $Y\left(\frac{\nu }{\lambda }\right),$ let $$n_{ij}=\text{the number of symbols '}i\text{' placed in row}\hspace{0.17em}j\hspace{0.17em}\text{of}\hspace{0.17em}Y\left(\frac{\nu }{\lambda }\right)\text{.}$$ Clearly this defines a one-to-one correspondence between the set of ways of filling $Y\left(\frac{\nu }{\lambda }\right)$ and the set of integer arrays satisfying LRA1, LRA2, and LRA3. It remains to show that if an arbitrary way of filling $Y\left(\frac{\nu }{\lambda }\right)$ satisfies the two LR conditions, then the corresponding array satisfies LRA4 and LRA5, and conversely. Suppose that $\left[n_{ij}\right]$ corresponds to a way of filling $Y\left(\frac{\nu }{\lambda }\right)$ which satisfies LR1 and LR2. Then $\left[n_{ij}\right]$ must satisfy LRA4 and LRA5, as the following two arguments show. 1) Suppose that LRA4 fails to hold for $\left[n_{ij}\right]\text{.}$ Then there is some $j_0$ that $${\lambda }_{j_0}+\sum _{i=1}^{t_0}{n}_{i{j}_0}<{\lambda }_{j_0+1}+\sum _{i=1}^{t_0+1}{n}_{i{j}_0+1}$$ for some $t_0\text{.}$ We assume that $j_0$ is the minimal such index, and that $t_0$ is the smallest is the smallest possible index corresponding to $j_0\text{.}$ Let $$k_1={\lambda }_{j_0}+\sum _{i=1}^{t_0}{n}_{i{j}_0}$$ and $$k_2={\lambda }_{j_0+1}+\sum _{i=1}^{t_0+1}{n}_{i{j}_0+1}\text{.}$$ By assumption, $k_1<k_2\text{.}$ Now in row $j_0$ of $Y\left(\frac{\nu }{\lambda }\right),$ the placement of 1's, 2's, $\dots ,$ $t_0\text{'s}$ extends out to column $k_1$ at most; hence the square in row $j_0,$ column $k_2$ of $Y\left(\frac{\nu }{\lambda }\right)$ contains a symbol greater than or equal to $t_0+1\text{.}$ However, the square in row $j_0+1,$ column $k_2$ contains precisely the symbol $t_0+1$ (because $n_{t_0+1,j_0*1}$ can not be zero by the minimality of $j_0$ and $t_0\text{).}$ But then this way of filling $Y\left(\frac{\nu }{\lambda }\right)$ does not satisfy LR1 ("symbols in a given column must be strictly increasing"), a contradiction. 2) Suppose LRA5 fails to hold for $\left[n_{ij}\right]\text{.}$ Then there exist indices $i_0,t_0$ such that $$\sum _{j=1}^{t_0}{n}_{i_{0}j}<\sum _{j=1}^{t_0+1}{n}_{i_0+1,j}\text{.}$$ We may assume $i_0$ is the least such index, and $t_0$ the least possible index corresponding to $i_0\text{.}$ In this case we must have $n_{i_0+1,t_0+1}\ne 0\text{.}$ Let $$k_1=\sum _{j=1}^{t_0}{n}_{i_{0}j}$$ and $$k_2=\sum _{j=1}^{t_0+1}{n}_{i_0+1,j}\text{.}$$ Now for the way of filling $Y\left(\frac{\nu }{\lambda }\right)$ given by $\left[n_{ij}\right],$ let the sequence $({\alpha }_1,{\alpha }_2,\dots )$ be obtained by reading the symbols $Y\left(\frac{\nu }{\lambda }\right)$ from right to left in the first, second, $\dots ,$ $d^{\text{th}}$ rows. Since $n_{i_0+1,t_0+1}\ne 0,$ the symbol $i_0+1$ occurs in row $t_0+1$ of $Y\left(\frac{\nu }{\lambda }\right)\text{.}$ Let the rightmost occurrence of $i_0+1$ in row $t_0+1$ appear in the sequence $({\alpha }_1,{\alpha }_2,\dots )$ as ${\alpha }_N\text{.}$ Then the number of occurrences of $i_0+1$ among ${\alpha }_1,{\alpha }_2,\dots ,{\alpha }_N$ is $k_2,$ while the number of occurences of $i_0$ among ${\alpha }_1,{\alpha }_2,\dots ,{\alpha }_N$ is $k_1\text{.}$ But $k_1<k_2$ contradicts the assumption that the given way of filling $Y\left(\frac{\nu }{\lambda }\right)$ satisfies LR2. Arguments 1) and 2) may be more readily understood by working out a few examples. A reversal of the arguments shows that for any integer matrix satisfying LRA1–LRA5, the corresponding way of filling $Y\left(\frac{\nu }{\lambda }\right)$ satisfies LR1 and LR2. This establishes the one-to-one correspondence and completes the proof of Theorem 4.12. $\square$

An integer matrix $\left[n_{ij}\right]$ satisfying conditions LRA1 through LRA2, with respect to partitions $\lambda ,\nu ,$ and $\nu ,$ will be called a $(\lambda ,\mu ,\nu )$ Littlewood-Richardson array $\text{(}(\lambda ,\mu ,\nu )\text{-LRA).}$ Theorem 4.12 shows that if a $(\lambda ,\mu ,\nu )\text{-LRA}$ exists, then the coefficient $c_{\lambda \mu \nu }$ is non-zero. In order to determine more about the existence of LRA's for a given triple $(\lambda ,\mu ,\nu ),$ we consider a slightly more general object.

Definition An element $(\lambda ,\mu ,\nu ,N)$ belonging to ${ℝ}^d\times {ℝ}^d\times {ℝ}^d\times {ℝ}^{d\times d}$ will be called a Littlewood-Richardson design (LRD) if the following conditions hold:

1)	${\lambda }_1\ge {\lambda }_2\ge \dots \ge {\lambda }_d\ge 0,$ ${\mu }_1\ge {\mu }_2\ge \dots \ge {\mu }_d\ge 0,$ ${\nu }_1\ge {\nu }_2\ge \dots \ge {\nu }_d\ge 0\text{.}$
2)	$N=\left[n_{ij}\right]$ satisfies conditions LRA1-LRA5.

Comments:

i)	If $(\lambda ,\mu ,\nu ,N)$ is an LRD which is integral, then $N$ is a $(\lambda ,\mu ,\nu )\text{-LRA.}$
ii)	If $N$ is a $(\lambda ,\mu ,\nu )\text{-LRA,}$ then $(\lambda ,\mu ,\nu ,N)$ is an integral LRD.

We now make a useful observation.

The set of Littlewood-Richardson designs in ${ℝ}^d\times {ℝ}^d\times {ℝ}^d\times {ℝ}^{d\times d}$ is a closed convex cone.

		Proof.
	The theorem follows from the fact that the set of LRD's is defined by a system of homogeneous linear inequalities. $\square$

The following theorem is fundamental.

Let $(\lambda ,\mu ,\nu )$ be partitions of length $d,$ $d\le 4\text{.}$ If there exists a $(\lambda ,\mu ,\nu )\text{-LRD,}$ then there exists a $(\lambda ,\mu ,\nu )\text{-LRA.}$

		Proof.
	Let $(\lambda ,\mu ,\nu ,N)$ be a $(\lambda ,\mu ,\nu )\text{-LRD;}$ we show how to successively "perturb" $N$ so that at each step we have a $(\lambda ,\mu ,\nu )\text{-LRD}$ and the final perturbed matrix is integral. Let $$N=\left(n_{ij}\right),1\le i,j\le d\text{.}$$ Condition LRA5 guarantees that $N$ is upper triangular. This makes the result trivial if $d=1$ or $d=2\text{.}$ For $d=3,$ the only non-integral elements of $N$ must lie in the submatrix $N[1,2|2,3]\text{.}$ The presence of fractions means that there is some "play" in the inequalities LRA4 and LRA5. If we "rotate" the submatrix $N[1,2|2,3]$ (i.e. add $\xi$ to $n_{12},$ subtract $\xi$ from $n_{13},$ add $\xi$ to $n_{23},$ and subtract $\xi$ from $n_{22}\text{)}$ the right amount, we obtain an integral matrix, and LRA1-LRA5 still hold. Now consider the case $d=4\text{.}$ Since $N$ is upper triangular, $n_{11}$ and $n_{dd}$ are integral. We perturb $N$ until $n_{33}$ is integral as follows: decrease $n_{22}$ and $n_{33}$ by $\xi ,$ increase $n_{12},n_{23},$ and $n_{34}$ by $\xi ,$ and decrease $n_{14}$ by $\xi ,$ where $$\xi =\text{min}\{n_{14},n_{33}-\left[n_{33}\right]\}\text{.}$$ As a result, either $n_{33}$ is integral or $n_{14}$ is zero. Case 1. $n_{14}=0$ Perturb $N$ further by decreasing $n_{22}$ and $n_{33}$ by $\xi \text{;}$ increasing $n_{12},$ $n_{23},$ and $n_{34}$ by $\xi$ and then increasing $n_{23}$ by another $\xi \text{;}$ and decreasing $n_{13}$ and $n_{24}$ by $\xi ,$ where this time $$\xi =\text{min}\{n_{13},n_{24},n_{33}-\left[n_{33}\right]\}\text{.}$$ One possible result is that $n_{13}=0\text{.}$ Then $n_{12}$ and $n_{22}$ are integral, so a rotation of $N[2,3|3,4]$ yields a $(\lambda ,\mu ,\nu )\text{-LRA.}$ The other possible result is that $n_{24}=0$ or $n_{33}$ is integral; in either case $n_{33},$ $n_{34},$ $n_{24},$ and $n_{14}$ are all integral, so a simple rotation of $N[1,2|2,3]$ yields a $(\lambda ,\mu ,\nu )\text{-LRA.}$ Case 2. $n_{33}$ is integral. Then $n_{34}$ is also integral, so we rotate $N[1,2|3,4]$ until an integral element results, and still have a $(\lambda ,\mu ,\nu )\text{-LRD.}$ The last non-integral elements all lie in some 2-by-2 submatrix; we again rotate to remove them, and wind up with a $(\lambda ,\mu ,\nu )\text{-LRA.}$ This ends the proof. $\square$

Theorem 4.14 removes a difficult constraint in verifying the existence of a $(\lambda ,\mu ,\nu )\text{-LRA;}$ i.e. the existence of any real matrix satisfying conditions LRA1-LRA5 is enough to guarantee the existence of an integral matrix satisfying those conditions. Relaxing this constraint allows the use of standard arguments from convexity theory.

Additional Characterizations of $V_d^n$

We can use several of the preceding results to formulate new characterizations for the set $V_d^n,$ introduced in section II. Theorem 3.9 states that $$V_d^n=\left\{(a,b,c)\hspace{0.17em}\right|\hspace{0.17em}\begin{array}{ll}\text{1)}& a,b,c\in Q_{d,n},\\ \text{2)}& \mathrm{\Omega }\left(a\right)·\mathrm{\Omega }\left(b\right)·\mathrm{\Omega }\left(c\right)\ne 0\end{array}\}\text{.}$$ Here $\mathrm{\Omega }\left(a\right),\mathrm{\Omega }\left(b\right),$ and $\mathrm{\Omega }\left(c\right)$ are Schubert cycles (elements of the ring $A\left(G_{d,n}\right)\text{).}$ This definition of $V_d^n$ is based on a multiplication statement in the ring $A\left(G_{d,n}\right)\text{.}$ We know from Theorem 4.9 that $A\left(G_{d,n}\right)$ is ring isomorphic to $A/I_{dn}\text{.}$ Using this isomorphism, we can translate the condition $$\mathrm{\Omega }\left(a\right)·\mathrm{\Omega }\left(b\right)·\mathrm{\Omega }\left(c\right)\ne 0$$ in $A\left(G_{d,n}\right)$ to an equivalent condition in $A/I_{dn}\text{.}$ Application of the Littlewood-Richardson rule then gives information about elements of $V_d^n\text{.}$

Suppose $$\mathrm{\Omega }\left(a\right)·\mathrm{\Omega }\left(b\right)·\mathrm{\Omega }\left(c\right)=n·\mathrm{\Omega }(1,2,\dots ,d)$$ and $$\mathrm{\Omega }\left(a\right)·\mathrm{\Omega }\left(b\right)=\sum _{s\in Q_{d,n}}{n}_s·\mathrm{\Omega }\left(s\right)\text{.}$$ Then $$n_{\bar{c}}=n\text{.}$$

		Proof.
	Easy consequence of Theorem 3.7. $\square$

Recall the definition of the map ${\theta }_{d,n}$ which maps the set of partitions ${\mathrm{\Pi }}_d$ onto the set $Q_{d,n}\text{:}$ $${\theta }_{d,n}\left(\lambda \right)=\{\begin{array}{ll}\varnothing ,& \text{if}\hspace{0.17em}\lambda \nleqq p,\\ n-d+1-{\lambda }_1,n-d+2-{\lambda }_2,\dots ,n-{\lambda }_d,& \text{otherwise.}\end{array}$$ We can define a one-sided inverse for ${\theta }_{d,n}$ which maps elements of $Q_{d,n}$ into the set of partitions $\mathrm{\Pi }\text{.}$ We will call this one-sided inverse ${\theta }_{d,n}^{-1}$ and define it by $${\theta }_{d,n}^{-1}\left(a\right)=(n-d+1-a_1,n-d+2-a_2,\dots ,n-a_d)\text{.}$$ By convention, ${\theta }^{-1}={\theta }_{d,n}^{-1}\text{.}$

Let $$\mathrm{\Omega }\left(a\right)·\mathrm{\Omega }\left(b\right)=\sum _{s\in Q_{d,n}}{n}_s·\mathrm{\Omega }\left(s\right)$$ and $$e_{{\theta }^{-1}\left(a\right)}·e_{{\theta }^{-1}\left(b\right)}=\sum _{\nu }{m}_{\nu }·e_{\nu }\text{.}$$ Then $$n_s=m_{{\theta }^{-1}\left(s\right)}\text{.}$$

		Proof.
	The isomorphism from $A/I_{dn}$ to $A\left(G_{d,n}\right)$ given by $$e_{\lambda }+I_{dn}⟶\mathrm{\Omega }\left(\theta \left(\lambda \right)\right)$$ has an inverse given by $$\mathrm{\Omega }\left(a\right)⟶e_{{\theta }^{-1}\left(a\right)}{I}_{dn}\text{.}$$ We are given that $$\mathrm{\Omega }\left(a\right)·\mathrm{\Omega }\left(b\right)=\sum _s{n}_s·\mathrm{\Omega }\left(s\right)$$ in $A\left(G_{d,n}\right)\text{.}$ Applying ${\theta }^{-1}$ to each side yields $$(e_{{\theta }^{-1}\left(a\right)}+I_{dn})(e_{{\theta }^{-1}\left(b\right)}+I_{dn})=\sum _s{n}_s·(e_{{\theta }^{-1}\left(s\right)}+I_{dn})$$ or $$\begin{array}{cc}{\displaystyle e_{{\theta }^{-1}\left(a\right)}·e_{{\theta }^{-1}\left(b\right)}+I_{dn}=\sum _{s\in Q_{d,n}}{n}_s·e_{{\theta }^{-1}\left(s\right)}+I_{dn}\text{.}}& \text{(*)}\end{array}$$ In the ring $A,$ we have $$\begin{array}{rcl}{\displaystyle e_{{\theta }^{-1}\left(a\right)}·e_{{\theta }^{-1}\left(b\right)}}& =& {\displaystyle \sum _{\nu \in \mathrm{\Pi }}{m}_{\nu }{e}_{\nu }}\\ & =& {\displaystyle \sum _{\nu \le p}{m}_{\nu }{e}_{\nu }+\sum _{\nu \nleqq p}{m}_{\nu }{e}_{\nu }\text{.}}\end{array}$$ Mapping this equation into $A/I_{dn}$ yields $$e_{{\theta }^{-1}\left(a\right)}·e_{{\theta }^{-1}\left(b\right)}+I_{dn}=\sum _{\nu \le p}{m}_{\nu }{e}_{\nu }+I_{dn}$$ or $$\begin{array}{cc}{\displaystyle e_{{\theta }^{-1}\left(a\right)}·e_{{\theta }^{-1}\left(b\right)}+I_{dn}=\sum _{s\in Q_{d,n}}{m}_{{\theta }^{-1}\left(s\right)}·(e_{{\theta }^{-1}\left(s\right)}+I_{dn})\text{.}}& \text{(**)}\end{array}$$ Comparing (*) to (**) shows that $$n_s=m_{{\theta }^{-1}\left(s\right)}\text{.}$$ $\square$

$$\begin{array}{c}\mathrm{\Omega }\left(a\right)·\mathrm{\Omega }\left(b\right)·\mathrm{\Omega }\left(c\right)=n·\mathrm{\Omega }(1,2,\dots ,d)\\ \text{for some non-zero}\hspace{0.17em}n\end{array}⟺\text{there exists a}\hspace{0.17em}({\theta }^{-1}\left(a\right),{\theta }^{-1}\left(b\right),{\theta }^{-1}\left(\bar{c}\right))\text{-LRA.}$$

		Proof.
	The theorem follows in a straightforward manner from lemmas 4.15 and 4.16 and Theorem 4.12. $\square$

We now have two methods of testing whether a product $\mathrm{\Omega }\left(a\right)·\mathrm{\Omega }\left(b\right)·\mathrm{\Omega }\left(c\right),$ known to be a multiple of $\mathrm{\Omega }(1,2,\dots ,d),$ is non-zero:

1)	Compute (using the determinantal and Pieri's formula) $\mathrm{\Omega }\left(a\right)·\mathrm{\Omega }\left(b\right)·\mathrm{\Omega }\left(c\right)$ in the ring $A\left(G_{d,n}\right)\text{;}$
2)	Determine (using the LR rule) whether a $({\theta }^{-1}\left(a\right),{\theta }^{-1}\left(b\right),{\theta }^{-1}\left(\bar{c}\right))\text{-LRA}$ exists.

Note that method 1 yields more information than we seek: it identifies the multiple exactly. Method 2 can also be used to find the multiple exactly, but with less work can simply tell whether or not the multiple is non-zero.

We introduce some notation relevant to the next theorem: For $a\in Q_{d,n}$ and $a\prime \in Q_{d,n\prime },$ define $a\oplus a\prime$ by $$(a\oplus a\prime )\left(i\right)=a_i+a_i^{\prime }-i(a\oplus a\prime \in Q_{d,n+n\prime -d})\text{.}$$

("generalized pushing lemma") If $(a,b,c)\in V_d^n$ and $(a\prime ,b\prime ,c\prime )\in V_d^{n\prime },$ then $$(a,b,c)\oplus (a\prime ,b\prime ,c\prime )\in V_d^{n+n\prime -d}\text{.}$$

		Proof.
	The proof is done by translating from sequences in $Q_{d,n},Q_{d,n\prime },$ and $Q_{d,n+n\prime -d}$ to partitions in ${\mathrm{\Pi }}_d\text{.}$ Let $(a,b,c)\in V_d^n$ and $(a\prime ,b\prime ,c\prime )\in V_d^{n\prime }\text{.}$ Then $$\begin{array}{rcl}{\displaystyle \mathrm{\Omega }\left(a\right)·\mathrm{\Omega }\left(b\right)·\mathrm{\Omega }\left(c\right)}& \ne & {\displaystyle 0\hspace{0.17em}\text{in}\hspace{0.17em}A\left(G_{d,n}\right),}\\ {\displaystyle \mathrm{\Omega }\left(a\prime \right)·\mathrm{\Omega }\left(b\prime \right)·\mathrm{\Omega }\left(c\prime \right)}& \ne & {\displaystyle 0\hspace{0.17em}\text{in}\hspace{0.17em}A\left(G_{d,n\prime }\right)\text{.}}\end{array}$$ First assume both these products are non-zero multiples of $\mathrm{\Omega }(1,2,\dots ,d)$ in $A\left(G_{d,n}\right)$ and $A\left(G_{d,n\prime }\right),$ respectively. From Theorem 4.17, there exists a $$({\theta }_{d,n}^{-1}\left(a\right),{\theta }_{d,n}^{-1}\left(b\right),{\theta }_{d,n}^{-1}\left(\bar{c}\right))\text{-LRA,}$$ (which we will denote by $N\text{),}$ and a $$({\theta }_{d,n}^{-1}\left(a\prime \right),{\theta }_{d,n}^{-1}\left(b\prime \right),{\theta }_{d,n}^{-1}\left(\bar{c}\prime \right))\text{-LRA,}$$ (which we will denote by $N\prime \text{).}$ From Theorem 4.13, $N+N\prime$ is an LRA. Let $$\begin{array}{rcl}{\displaystyle \lambda }& =& {\displaystyle {\theta }_{d,n+n\prime -d}^{-1}(a\oplus a\prime ),}\\ {\displaystyle \mu }& =& {\displaystyle {\theta }_{d,n+n\prime -d}^{-1}(b\oplus b\prime ),}\\ {\displaystyle \nu }& =& {\displaystyle {\theta }_{d,n+n\prime -d}^{-1}\left(\overline{c\oplus c\prime }\right)\text{.}}\end{array}$$ Again by Theorem 4.17, we can show that $$(a\oplus a\prime ,b\oplus b\prime ,c\oplus c\prime )\in V_d^{n+n\prime -d}$$ if there exists a $(\lambda ,\mu ,\nu )\text{-LRA,}$ and this will establish the theorem. We claim that $N+N\prime$ is a $(\lambda ,\mu ,\nu )\text{-LRA.}$ The verification amounts to the following exercise: $$\begin{array}{rcl}{\displaystyle \left[{\theta }_{d,n}^{-1}\left(a\right)\right]\left(i\right)+\left[{\theta }_{d,n}^{-1}\left(a\prime \right)\right]\left(i\right)}& =& {\displaystyle (n-d+i-a_i)+(n\prime -d+i-a_i^{\prime })}\\ & =& {\displaystyle (n+n\prime -d)-d+i-(a_i+a_i^{\prime }-i)}\\ & =& {\displaystyle (n+n\prime -d)-d+i-[a\oplus a\prime ]\left(i\right)}\\ & =& {\displaystyle \left[{\theta }_{n+n\prime -d}^{-1}(a\oplus a\prime )\right]\left(i\right)\text{.}}\end{array}$$ This identity, together with the fact that $$\overline{c\oplus c\prime }=\bar{c}\oplus \overline{c\prime },$$ easily establishes the claim. The theorem is now established in the case where the products of Schubert cycles are multiples of $\mathrm{\Omega }(1,2,\dots ,d)\text{.}$ If this is not the case, then by Theorem 3.10 we can find $$\begin{array}{rcl}{\displaystyle (x,y,z)}& \le & {\displaystyle (a,b,c),}\\ {\displaystyle (x\prime ,y\prime ,z\prime )}& \le & {\displaystyle (a\prime ,b\prime ,c\prime )}\end{array}$$ such that the products $\mathrm{\Omega }\left(x\right)·\mathrm{\Omega }\left(y\right)·\mathrm{\Omega }\left(z\right)$ and $\mathrm{\Omega }\left(x\prime \right)·\mathrm{\Omega }\left(y\prime \right)·\mathrm{\Omega }\left(z\prime \right)$ are non-zero multiples of $\mathrm{\Omega }(1,2,\dots ,d)\text{.}$ Hence $$(x,y,z)\oplus (x\prime ,y\prime ,z\prime )\in V_d^{n+n\prime -d}$$ by our previous result. Since $$(x,y,z)\oplus (x\prime ,y\prime ,z\prime )\le (a,b,c)\oplus (a\prime ,b\prime ,c\prime ),$$ Theorem 2.11 guarantees the desired result. $\square$

In the next section, we will show that Theorem 4.18 is indeed a generalization of Horn's original "pushing" lemma.

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