Flag Varieties and Interpretations of Young Tableau Algorithms

Marc A. A. van Leeuwen

Université de Poitiers, Département de Mathématiques, UFR Sciences SP2MI, Téléport 2, BP 30179, 86962 Futuroscope Chasseneuil Cedex, France

                              maavl@math.univ-poitiers.fr
                     URL: http://www-math.univ-poitiers.fr/~maavl/

ABSTRACT

The conjugacy classes of nilpotent n × n matrices can be parametrised by partitions λ of n, and for a nilpotent η in the class parametrised by λ, the variety F_{η} of η-stable flags has its irreducible components parametrised by the standard Young tableaux of shape λ. We indicate how several algorithmic constructions defined for Young tableaux have significance in this context, thus extending Steinberg’s result that the relative position of flags generically chosen in the irreducible components of F_{η} parametrised by tableaux P and Q, is the permutation associated to (P, Q) under the Robinson-Schensted correspondence. Other constructions for which we give interpretations are Schützenberger’s involution of the set of Young tableaux, jeu de taquin (leading also to an interpretation of Littlewood-Richardson coefficients), and the transpose Robinson-Schensted correspondence (defined using column insertion). In each case we use a doubly indexed family of partitions, defined in terms of the flag (or pair of flags) determined by a point chosen in the variety under consideration, and we show that for generic choices, the family satisfies combinatorial relations that make it correspond to an instance of the algorithmic operation being interpreted, as described in [vLee3].

1991 Mathematics Subject Classification: 05E15, 20G15.

Keywords and Phrases: flag manifold, nilpotent, Jordan decomposition, jeu de taquin, Robinson-Schensted

correspondence, Littlewood-Richardson rule. Note: Work partly supported by the Schweizerische Nationalfonds and by l’Université du Québec à Montréal.

§0. Introduction. The Schensted algorithm, which defines a bijective correspondence between permutations and pairs of (standard) Young tableaux, and the Schützenberger (or evacuation) algorithm, which defines a shape preserving involution of the set of Young tableaux, can both be described using doubly indexed families of partitions that satisfy certain local rules, as described in [vLee3]. In this paper we show how both correspondences occur in relation to questions concerning varieties of flags stabilised by a fixed nilpotent transformation η. The mentioned doubly indexed families of partitions arise very naturally in this context, and they provide detailed information concerning the internal steps of the algorithms, rather than just about the correspondences defined by them. As a consequence, the study of the Schützenberger algorithm also leads to an interpretation of jeu de taquin, and of the Littlewood-Richardson coefficients. The connections between geometry and combinatorics presented here include and extend results due to Steinberg ([Stb1], [Stb2]) and Hesselink ([Hes]).

The basic fact underlying these interpretations is that the irreducible components of the variety F_{η} of η-stable complete flags is parametrised in a natural way by the set of standard Young tableaux of shape equal to the Jordan type J(η) of η. In fact there are two dual parametrisations, and we show that the transition between them is given by the Schützenberger involution. Taking a projection on varieties of incomplete flags by forgetting the parts of flags below a certain dimension, we obtain from this an interpretation of jeu de taquin (operating on skew standard tableaux), and a bijection between Littlewood-Richardson tableaux and irreducible components of a variety of η-stable subspaces of fixed type and cotype.

The other interpretations involve the Robinson-Schensted algorithm and relative positions of flags. We give a derivation of Steinberg’s result that the relative position of two generically chosen flags in given irreducible components of F_{η} is the permutation related by the Robinson-Schensted correspondence to the pair of the tableaux parametrising those components. For this result a specific choice of parametrisation is required, but there are variations of the statement for other choices; in particular when dual parametrisations are used for the two components, one obtains the transpose Robinson-Schensted correspondence, defined using column insertion. Together, these interpretations give a geometric meaning to many key properties of the combinatorial correspondences: involutivity of the Schützenberger correspondence, confluence of jeu de taquin, the fact that the number of skew tableaux of a fixed shape and given rectification P depends only on the shape of P, symmetry of the Robinson-Schensted correspondence, and the various relations between this correspondence, its transpose, and the Schützenberger correspondence.

This paper is organised as follows. In §1 we review the essential facts in the linear algebra of a vector space equipped with a nilpotent transformation η, followed in §2 by the definition of the variety F_{η}, and the parametrisations of its irreducible components by Young tableaux. In §3 and §4 we give the respective interpretations of the Schützenberger algorithm, and of jeu de taquin and Littlewood-Richardson tableaux. In §5 we discuss relative positions of flags, which are used in §6 to give a geometric interpretation of the Robinson-Schensted correspondence, and in §7 to give a similar but independent interpretation of the transposed Robinson-Schensted correspondence.

In our combinatorial notation, as well as in our approach of the algorithms considered, we shall closely follow [vLee3]; we collect here the essential definitions used. A partition λ is an infinite weakly decreasing sequence λ_{0} ≥ λ_{1} ≥ ⋯ of natural numbers (called the parts of λ) with finite sum, denoted by |λ|. To each partition λ is associated its Young diagram Y (λ) ⊂ N × N, defined by (i, j) ∈ Y (λ) ⟺ j < λ_{i} (so that #Y (λ) = |λ|); the transposed partition λ^{t} of λ is the one whose Young diagram is obtained by reflection of Y (λ) in the main diagonal. The elements of Y (λ) are called its squares, and are depicted correspondingly (so that they may be filled with values); Young diagrams are displayed with the first index i increasing downwards, the second increasing toward the right, like matrices. The set of all partitions is denoted by P, and is partially ordered by inclusion of Young diagrams, written ‘⊆’; the elements of P_{n} = { λ ∈ P | |λ| = n }, are called partitions of n. For the predecessor relation in P, which was denoted by μ ∈ λ^{−} in [vLee3], we shall write instead μ ≺ λ, with μ ⪯ λ meaning that μ ≺ λ or μ = λ. When μ ≺ λ and Y (λ) \ Y (μ) = {x} we call the square x a corner of λ and a cocorner of μ, and write λ = μ + x, μ = λ − x and λ − μ = x. We write x ∥ y to indicate that squares x and y are adjacent.

A Young tableau is an injective map T: Y (λ) → N, for some λ ∈ P called the shape sh T of T, such that when each number T (i, j) is written as entry into square (i, j), all rows and columns are increasing. Each such T determines a saturated decreasing chain ch T from λ to (0) in P, by recording the successive shapes as the squares are removed from Y (λ) in order of decreasing entries. When ch T = ch T′ we write T ∼ T′, which is an equivalence relation on tableaux; for tableaux of fixed shape λ, a set of representatives of the equivalence classes is formed by the set T_{λ} of normalised tableaux, whose entries are all < |λ|. For any non-empty Young tableau T, the square containing the highest entry of T is denoted by ⌈T ⌉, and the tableau obtained by removing that square (and its entry) from T by T^{−}. By applying the deflation procedure used in the definition of the Schützenberger algorithm to T, a tableau T^{↓} is obtained, in which the smallest entry has disappeared. The result of applying the full Schützenberger algorithm to T is denoted by S(T), and the pair of tableaux obtained by applying the Schensted algorithm to a permutation σ is denoted by RS(σ) (see [vLee3] for definitions).

When numbering or indexing with natural numbers, these definitions all start using 0, rather than 1; this holds in particular for the parts of a partition, and the rows and columns of Young diagrams. This leads to simpler expressions, but note that while row i of Y (λ) has length λ_{i}, it has no square in column λ_{i}. We even have gone a bit further than in [vLee3], by defining entries of normalised tableaux to start at 0. Also, the group S_{n} is taken to consist of permutations of {0, …, n − 1}, represented by sequences of the form σ_{0}, σ_{1}, …, σ_{n−1}; in particular, the order reversing permutation ñ ∈ S_{n} satisfies ñ_{i} = n − 1 − i.

1 Nilpotent transformations

The work presented here was motivated by that of the author’s thesis [vLee1], which deals with the significantly more complicated case of other classical groups (in characteristic ≠ 2) instead of GL_{n}. There a combinatorial algorithm analogous to the Robinson-Schensted algorithm is deduced, that performs the corresponding computation of generic relative positions of flags; however there are complications that cause the descriptions and proofs to be much more technical than those in the current paper. Our aim here was to separate the main techniques and arguments of [vLee1] from a number of distracting technicalities, by applying them in the simpler situation of GL_{n}; even so the reasoning is sometimes detailed and subtle. At the same time we believe that in describing that situation as transparently as possible, we have been able to provide some new insight.

§1. Nilpotent transformations. Let V be a vector space of finite dimension n over an infinite field k. In this section we recall some basic facts concerning V, equipped with a fixed nilpotent endomorphism η. Most of these facts are also discussed, from a somewhat more general and elevated perspective, in [Macd, Chapter II].

A subspace V′ of V is called η-stable if η(V′) ⊆ V′. There exists a decomposition of V as a direct sum of non-zero η-stable subspaces that cannot be so decomposed further; any summand of dimension d admits a basis x_{0}, …, x_{d−1} such that η(x_{0}) = 0 and η(x_{i}) = x_{i−1} for 0 < i < d. This is called a decomposition into Jordan blocks; it is generally not unique, but the multiset of the dimensions of the blocks depends only on η. Arranged into weakly decreasing order these dimensions form a partition of n, called the Jordan type J(η) of η. Throughout this paper we write λ for J(η) and u for the unipotent transformation η + 1 ∈ GL(V) corresponding to η; when η is variable, λ and u are assumed to vary correspondingly.

One can characterise λ in terms of the powers η^{j} of η (among which we include η^{0} = 1), without referring to any particular decomposition into Jordan blocks, as follows.

1.1. Proposition. For all c ≥ 0 one has dim(ker η^{c}) = ∑_{0≤j<c} λ_{j}^{t}, which is the number of squares in the first c columns of the Young diagram Y (λ). Similarly, dim(im η^{c}) = ∑_{j≥c} λ_{j}^{t}, which is the number of squares in the remaining columns of Y (λ).

Proof. This is easily verified for individual Jordan blocks, from which the general case follows.

For any η-stable subspace V′ of V, η induces nilpotent endomorphisms of the spaces V′ and V/V′, which will be denoted respectively by η|_{V′} and η_{/V′}. Since a nilpotent endomorphism of a 1-dimensional space is necessarily 0, a subspace l of dimension 1 (a line) is η-stable if and only if l ⊆ ker η, and similarly a subspace H of codimension 1 (a hyperplane) is η-stable if and only if H ⊇ im η.

1.2. Proposition. Let V′ be an η-stable subspace of V. Then J(η|_{V′}) ⊆ λ, and J(η_{/V′}) ⊆ λ.

Proof. The image of the subspace ker η^{j} under the projection V → V/V′ is ker η^{j}/ ker(η|_{V′})^{j}, for all j ≥ 0; since ker η^{j} ⊆ ker η^{j+1}, it follows that dim(ker η^{j})−dim(ker(η|_{V′})^{j}) increases weakly as j increases:

dim(ker η^{j}) − dim(ker(η|_{V′})^{j}) ≤ dim(ker η^{j+1}) − dim(ker(η|_{V′})^{j+1}).  (1)

The length λ_{j}^{t} of column j of Y (λ) is equal to dim(ker η^{j+1}) − dim(ker η^{j}) by proposition 1.1, so from (1) one gets J(η|_{V′})_{j}^{t} ≤ λ_{j}^{t}, and combining this for all j yields J(η|_{V′}) ⊆ λ. Similarly, the kernel of the projection im η^{j} → (im η^{j})/V′ = im(η_{/V′})^{j} is equal to V′ ∩ im η^{j}, so its dimension dim(im η^{j}) − dim(im(η_{/V′})^{j}) decreases weakly as j increases, since im η^{j} ⊇ im η^{j+1}. Then using λ_{j}^{t} = dim(im η^{j}) − dim(im η^{j+1}), it follows analogously to the argument above that λ_{j}^{t} ≥ J(η_{/V′})_{j}^{t} for all j, whence J(η_{/V′}) ⊆ λ.

The partition J(η|_{V′}) is called the type of V′, and J(η_{/V′}) is the cotype of V′ (in V). Since the spaces ker(η|_{V′})^{j} = V′ ∩ ker η^{j} whose dimensions determine the type of V′ are not directly related to the spaces V′ ∩ im η^{j} that were used to determine its cotype, it is not generally possible (for a fixed value of λ) to determine the type from the cotype or vice versa. However, there is an exception when λ is a “rectangular” partition, i.e., when all its non-zero parts have a fixed size d: in that case one has ker η^{j} = im η^{d−j} for 0 ≤ j ≤ d. This leads to the following fact.

1.3. Proposition. If λ = (d, d, …, d) with d occurring m times, and J(η|_{V′}) = (μ_{0}, …, μ_{m−1}), then J(η_{/V′}) = (d − μ_{m−1}, …, d − μ_{0}).

Proof. From the proof of proposition 1.2, one has for 0 ≤ j < d:

J(η|_{V′})_{j}^{t} = dim(V′ ∩ ker η^{j+1}) − dim(V′ ∩ ker η^{j}) = dim(V′ ∩ im η^{d−j−1}) − dim(V′ ∩ im η^{d−j}) = λ_{d−j−1}^{t} − J(η_{/V′})_{d−j−1}^{t} = m − J(η_{/V′})_{d−j−1}^{t},

from which the stated relation between J(η|_{V′}) and J(η_{/V′}) follows.

We now specialise to the cases of η-stable lines and hyperplanes. As we have seen above, η-stability of a line l means l ⊆ ker η, so the set of η-stable lines is identified with the projective space P(ker η), which we shall denote by P(V)_{η}. Also, the cotype J(η_{/l}) of l is determined by the (weakly decreasing) sequence of values dim(l ∩ im η^{j}) ∈ {0, 1}, for j ≥ 0. We define for j ∈ N subspaces

W_{j}(η) = ker η ∩ im η^{j}  (2)

of ker η, which form a weakly decreasing chain. We also define subsets

U_{j}(η) = P(W_{j}(η)) \ P(W_{j+1}(η))  (3)

of the projective space P(V)_{η}; the non-empty U_{j}(η) form a finite partition of that space. We have dim W_{j}(η) = λ_{j}^{t} by proposition 1.1; therefore U_{j}(η) is non-empty if and only if the following equivalent statements hold: λ_{j}^{t} > λ_{j+1}^{t}; there is a corner of λ in column j; at least one part of λ equals j + 1. For the case of η-stable hyperplanes we can apply these definitions to η^{∗}, the nilpotent endomorphism of the dual vector space V^{∗} given by η^{∗}(ϕ): v ↦ ϕ(η(v)) for ϕ ∈ V^{∗} and v ∈ V. We therefore define

W_{j}^{∗}(η) = W_{j}(η^{∗}) = { ϕ ∈ V^{∗} | ϕ(im η) = 0 ∧ ϕ(ker η^{j}) = 0 }.  (4)

The set U_{j}(η^{∗}) is contained in the set P(V^{∗}) of 1-dimensional subspaces of V^{∗}, which is in canonical bijection with the set of hyperplanes H of V by H ↦ { ϕ ∈ V^{∗} | ϕ(H) = 0 }. We shall denote this set of hyperplanes by P^{∗}(V), and its subset { H ∈ P^{∗}(V) | H ⊇ im η } of η-stable hyperplanes by P^{∗}(V)_{η}. Then we define U_{j}^{∗}(η) as the subset of P^{∗}(V)_{η} corresponding to U_{j}(η^{∗}):

U_{j}^{∗}(η) = { H ∈ P^{∗}(V)_{η} | H ⊇ ker η^{j} ∧ H ⊉ ker η^{j+1} }.  (5)

The U_{j}(η) and U_{j}^{∗}(η) respectively partition P(V)_{η} according to cotype and P^{∗}(V)_{η} according to type:

1.4. Proposition. If l ∈ U_{j}(η), then the Young diagram of J(η_{/l}) is obtained from that of λ by removing its corner in column j. If H ∈ U_{j}^{∗}(η), then the Young diagram of J(η|_{H}) is obtained from that of λ by removing its corner in column j.

Proof. If l ∈ U_{j}(η), then by reasoning as in the proof of proposition 1.2 we find that λ_{j}^{t} − J(η_{/V′})_{j}^{t} = 1, and λ_{c}^{t} = J(η_{/V′})_{c}^{t} for all c ≠ j. The argument for H ∈ U_{j}^{∗}(η) is entirely analogous.

For any basis {b_{0}, …, b_{k}} of ker η with the property that each W_{j}(η) is spanned by { b_{i} | 0 ≤ i < λ_{j}^{t} }, one can find a decomposition into Jordan blocks V = B_{0} ⊕ ⋯ ⊕ B_{k} such that ker(η|_{B_{i}}) = ⟨b_{i}⟩ for all i (it suffices to choose vectors v′_{i} with η^{j}(v′_{i}) = b_{i}, where j is such that⟨b_{i}⟩ ∈ U_{j}(η), and to set B_{i} = ⟨η^{k}(v′_{i}) | 0 ≤ k ≤ j⟩). For any given l ∈ P(V)_{η} the basis can be chosen such that l = ⟨b_{i}⟩ for some i; we shall say that a corresponding decomposition of V into Jordan blocks is adapted to l. We shall similarly call a decomposition of V into Jordan blocks adapted to H ∈ P^{∗}(V)_{η} if H contains all blocks but one; for that block B_{i} one has H ∩ B_{i} = im(η|_{B_{i}}). We see that the centraliser Z_{u} of u in GL(V) acts transitively on each set U_{j}(η) and on each U_{j}^{∗}(η). The following characterisations of the index j such that l ∈ U_{j}(η) respectively H ∈ U_{j}^{∗}(η) will be useful in the sequel.

1.5. Lemma.

(1) If l ∈ U_{j}(η), then j is the minimal value for which (ker η)/l ⊇ W_{j}(η_{/l}).

(2) If H ∈ U_{j}^{∗}(η), then j is the minimal value for which im η ⊆ im(η|_{H}) + ker(η|_{H})^{j}.

(3) H ∈ U_{j}^{∗}(η) if and only if im η + ker η^{j} = im(η|_{H}) + ker(η|_{H})^{j}.

(4) If H ∈ U_{j}^{∗}(η), then W_{c}(η|_{H}) = W_{c}(η) for c ≠ j, while W_{j}(η|_{H}) is a hyperplane in W_{j}(η).

2 Flags

Proof. In each case let the initial condition be satisfied, and let V = B_{0} ⊕ ⋯ ⊕ B_{k} be a decomposition into Jordan blocks adapted to l respectively to H. For (1), let B_{i} be the block containing l, then V/l ≅ B_{0} ⊕ ⋯ ⊕ (B_{i}/l) ⊕ ⋯ ⊕ B_{k}, and the projection V → V/l is the identity on all summands except B_{i}. This reduces us to the case V = B_{i}; then (ker η)/l = {0} and J(η_{/l}) = (j), whence the statement is obvious. For (2), let B_{i} be the block not contained in H, then the intersection of im η with any other block is contained in im(η|_{H}); this again reduces us to the case V = B_{i}, where the statement follows from J(η|_{H}) = (j). Part (3) now follows because ker η^{c} ⊈ H for c > j. Part (4) also follows by considering the decomposition of V, or by observing that W_{c}(η|_{H}) ⊆ W_{c}(η) and dim(W_{c}(η)) = λ_{c}^{t}, in conjunction with proposition 1.4.

§2. Flags.

A (complete) flag f in V is a saturated chain 0 = f_{0} ⊂ f_{1} ⊂ ⋯ ⊂ f_{n} = V of subspaces of V. We have dim f_{i} = i, and the individual spaces f_{i} are called the parts of f. Let F be the set of all such flags, called the flag manifold of V. It has the structure of a projective algebraic variety (see [Hum, 8.1]), and the maps f ↦ f_{i} are morphisms onto the respective Grassmann varieties. Of particular interest are the morphisms giving the line and hyperplane parts: if n > 0 we define α: F → P(V) and ω: F → P^{∗}(V) by α(f) = f_{1}, ω(f) = f_{n−1}. The group GL(V) acts on F, P(V), and P^{∗}(V), and clearly α and ω are GL(V)-equivariant. We say that a flag f ∈ F is η-stable if all its parts are, and let F_{η} denote the subvariety of η-stable flags in F, or equivalently the fixed point set of u acting on F; α_{η} and ω_{η} will denote the restrictions to F_{η} of α and ω, respectively. We have im α_{η} = P(V)_{η} = ⋃_{j≥0} U_{j}(η), and similarly im ω_{η} = P^{∗}(V)_{η} = ⋃_{j≥0} U_{j}^{∗}(η).

For each η-stable hyperplane H ∈ P^{∗}(V)_{η}, the fibre ω_{η}^{−1}(H) of ω_{η} is isomorphic to the variety F_{η|_{H}} of η|_{H}-stable flags in H. Indeed the isomorphism is given by f ↦ f^{−}, where f^{−} = (f_{0} ⊂ ⋯ ⊂ f_{n−1} = H) is the flag obtained from f by omitting the last part f_{n} = V. Similarly, for each η-stable line l ∈ P(V)_{η}, the fibre α_{η}^{−1}(l) is isomorphic to the variety F_{η_{/l}} of η_{/l}-stable flags in V/l; here the isomorphism will be written as f ↦ f^{↓}, where f^{↓} = (f_{1}/l ⊂ ⋯ ⊂ f_{n}/l) is the flag obtained from f by reducing modulo f_{1} = l all its parts except f_{0}. There will be no confusion if the same notations f^{−} and f^{↓} are used when f is a flag in a vector space other than V (provided its dimension is non-zero); this allows us in particular to write for f ∈ F_{η} expressions such as f^{−−}, f^{↓↓↓}, and f^{−↓}, as long as the total number of operations applied does not exceed n. Moreover, the operations commute: f^{−↓} and f^{↓−} denote the same flag in f_{n−1}/f_{1}. In general, one obtains in this manner from f ∈ F_{η} an η_{f_{i}/f_{j}}-stable flag in f_{i}/f_{j}, for some i ≥ j, where η_{f_{i}/f_{j}} is the nilpotent endomorphism of f_{i}/f_{j} induced by η.

The sequences of types and of cotypes of the parts of f ∈ F_{η} define two saturated decreasing chains in P from λ to (0), that can be used to define Young tableaux r_{η}(f), q_{η}(f) ∈ T_{λ}:

ch r_{η}(f) = (J(η), J(η|_{f_{n−1}}), J(η|_{f_{n−2}}), …, (0)),  (6)
ch q_{η}(f) = (J(η), J(η_{/f_{1}}), J(η_{/f_{2}}), …, (0)).  (7)

In other words, the subtableau of r_{η}(f) containing entries < i has shape J(u|_{f_{i}}), while the subtableau of q_{η}(f) containing entries < n − i has shape J(u_{/f_{i}}). If we define for each flag f ∈ F a dual flag f^{∗} in V^{∗} by f^{∗}_{i} = { ϕ ∈ V^{∗} | ϕ(f_{n−i}) = 0 }, then one readily verifies that q_{η}(f) = r_{η^{∗}}(f^{∗}), and r_{η}(f) = q_{η^{∗}}(f^{∗}).

As was mentioned earlier, there is in general no direct relationship between the type and cotype of the parts of f, and so there is no one-to-one correspondence between r_{η}(f) and q_{η}(f) either. However, we have again an exception if λ is a rectangular partition. To describe the relationship in this case, we introduce the involutive operation T ↦ T^{⋄} on T_{λ} for rectangular λ: let the square t be the unique corner of λ, then whenever some square s ≤ t has entry i in t, then the diametrically opposite square t − s has entry ñ_{i} = n−1−i in T^{⋄} (this is essentially the same as the operation P ↦ \overline{P} of [vLee3, proposition 5.7]).

2.1. Proposition. If λ is a rectangular partition, then q_{η}(f) = r_{η}(f)^{⋄} for all f ∈ F_{η}.

Proof. Put ch r_{η}(f) = (λ^{n}, λ^{n−1}, …, λ^{0}), and ch q_{η}(f) = (μ^{n}, …, μ^{0}). Then each λ^{i} determines μ^{n−i}, as described in proposition 1.3. For 0 ≤ i < n, the square with entry i in r_{η}(f) is λ^{i+1} − λ^{i}, which determines the square μ^{n−i} − μ^{n−i−1} containing ñ_{i} in q_{η}(f); therefore q_{η}(f) = r_{η}(f)^{⋄}.

We define for any Young tableau T of shape λ:

F_{η,T} = { f ∈ F_{η} | r_{η}(f) ∼ T },  (8)
F_{η,T}^{∗} = { f ∈ F_{η} | q_{η}(f) ∼ T }.  (9)

If the square ⌈T ⌉ lies in column j (which implies that U_{j}(η) and U_{j}^{∗}(η) are non-empty), then one has ω(F_{η,T}) ⊆ U_{j}^{∗}(η) and α(F_{η,T}^{∗}) ⊆ U_{j}(η). Moreover, for any H ∈ U_{j}^{∗}(η) the fibre F_{η,T} ∩ ω_{η}^{−1}(H) is isomorphic to F_{η|_{H},T^{−}} by f ↦ f^{−}, and for any l ∈ U_{j}(η) the fibre F_{η,T}^{∗} ∩ α_{η}^{−1}(l) is isomorphic to F_{η_{/l},T^{−}}^{∗} by f ↦ f^{↓}. It follows by induction that each of the sets F_{η,T} and F_{η,T}^{∗} is non-empty, and open in its closure. As T ranges over T_{λ}, the sets F_{η,T} partition F_{η} into finitely many subsets, as do the sets F_{η,T}^{∗}.

2.2. Proposition.

(1) For each T ∈ T_{λ} the sets F_{η,T} and F_{η,T}^{∗} are irreducible.

(2) dim(F_{η,T}) = dim(F_{η,T}^{∗}) = n(λ) =^{def} ∑_{i∈N} iλ_{i}, regardless of T ∈ T_{λ}.

(3) The set of irreducible components of F_{η} is equal to \{ \overline{F_{η,T}} | T ∈ T_{λ} \}, and also to \{ \overline{F_{η,T}^{∗}} | T ∈ T_{λ} \}.

Proof. We proceed by induction on n = |λ|, and only prove the statements for F_{η,T}, as those for F_{η,T}^{∗} are entirely similar (and also follow by transition to the dual vector space). The case n = 0 is trivial, so assume n > 0; let T ∈ T_{λ} and let ⌈T ⌉ be the square (i, j). Since U_{j}^{∗}(η) is irreducible and an orbit for Z_{u}, it is already an orbit for the identity component Z_{u}^{∘} of Z_{u} (in fact Z_{u} is always connected, but we do not wish to invoke that fact here). Using the isomorphism F_{η,T} ∩ ω_{η}^{−1}(H) →^{∼} F_{η|_{H},T^{−}} for some H ∈ U_{j}^{∗}(η), we may define a surjective morphism Z_{u}^{∘} × F_{η|_{H},T^{−}} → F_{η,T} by (z, f^{−}) ↦ z · f; since the domain of this morphism is irreducible by the induction hypothesis, so is its image, which establishes (1). We have dim(U_{j}^{∗}(η)) = dim(W_{j}^{∗}(η))−1 = i, and so for any H ∈ U_{j}^{∗}(η) we have dim F_{η,T} = dim U_{j}^{∗}(η) + dim F_{η|_{H},T^{−}} = i + n(sh T^{−}) = n(λ), proving (2). Part (3) follows from (1) and (2). Remark. Part (3) gives two different natural parametrisations of the irreducible components of F_{η} by Young tableaux. The first one, based on the types of the parts of flags (as it uses r_{η}) corresponds to the parametrisation used in [Stb2], but in [Spa2, II.5.3] the other parametrisation, based on cotypes (q_{η}), is effectively used. We choose to work primarily with the former parametrisation, partly because it is somewhat simpler to use restrictions than quotients, but mainly because this choice leads to a more direct interpretation of the Robinson-Schensted algorithm. Note that our choice does lead to a slightly illogical use of asterisks: F_{η,T} has a fibration over U_{j}^{∗}(η), while F_{η,T}^{∗} has one over U_{j}(η).

We close this section with an example, illustrating these parametrisations of the irreducible components of F_{η} in the simplest non-trivial case, namely for the Jordan type λ = (2, 1). Then T_{λ} has 2 elements, namely

T = 0 1 2  and  T′ = 0 2 1 ,

and hence F_{η} has 2 irreducible components, of dimension n(λ) = 1. To be specific, let us take

η = ( \begin{matrix}0 & 1 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix} ) .

Calling the standard basis vectors e_{0}, e_{1}, e_{2} we have ker η = ⟨e_{0}, e_{2}⟩ and im η = ⟨e_{0}⟩, while η^{j} = 0 for j > 1. There are two Z_{u}-orbits of η-stable hyperplanes, namely the set U_{0}^{∗}(η) of all hyperplanes containing im η = ⟨e_{0}⟩ but not ker η = ⟨e_{0}, e_{2}⟩, and the singleton U_{1}^{∗}(η) = {⟨e_{0}, e_{2}⟩}. For any H ∈ U_{0}^{∗}(η) the fibre ω_{η}^{−1}(H) consists of a single flag f, with f_{1} = H ∩ ker η = ⟨e_{0}⟩ and of course f_{2} = H, so F_{η,T} is isomorphic to the affine line U_{0}^{∗}(η). On the other hand for H = ⟨e_{0}, e_{2}⟩ ∈ U_{1}^{∗}(η) we have η|_{H} = 0, whence an η-stable flag f with f_{2} = H can have an arbitrary element of P(H) as f_{1}, so in this case the fibre ω_{η}^{−1}(H), which coincides with F_{η,T′}, is a projective line. There is one element of F_{η,T′} that lies in the closure of F_{η,T}, namely the flag f with f_{1} = ⟨e_{0}⟩ and f_{2} = ⟨e_{0}, e_{2}⟩. Therefore, the whole variety F_{η} can be depicted as follows

3 Interpretation of the Schützenberger algorithm

\begin{aligned}& F_{η,T′} \\ F_{η,T} \end{aligned}

This illustration should be considered to lie in P_{1} × P_{1}, with the horizontal coordinate representing the choice of the hyperplane H = f_{2}, and the vertical coordinate representing the choice of the line f_{1}. By reasoning similar to that above, it can be seen that the fibre F_{η,T′}^{∗} of the morphism α_{η} is the horizontal line including the point of crossing, and F_{η,T}^{∗} is the remainder of the vertical line. So r_{η}(f) ≠ q_{η}(f) for all flags f ∈ F_{η}, except the flag represented by the crossing point of the lines, for which r_{η}(f) = q_{η}(f) = T′ = 0 2 1.

§3. Interpretation of the Schützenberger algorithm. We shall now proceed to show that the two given parametrisations of the irreducible components of F_{η} are related by the involution S of T_{λ} defined by the Schützenberger (evacuation) algorithm. In fact we shall give a more detailed description of the situation than this. We first recall the following two kinds of configurations of 4 partitions that can occur within the doubly indexed family of partitions that was used in [vLee3, 2.2] to give a description of the Schützenberger algorithm.

3.1. Definition. An arrangement of 4 partitions ({λ \atop μ′} {μ \atop ν}) with ν ≺ μ ≺ λ and ν ≺ μ′ ≺ λ is called

(i) a configuration of type S1 if μ = μ′ and (μ − ν) ∥ (λ − μ), (ii) a configuration of type S2 if μ ≠ μ′ (so that one has λ = μ ∪ μ′ and ν = μ ∩ μ′).

Note that the condition (μ − ν) ∥ (λ − μ) implies μ = μ′ (there are no other partitions between ν and λ), and that in the other case the two partitions μ, μ′ are the only ones between ν and λ. It follows that if ({λ \atop μ′} {μ \atop ν}) is known to be of type S1 or S2, then either one of μ or μ′ is uniquely determined by the other three partitions. The relevance of these configurations becomes clear when one considers for ν ≺ μ ≺ λ the following variety E_{η,μ,ν} of partial flags, consisting of only a line and hyperplane part:

E_{η,μ,ν} = { (l, H) ∈ P(V)_{η} × P^{∗}(V)_{η} | J(η|_{H}) = μ ∧ l ⊆ H ∧ J(η_{H/l}) = ν }.  (10)

3.2. Lemma. Let ν ≺ μ ≺ λ, and let μ′ be determined by the condition that ({λ \atop μ′} {μ \atop ν}) is of type S1 or S2. Then E_{η,μ,ν} is irreducible, and J(η_{/l}) = μ′ for (l, H) in a Z_{u}-stable dense open subset of E_{η,μ,ν}.

Proof. Put λ−μ = (i, j), μ−ν = (r, c); then E_{η,μ,ν} consists of those pairs (l, H) with H ∈ U_{j}^{∗}(η) and l ∈ U_{c}(η|_{H}), from which its irreducibility follows. If j = c or i = r, then ({λ \atop μ′} {μ \atop ν}) is of type S1, and J(η_{/l}) = μ′ is forced by ν ≺ J(η_{/l}) ≺ λ. If j ≠ c and i ≠ r, then ({λ \atop μ′} {μ \atop ν}) is of type S2; if moreover c ≠ j − 1, then U_{c}(η|_{H}) = U_{c}(η) follows from lemma 1.5 (4), so J(η_{/l}) = λ−(r, c) = μ′. In the final case that c = j−1 and r > i, we find for all H ∈ U_{j}^{∗}(η), again using lemma 1.5 (4), that U_{c}(η) = P(W_{c}(η))\P(W_{j}(η)) ≅ P_{r}\P_{i} is dense and open in U_{c}(η|_{H}) = P(W_{c}(η))\P(W_{j}(η|_{H})) ≅ P_{r} \P_{i−1} (with P_{−1} = ∅)), so the subset of E_{η,μ,ν} of pairs (l, H) for which l ∈ U_{c}(η) is dense and open, and on this set J(η_{/l}) = λ − (r, c) = μ′ holds.

3.3. Theorem. There is a dense open subset F′_{η} of F_{η}, such that for all f ∈ F′_{η} the following holds: if for i + j ≤ n one puts λ^{[i,j]} = J(η_{f_{n−j}/f_{i}}), then any configuration

( \begin{matrix}λ^{[i,j]} & λ^{[i,j+1]} \\ λ^{[i+1,j]} & λ^{[i+1,j+1]} \end{matrix} )

is either of type S1 or of type S2.

4 Interpretation of jeu de taquin, and Littlewood-Richardson tableaux

Proof. It will suffice to find for each T ∈ T_{λ} a dense open subset of F_{η,T} on which the stated condition holds. We use induction on n, with n = 1 as trivial starting case. Fix T ∈ T_{λ}, and let the family (λ^{[i,j]})_{i+j≤n} of partitions be defined by ch T = (λ^{[0,0]}, λ^{[0,1]}, …, λ^{[0,n]}), and by the condition on configurations in the statement of the theorem; we shall show that for appropriately chosen f ∈ F_{η,T} one has J(η_{f_{n−j}/f_{i}}) = λ^{[i,j]} for i + j ≤ n. Choose some H ∈ ω(F_{η,T}), then by the induction hypothesis applied to F_{η|_{H},T^{−}}, we have for f in a dense open subset of the fibre F_{η,T} ∩ ω_{η}^{−1}(H) that all instances of J(η_{f_{n−j}/f_{i}}) = λ^{[i,j]} with j > 0 hold. Since ω(F_{η,T}) is equal to some Z_{u}-orbit U_{c}^{∗}(η), this property extends by the action of Z_{u} to a Z_{u}-stable dense open subset U of F_{η,T}. By construction U is contained in { f ∈ F_{η,T} | (f_{1}, f_{n−1}) ∈ E_{η,μ,ν} }, which projects onto E_{η,μ,ν} with fibres that are all of dimension n(λ^{[1,1]}). It follows that U meets the inverse image under this projection of the dense open subset of E_{η,μ,ν} described in lemma 3.2. The intersection U′ of U with this inverse image is a Z_{u}-stable dense open subset of F_{η,T} on which the additional property J(η_{/f_{1}}) = λ^{[1,0]} holds. Then α(U′) is a single Z_{u}-orbit, and U′ intersects each fibre α_{η}^{−1}(l) for l ∈ α(U′) densely; the image of this intersection under f ↦ f^{↓} is a dense open subset of F_{η_{/l},T^{↓}}. The proof can now be completed by applying the induction hypothesis to F_{η_{/l},T^{↓}}.

3.4. Corollary. For all T ∈ T_{λ} one has \overline{F_{η,T}} = \overline{F_{η,S(T)}^{∗}}.

Proof. This follows immediately from the theorem, and the fact that the family λ^{[i,j]} with the mentioned properties can be used to compute S(T) (cf. the proof of [vLee3, theorem 2.2.1]).

The proof given for this geometric interpretation uses a description of S from which it obvious that S is an involution (in fact one that was used to prove this fact combinatorially). However, even if we forget the proof, the interpretation clearly implies that S is an involution, since f ∈ F_{η,T}^{∗} is equivalent to f^{∗} ∈ F_{η^{∗},T}, and f^{∗∗} = f. In combination with proposition 2.1, the corollary also implies that S(T) ∼ T^{⋄} for tableaux T of rectangular shape, as stated in [vLee3, Corollary 5.7]; in this case the geometric proof has no purely combinatorial counterpart (the proof given in [vLee3] is based on the relationship of the Schützenberger correspondence with the Robinson-Schensted correspondence). There is on the other hand one combinatorially obvious symmetry of S without any clear geometric meaning, namely the fact that it commutes with transposition (a geometric interpretation of this fact would require some operation that gives rise to transposition of Jordan types). Nevertheless, this symmetry of S will be important below, when we give geometric interpretations of the Robinson-Schensted correspondence and its transpose.

§4. Interpretation of jeu de taquin, and Littlewood-Richardson tableaux. The deflation procedure used in the Schützenberger algorithm is related to the operation of jeu de taquin (also known as glissement), which is performed on skew tableaux. Jeu de taquin can be described completely in terms of the deflation procedure [vLee3, §5], which allows us to deduce from theorem 3.3 an interpretation of jeu de taquin. That theorem does not mention tableaux or their entries directly however, but is stated in terms of families of partitions, and for our interpretation, all that matters about a skew tableau is the chain in P associated to it. For convenience we shall work directly with such chains, rather than with skew tableaux: we define a skew chain of shape λ/μ to be a saturated decreasing chain in P from λ to μ. We denote the set of all skew chains of shape λ/μ by T_{λ/μ}; the set T_{λ} is in bijection with T_{λ/∅} by P ↦ ch P.

We proceed to give a geometric interpretation to skew chains, in analogy to the definition of F_{η,T} for Young tableaux T. Let G_{m}^{η} be the variety of m-dimensional η-stable subspaces of V, and let F_{η}^{(m)} be the set of η-stable partial flags in V with parts in dimensions m and higher, i.e., of chains f = (f_{m} ⊂ f_{m+1} ⊂ ⋯ ⊂ f_{n}) with f_{i} ∈ G_{i}^{η}. For f ∈ F_{η}^{(m)} the part f_{m} of minimal dimension will be denoted by ⌊f⌋, and we define the complete flag \overline{f} = (f_{m}/⌊f⌋ ⊂ ⋯ ⊂ f_{n}/⌊f⌋) ∈ F_{η_{/⌊f⌋}} by reducing all parts of f modulo ⌊f⌋. We also define r_{η}(f) = (J(η), J(η|_{f_{n−1}}), …, J(η|_{⌊f⌋})) ∈ T_{λ/μ} where μ = J(η|_{⌊f⌋}), and put

F_{η,K} = { f ∈ F_{η}^{(m)} | r_{η}(f) = K }.  (11)

4.1. Proposition. F_{η,K} is an irreducible variety for every K ∈ T_{λ/μ}, and dim(F_{η,K}) = n(λ) − n(μ).

Proof. The proof is entirely analogous to that of parts (a) and (b) of proposition 2.2, the only difference being that the induction starts at |λ| = |μ| rather than at |λ| = 0.

For a Young tableau T ∈ T_{λ}, let T_{<m} denote its subtableau of entries less than m; putting μ = sh T_{<m}, let T_{≥m} ∈ T_{λ/μ} denote the subchain (sh T, sh T^{−}, …, μ) of ch T corresponding to the remaining entries. If we denote by T^{↓∗i} the result of applying the deflation procedure i times to T, then the relation K ▷ K′ of glissement (K′ is obtainable from K by inward jeu de taquin slides) is defined in [vLee3, §5] by restricting T and T^{↓∗i} to skew subtableaux with the same set of entries. The corresponding definition for skew chains is that T_{≥m} ▷ T^{↓∗i}_{≥m} for i ≤ m. We obtain from theorem 3.3:

4.2. Corollary. Let K ∈ T_{λ/μ} be a skew chain, and let P ∈ T_{ν} be a Young tableau such that K ▷ ch P. Then there is a dense open subset F′_{η,K} of F_{η,K} such that r_{η_{/⌊f⌋}}(\overline{f}) = P for all f ∈ F′_{η,K}.

Proof. Since K ▷ ch P, there exists a T ∈ T_{λ} with K = T_{≥m} and P ∼ T^{↓∗m}. Let p denote the natural projection F_{η,T} → F_{η,K} (which is clearly surjective), and take F′_{η,K} = p(F_{η,T} ∩ F′_{η}), where F′_{η} is as in theorem 3.3; the conclusion of that theorem immediately implies r_{η_{/⌊f⌋}}(\overline{f}) = P for f ∈ F′_{η,K}.

In this geometric interpretation, confluence of jeu de taquin is obvious: P is uniquely determined by K. We now partition G_{m}^{η} according to the type and cotype of its elements: for μ ∈ P_{m}, ν ∈ P_{n−m} put

G_{μ,ν}^{η} = { X ∈ G_{m}^{η} | J(η|_{X}) = μ ∧ J(η_{/X}) = ν };  (12)

furthermore, denote by T_{λ/μ}^{▷ν} the set of K ∈ T_{λ/μ} such that K ▷ ch P for some P ∈ T_{ν}.

4.3. Theorem. Denote by π: F_{η}^{(m)} → G_{m}^{η} the morphism defined by π(f) = ⌊f⌋. Let μ ∈ P_{m} and ν ∈ P_{n−m}.

(1) If K ∈ T_{λ/μ}^{▷ν}, then the image π(F′_{η,K}) of the set F′_{η,K} of corollary 4.2 is dense in an irreducible component of G_{μ,ν}^{η} of dimension n(λ; μ, ν) =^{def} n(λ) − n(μ) − n(ν). Moreover, any such component is so obtained as π(\overline{F_{η,K}}) ∩ G_{μ,ν}^{η} for at least one K ∈ T_{λ/μ}^{▷ν}, and there are no components of higher dimension.

(2) The number of irreducible components of G_{μ,ν}^{η} of dimension n(λ; μ, ν) is equal to the Littlewood-Richardson coefficient c_{μ,ν}^{λ}, and they can be explicitly parametrised by the Littlewood-Richardson tableaux of shape λ/μ and weight ν.

(3) For K, L ∈ T_{λ/μ}^{▷ν}, the irreducible components π(\overline{F_{η,K}}) ∩ G_{μ,ν}^{η} and π(\overline{F_{η,L}}) ∩ G_{μ,ν}^{η} of G_{μ,ν}^{η} are equal if and only if K and L are dual equivalent in the sense of [Haim].

Limiting itself to what can be deduced from corollary 4.2, the theorem avoids any statement about possible irreducible components of G_{μ,ν}^{η} of dimension less than n(λ; μ, ν). However, we shall show below that such components do not exist, and so an accordingly simplified and strengthened form of the theorem does in fact hold. Proof. (1) It is clear that π^{−1}(G_{μ,ν}^{η}) ⊆ _{⋃K∈T_{λ/μ}}F_{η,K}, whose components have dimension n(λ) − n(μ), while the fibre π^{−1}(X) at any X ∈ G_{μ,ν}^{η} is isomorphic to F_{η_{/X}}, whose components have dimension n(ν). Therefore any irreducible component C of G_{μ,ν}^{η} can have dimension at most n(λ; μ, ν), and when it has this dimension, π^{−1}(C) is dense in some union of sets F_{η,K} with K ∈ T_{λ/μ}. By corollary 4.2 one has π(F′_{η,K}) ⊆ G_{μ,ν}^{η} whenever K ∈ T_{λ/μ}^{▷ν}, from which the claims follow.

(2) Corollary 4.2 also implies that if K ▷ ch P, then F_{η,K} meets any fibre π^{−1}(X) with X ∈ π(F′_{η,K}) in the irreducible component of that fibre that corresponds to F_{η_{/X},P}; hence, fixing an arbitrary P ∈ T_{ν}, the irreducible components of G_{μ,ν}^{η} of dimension n(λ; μ, ν) correspond bijectively to the skew chains K ∈ T_{λ/μ}^{▷ν} with K ▷ ch P. The number of such K is known to be independent of the choice of P ([Schü2, (3.7)]) and equal to c_{μ,ν}^{λ} ([Schü2, (4.7)], see also [vLee4, Theorem 5.2.5]). In fact there is a specific P ∈ T_{ν} for which the Littlewood-Richardson tableaux T of shape λ/μ and weight ν correspond directly to the skew chains K ∈ T_{λ/μ}^{▷ν} with K ▷ ch P. To associate a skew chain K to a semistandard skew tableau T, one uses the well known process of standardisation: its sequence of partitions, starting at λ, is found by removing the squares of T by decreasing entries, and among squares with equal entries from right to left. Jeu de taquin is defined for semistandard tableaux in such a way that it commutes with this standardisation, and it preserves the property of being a Littlewood-Richardson tableau. The indicated special tableau P ∈ T_{ν} is such that ch P is the standardisation of the tableau T_{ν} of shape ν in which each row i is filled with entries i (T_{ν} is the unique Littlewood-Richardson tableau of shape ν, and it has weight ν). Then K ∈ T_{λ/μ} is the standardisation of a Littlewood-Richardson tableau T of weight ν if and only if K ▷ ch P.

(3) Define for K, L ∈ T_{λ/μ}^{▷ν} the equivalence relation K ≡ L to mean π(\overline{F_{η,K}}) ∩ G_{μ,ν}^{η} = π(\overline{F_{η,L}}) ∩ G_{μ,ν}^{η}. We have established above that for any P ∈ T_{ν} the jeu de taquin equivalence class { K ∈ T_{λ/μ}^{▷ν} | K ▷ ch P } is a set of representatives of the classes for ‘≡’. As the members of such a jeu de taquin equivalence class are mutually dual inequivalent (this is the easy part of [Haim, theorem 2.13]), it will suffice to prove that K ≡ L implies the dual equivalence of K and L. We shall establish this by finding a sequence of jeu de taquin slides that transforms K and L respectively into K′, L′ ∈ T_{ν/∅}, preserving equality of shapes at each step; being (chains corresponding to) Young tableaux of the same shape, K′ and L′ will be dual equivalent [Haim, corollary 2.5], which implies dual equivalence of K and L. Since K ≡ L, it is possible to choose partial flags f ∈ F′_{η,K} and f′ ∈ F′_{η,L} with ⌊f⌋ = ⌊f′⌋; by extending f and f′ identically with suitably chosen parts in dimensions less than m, one obtains flags f̂, f̂′ ∈ F′_{η} such that T = r_{η}(f̂) and U = r_{η}(f̂′) satisfy T_{≥m} = K, U_{≥m} = L, and T_{<m} = U_{<m}. Then for i ≤ m the shapes of the skew chains T^{↓∗i}_{≥m} and U^{↓∗i}_{≥m} are both equal to J(η_{/f̂_{i}})/J(η_{⌊f⌋/f̂_{i}}) (since f̂_{i} = f̂′_{i}), which gives the required sequence of slides transforming K and L respectively into K′ = ch T^{↓∗m} and L′ = ch U^{↓∗m}.

The detailed statement of the theorem appears to be new. However, the relation between G_{μ,ν}^{η} and Littlewood-Richardson coefficients was already indicated in [Spr1, Theorem 4.4]. The setting there is in fact more general, with a semi-simple linear algebraic group G replacing GL_{n}; correspondingly, G_{μ,ν}^{η} is replaced by a variety X′_{A,B}(P) of parabolic subgroups, and Littlewood-Richardson coefficients by decomposition multiplicities for representations induced from the Weyl group W′ of a Levi factor of P to the Weyl group W of G. (Our theorem corresponds only to maximal parabolic P, but can be extended easily so as to correspond to arbitrary parabolic subgroups.) The number of irreducible components of G_{μ,ν}^{η} of dimension n(λ; μ, ν) appears in a somewhat disguised form, as a decomposition multiplicity n_{A,B,ϕ,ψ} for a permutation action of a group C_{G}(A) × C_{G}(B) on the set of irreducible components of X′_{A,B}(P) of that dimension; for GL_{n}, the group C_{G}(A)×C_{G}(B) is always trivial, and n_{A,B,ϕ,ψ} reduces to the number of components acted (trivially) upon.

Another, rather weaker, connection between the Littlewood-Richardson rule and the geometry of F_{η} was indicated in [Sri]. Its main theorem (4.2) corresponds to our corollary 4.2, but it is stated (and proved) in a somewhat roundabout fashion in terms of permutations, whose link to geometry is formed by Steinberg’s interpretation of the Robinson-Schensted correspondence (which will be discussed below). In fact, that theorem itself involves no geometry at all, and it can be proved in a purely combinatorial manner. Since only a fixed maximal parabolic subgroup P is considered, no connection with the geometry of G_{μ,ν}^{η} is indicated; the Littlewood-Richardson coefficients, which arise in relation to jeu de taquin in the same way as above, are only given their traditional representation theoretic interpretation.

As we have seen, dual equivalence classes in T_{λ/μ}^{▷ν} are in bijection with Littlewood-Richardson tableaux of shape λ/μ and weight ν. Once the latter have all been determined, one can construct the set { K ∈ T_{λ/μ}^{▷ν} | K ▷ ch P } effectively, not just for the special tableau P indicated in the proof above, but for any given P ∈ T_{ν}. Such a construction is given in the proof of [vLee4, Theorem 5.2.5] in terms of the Robinson-Schensted correspondence for “pictures”; we shall formulate it here without using pictures. One associates to any skew chain K ∈ T_{λ/μ} a permutation w(K) by concatenating the rows of the skew tableau corresponding to K, taking them in order from bottom to top. Call the two Young tableaux (P, Q) = RS(w(K)) the P -symbol and Q-symbol of K; then the P -symbol of K characterises its jeu de taquin equivalence class (indeed K ▷ ch P), and the Q-symbol its dual equivalence class. Whenever c_{μ,ν}^{λ} > 0, all tableaux in T_{ν} occur as P -symbol of some K ∈ T_{λ/μ}^{▷ν}, but not necessarily as Q-symbol. The set of tableaux that do so occur, is precisely the set Q(λ/μ, ν) of Q-symbols of Littlewood-Richardson tableaux of shape λ/μ and weight ν (where the Q-symbol of a semistandard skew tableau is defined either as the Q-symbol of its standardisation, or directly by concatenating its rows and applying the version of the Schensted algorithm that allows repeated entries; either way the Q-symbol is a standard tableau). One then has

{ w(K) | K ∈ T_{λ/μ}^{▷ν} ∧ K ▷ ch P } = { RS^{−1}(P, Q) | Q ∈ Q(λ/μ, ν) },  (13)

from which the desired set of skew chains K is readily reconstructed.

Now as promised we shall rule out the possibility that G_{μ,ν}^{η} could have irreducible components of dimension less than n(λ; μ, ν), which implies in particular that G_{μ,ν}^{η} = ∅ whenever c_{μ,ν}^{λ} = 0. This requires an algebraic construction that associates a Littlewood-Richardson tableau to any individual element X ∈ G_{μ,ν}^{η}. We essentially use the construction described in [Macd, II 3], but since our context is dual to the one considered there, we shall present an adapted version of the construction and proof.

5 Relative positions of flags

4.4. Proposition. For any λ, μ, ν ∈ P, the irreducible components of G_{μ,ν}^{η} are precisely those described in theorem 4.3, i.e., G_{μ,ν}^{η} has no irreducible components of dimension less than n(λ; μ, ν).

Proof. We shall construct for any X ∈ G_{μ,ν}^{η} a tableau K ∈ T_{λ/μ}^{▷ν} with X ∈ π(F_{η,K}); then X lies in the component π(\overline{F_{η,K}}) ∩ G_{μ,ν}^{η}, and the proposition follows. Fix X ∈ G_{μ,ν}^{η}, and for i ∈ N put X_{i} = η^{−i}(X) and μ^{i} = J(η|_{X_{i}}) (in particular μ^{0} = μ and μ^{ν_{0}} = λ). By filling each skew diagram Y (μ^{i+1}) \ Y (μ^{i}) with entries i we obtain the transpose of a semistandard tableau T of shape λ^{t}/μ^{t} and weight ν^{t} (by proposition 1.2, since J(η_{/X}) = ν); we claim that T is a Littlewood-Richardson tableau (i.e., T ▷ T_{ν^{t}}). Assuming this for the moment, the transposes K ∈ T_{λ/μ} and P ∈ T_{ν/∅} of the standardisations of T and T_{ν^{t}} satisfy K ▷ P (jeu de taquin commutes with transposition), so K ∈ T_{λ/μ}^{▷ν}. To show that X ∈ π(F_{η,K}), it suffices to extend the sequence of subspaces X_{0} ⊂ X_{1} ⊂ ⋯ ⊂ X_{ν_{0}} by interpolation to some f ∈ F_{η,K}. Now η acts as 0 on each of the quotient spaces X_{i+1}/X_{i}, so any choice of complete flags in those spaces leads to a f ∈ F_{η}^{(m)}, which has moreover the property that all partitions μ^{i} occur in the chain r_{η}(f); we only need to show that it is possible to obtain r_{η}(f) = K. In fact, among the irreducible set of choices for f, a dense subset has r_{η}(f) = K; this follows from the observation that for any subspace V′ ⊇ im η, the projective space S = { H ∈ P^{∗}(V)_{η} | H ⊇ V′ } meets U_{j}^{∗}(η) whenever the vertical strip Y (λ) \ Y (J(η|_{V′})) meets column j, and then of course the intersection is dense in S for the minimal such j.

It remains to show that T is a Littlewood-Richardson tableau. That T is a semistandard tableau means that each Y (μ^{i+1}) \ Y (μ^{i}) is a vertical strip, or equivalently (μ^{i+1})_{c}^{t} ≥ (μ^{i})_{c}^{t} ≥ (μ^{i+1})_{c+1}^{t} for i, c ∈ N; this follows from the easily verified inclusions W_{c}(η|_{X_{i+1}}) ⊇ W_{c}(η|_{X_{i}}) ⊇ W_{c+1}(η|_{X_{i+1}}). The remaining conditions for T to be a Littlewood-Richardson tableau can be formulated in several equivalent ways, but the following will be practical here, in view of proposition 1.1: denoting by T (i, c) the number of entries i in the first c rows of T, one should have T (i + 1, c + 1) ≤ T (i, c) for i, c ∈ N (this implies T (i, c) = 0 when i ≥ c). Now T (i, c) is the difference between the number of squares in the first c columns of Y (μ^{i+1}) and of Y (μ^{i}); putting X_{i}^{c} = ker(η|_{X_{i}})^{c} = X_{i} ∩ ker η^{c}, we therefore have by proposition 1.1 that T (i, c) = dim X_{i+1}^{c} − dim X_{i}^{c} = dim(X_{i+1}^{c}/X_{i}^{c}). Now for all i, c one has η^{−1}(X_{i}^{c}) = X_{i+1}^{c+1}, whence η induces an injective map X_{i+2}^{c+1}/X_{i+1}^{c+1} → X_{i+1}^{c}/X_{i}^{c}, giving the required inequality T (i+1, c+1) ≤ T (i, c).

§5. Relative positions of flags. Besides the use mentioned above of the Robinson-Schensted algorithm as a computational aid in dealing with classes of jeu de taquin equivalence and dual equivalence, there is also a direct geometric interpretation, due to Steinberg, of the correspondence defined by it. To formulate it, we need to attach a geometric meaning to permutations; this meaning will be derived from the fact that permutations of n parametrise the orbits for the diagonal action of GL_{n} on F × F. This parametrisation can be defined by associating to each pair (f, f′) of flags a permutation called the relative position of f and f′ that will characterise the GL_{n}-orbit of (f, f′). By definition σ ∈ S_{n} is the relative position of f and f′ if there exists a basis e_{0}, …, e_{n−1} of V such that f_{i} = ⟨e_{0}, …, e_{i−1}⟩ and f′_{i} = ⟨e_{σ_{0}}, …, e_{σ_{i−1}}⟩ for all i ≤ n. The fact that there always exists a unique such σ is the essence of Bruhat’s lemma for GL_{n}, but it is useful to give here an explicit demonstration of this fact. We shall use the auxiliary concept of a growth matrix.

5.1. Definition. A growth matrix of order n is a matrix (A_{i,j})_{0≤i,j≤n} with entries in N satisfying a. A_{i,0} = A_{0,i} = 0 and A_{i,n} = A_{n,i} = i for 0 ≤ i ≤ n, b. A_{i+1,j} − A_{i,j} ∈ {0, 1} and A_{i,j+1} − A_{i,j} ∈ {0, 1} for 0 ≤ i, j < n, c. A_{i+1,j+1} = A_{i,j+1} ⇒ A_{i+1,j} = A_{i,j} for 0 ≤ i, j < n (or equivalently, A_{i+1,j+1} = A_{i+1,j} ⇒ A_{i,j+1} =

A_{i,j}).

Growth matrices of order n correspond bijectively to permutations of n: for a growth matrix A = (A_{i,j})_{0≤i,j≤n}, the corresponding permutation σ(A) ∈ S_{n} has a permutation matrix Π (given by Π_{i,j} = δ_{i,σ(A)_{j}} for 0 ≤ i, j < n) that is related to A by the equivalent relations

Π_{i,j} = A_{i+1,j+1} − A_{i+1,j} − A_{i,j+1} + A_{i,j}  for 0 ≤ i, j < n,  (14)
A_{i,j} = ∑_{0≤i′<i} ∑_{0≤j′<j} Π_{i′,j′}  for 0 ≤ i, j ≤ n.  (15)

6 Interpretation of the Robinson-Schensted algorithm

We define π(f, f′) = σ(A), where the growth matrix A is given by A_{i,j} = dim(f_{i} ∩ f′_{j}). From the definition it follows that if σ is the relative position of f and f′, then π(f, f′) = σ; in particular σ is unique. Conversely, for σ = π(f, f′), a basis e_{0}, …, e_{n−1} witnessing the fact that σ is the relative position of f and f′ can be constructed: for each i put j = σ_{i}^{−1} (so that Π_{i,j} = 1) and choose for e_{i} any vector in the complement of the subspace f_{i} ∩ f′_{j} within f_{i+1} ∩ f′_{j+1} (by the construction of σ this subspace is a hyperplane, and equal to both f_{i+1} ∩ f′_{j} and f_{i} ∩ f′_{j+1}). As an example, if f = f′, then A_{i,j} = min(i, j), whence π(f, f′) is the identity permutation; at the other extreme, when f and f′ are in general position one has A_{i,j} = max(0, i + j − n), whence π(f, f′) = ñ, the order reversing permutation. Remark. Besides the mentioned growth matrix A, growth matrices B, C, and D can also be associated to (f, f′) with B_{i,j} = dim(f_{i}/(f_{i} ∩ f′_{n−j})), C_{i,j} = dim(f′_{j}/(f_{n−i} ∩ f′_{j})), and D_{i,j} = dim(V/(f_{n−i} + f′_{n−j})). Putting σ = σ(A) = π(f, f′), it can easily be verified that σ(B) = σñ, σ(C) = ñσ, and σ(D) = ñσñ. Since dim(V/(f_{n−i}+f′_{n−j})) = dim(f_{i}^{∗}∩f_{j}^{′∗}), the last case implies that the relative position of the dual flags is obtained by conjugation by ñ: π(f^{∗}, f^{′∗}) = ñπ(f, f′)ñ. It is also obvious that π(f′, f) = π(f, f′)^{−1}. Remark. The Bruhat order ‘≤’ on S_{n} can be defined in terms the associated growth matrices: if σ = σ(A) and σ′ = σ(A′), then one has σ ≤ σ′ if and only if A_{i,j} ≥ A′_{i,j} for all i, j. It follows that for any σ ∈ S_{n}, the closure of { (f, f′) | π(f, f′) = σ } in F × F is { (f, f′) | π(f, f′) ≤ σ }.

§6. Interpretation of the Robinson-Schensted algorithm. In this section we shall demonstrate the result, due to Steinberg, that for a pair of flags generically chosen in irreducible components of F_{η} parametrised by a pair of standard Young tableaux, their relative position is related to those tableaux by the Robinson-Schensted correspondence. Like the interpretation of the Schützenberger correspondence, this will be deduced from a more detailed statement, that gives an interpretation of all the partitions in the doubly indexed family describing the algorithm; in the current case that family is the one of [vLee3, 3.2]. We recall the basic configurations that can occur.

6.1. Definition. An arrangement of 4 partitions ({ν \atop μ′} {μ \atop λ}) is called

(i) a configuration of type RS1 if ν = μ = μ′ ≺ λ and μ_{0} = λ_{0} − 1, (ii) a configuration of type RS2 if ν ≺ μ = μ′ ≺ λ, with μ_{i+1} = λ_{i+1} − 1 and ν_{i} = μ_{i} − 1 for some i ≥ 0, (iii) a configuration of type RS3 if ν ≺ μ ≺ λ, ν ≺ μ′ ≺ λ, and μ ≠ μ′, (iv) a configuration of type RS0 if ν = μ ⪯ μ′ = λ or ν = μ′ ⪯ μ = λ.

6.2. Definition. A family of partitions (λ^{[i,j]}), where i and j each range over an interval of Z, is said to be of type RS if any configuration ({λ^{[i,j]} \atop λ^{[i+1,j]}} {λ^{[i,j+1]} \atop λ^{[i+1,j+1]}} ) is of one of the types RS0–RS3.

Families of type RS were used in the proof of [vLee3, theorem 3.2.1] to relate a permutation σ and the pair (P, Q) = RS(σ) of tableaux computed from it by the Robinson-Schensted algorithm. The pair (P, Q) describes the partitions at the boundary of the family, while σ describes the places where a configuration of type RS1 occurs; specifying either of these suffices to determine the entire family. More precisely, to a family (λ^{[i,j]})_{0≤i,j≤n} of type RS with λ^{[n,n]} = λ, we associate tableaux P, Q ∈ T_{λ} such that ch P = (λ^{[n,n]}, λ^{[n−1,n]}, …, λ^{[0,n]}) and ch Q = (λ^{[n,n]}, λ^{[n,n−1]}, …, λ^{[n,0]}), and a permutation σ = σ(A) where A is the growth matrix with A_{i,j} = |λ^{[i,j]}|, which means that i = σ_{j} if and only if ({λ^{[i,j]} \atop λ^{[i+1,j]}} {λ^{[i,j+1]} \atop λ^{[i+1,j+1]}} ) is of type RS1. (In its relation to P, Q, and σ, our family has its indices interchanged with respect to [vLee3]; it remains of type RS, and it still establishes the relation (P, Q) = RS(σ).)

6.3. Theorem. Let P, Q ∈ T_{λ}, and σ ∈ S_{n} with (P, Q) = RS(σ). Then for all (f, f′) in a dense open subset of F_{η,P} × F_{η,Q}, the family J(η|_{f_{i}∩f′_{j}})_{0≤i,j≤n} is of type RS, and in particular π(f, f′) = σ.

6.4. Lemma. Let μ, μ′ ≺ λ, and let ν be determined by the condition that ({ν \atop μ′} {μ \atop λ}) is of one of the types RS1–RS3. For any H_{0} ∈ P^{∗}(V)_{η} with J(η|_{H_{0}}) = μ′, there is a dense open subset of { H ∈ P^{∗}(V)_{η} | J(η|_{H}) = μ } on which J(η|_{H∩H_{0}}) = ν holds.

Proof. If μ ≠ μ′ the configuration is of type RS3, and it follows from proposition 1.2 that one always has J(η|_{H∩H_{0}}) = ν = μ ∩ μ′. Assume now that μ = μ′, and let λ − μ = (i, j), so that H ranges over the set U_{j}^{∗}(η), which has dimension i. If i = 0 the configuration is of type RS1 and U_{j}^{∗}(η) = {H_{0}}, so that for the unique choice H = H_{0} one has J(η|_{H∩H_{0}}) = J(η|_{H}) = μ = ν. Finally, if i > 0, the configuration is of type RS2. We claim that intersection with H_{0} defines a surjective morphism \overline{U_{j}^{∗}(η)} \ \{H_{0}\} → \overline{U_{j′}^{∗}(η|_{H_{0}})}, where μ − ν = (i − 1, j′): the lemma then follows by taking for the dense open subset of U_{j}^{∗}(η) the intersection of U_{j}^{∗}(η) with the inverse image of U_{j′}^{∗}(η|_{H_{0}}). To prove the claim, observe that restriction to H_{0} defines a linear map W_{j}^{∗}(η) → W_{j}^{∗}(η|_{H_{0}}) = W_{j′}^{∗}(η|_{H_{0}}), the surjectivity of which follows from lemma 1.5 (3), or from a dimension consideration.

We note that in the final case each of the fibres of the indicated map \overline{U_{j}^{∗}(η)} \ \{H_{0}\} → \overline{U_{j′}^{∗}(η|_{H_{0}})} meets U_{j}^{∗}(η), whence the restriction of that map to U_{j}^{∗}(η)\{H_{0}} is still surjective. This means that in this case any partition obtained from μ by removing a corner in some column c > j′ can arise as J(η|_{H∩H_{0}}) for some non-generic H ∈ U_{j}^{∗}(η); of course, by taking H = H_{0} one can obtain J(η|_{H∩H_{0}}) = μ as well.

The lemma can also be formulated as follows: putting (i, j) = λ − μ and (i′, j′) = μ′ − ν, one has for H in a dense subset of U_{j}^{∗}(η) that H ∩ H_{0} ∈ U_{j′}^{∗}(η|_{H_{0}}). It is not true in general, however, that as H traverses this subset of U_{j}^{∗}(η), the values H ∩ H_{0} traverse a dense subset of U_{j′}^{∗}(η|_{H_{0}}). The reason for this is that within H_{0} equipped with η|_{H_{0}}, the subspace im η is in no way special (it is not fixed under automorphisms), yet H ∩ H_{0} always contains it (because both H_{0} and H do so). Although in some cases it can be shown that all hyperplanes in U_{j′}^{∗}(η|_{H_{0}}) contain im η, there are also cases where this is not so. This circumstance makes the proof of theorem 6.3 more difficult than that of theorem 3.3. There are however no difficulties in extending lemma 6.4 as follows.

6.5. Lemma. Fix an arbitrary flag f′ ∈ F_{η} and P ∈ T_{λ}; for all f in a dense open subset of F_{η,P}, the subfamily of J(η|_{f_{i}∩f′_{j}})_{0≤i,j≤n} determined by j ∈ {n − 1, n} is of type RS.

Clearly only the hyperplane part H = f′_{n−1} of f′ is relevant here. The sequence of subspaces f_{i} ∩ H forms a complete η|_{H}-stable flag in H, except that one part is repeated. Denoting this flag (without the repetition) by f ∩ H, the lemma states that for generic f ∈ F_{η,P} one has f ∩ H ∈ F_{η|_{H},P′} and f_{i_{0}} ∩H = f_{i_{0}+1} ∩H, where P′ and i_{0} are found by applying Schensted extraction (reverse insertion) to P, starting at the square λ − J(η|_{H}) (recall that the entries of P start at 0).

Proof. We apply induction on n. Put (λ^{n}, …, λ^{0}) = ch P (so that λ^{i} = J(η|_{f_{i}})), and μ^{i} = J(η|_{f_{i}∩H}). Applying lemma 6.4 with μ′ = μ^{n}, μ = λ^{n−1}, and H_{0} = H, we get for f_{n−1} in a dense open subset U of ω(F_{η,P}) that ({μ^{n−1} \atop μ^{n}} {λ^{n−1} \atop λ^{n}} ) is of one of the types RS1–RS3. If it is of type RS1, then f_{n−1} = H for all f ∈ F_{η,P}, so that μ^{i} = λ^{i} for i < n, and the remaining configurations ({μ^{i} \atop μ^{i+1}} {λ^{i} \atop λ^{i+1}} ) (0 ≤ i < n − 1) are of type RS0. Otherwise we fix any K ∈ U and consider the fibre ω^{−1}(K); the remaining configurations are then taken care of by induction applied to η|_{K} and K ∩ H in place of η and H, respectively.

This lemma does not suffice as an induction step for the proof of theorem 6.3. The induction hypothesis will describe the generic relative position of the pair formed by a flag in F_{η|_{H},P′} and f^{′−}, but for reasons indicated above, the set of flags f ∩ H is not generally dense in F_{η|_{H},P′}, and it is conceivable that the generic relative position of f ∩ H and f^{′−} is different (smaller in the Bruhat order). In order to dispell this possibility, we shall show that it is possible to write generic flags f ∈ F_{η|_{H},P′} as f̂∩H for some f̂ ∈ F_{η̂,P}, where η̂ is another nilpotent transformation of V than η, but with J(η̂) = λ and η̂|_{H} = η|_{H}. To that end, we shall now consider the reverse process of restricting a nilpotent transformation to a hyperplane. Let 0 ≤ i_{0} ≤ n and define the following vector bundle over F_{η,T}:

F_{η,T,i_{0}} = { (f, v) ∈ F_{η,T} × V | v ∈ f_{i_{0}} }.  (16)

Clearly F_{η,T,i_{0}} is stable under the diagonal Z_{u}-action on F_{η,T} ×V. For any (f, v) ∈ F_{η,T,i_{0}} we define in the n+1-dimensional space V ×k a nilpotent transformation η̂ and a flag f̂, as follows. Let e = (0_{V} , 1) ∈ V ×k, then η̂ is determined by η̂|_{V} = η and η̂(e) = v, and f̂ is defined by

f̂_{i} = \{ \begin{matrix}f_{i} & if 0 ≤ i ≤ i_{0}, \\ f_{i−1} ⊕ ⟨e⟩ & if i_{0} ≤ i − 1 ≤ n. \end{matrix}  (17)

It follows from v ∈ f_{i_{0}} that f̂ is η̂-stable.

6.6. Lemma. Let T ∈ T_{λ} and 0 ≤ i_{0} ≤ n. For all (f, v) in a dense open subset of F_{η,T,i_{0}}, the associated η̂ and f̂ satisfy the following property: with ν^{i} = J(η̂|f̂_{i}) and λ^{i} = J(η|_{f̂_{i}∩V}) for 0 ≤ i ≤ n + 1, any configuration of the form ({λ^{i} \atop λ^{i+1}} {ν^{i} \atop ν^{i+1}} ) is of type RS0 if i < i_{0}, of type RS1 if i = i_{0}, and of type RS2 or RS3 if i > i_{0}.

Proof. One has ch T = (λ^{n+1}, …, λ^{i_{0}+1} = λ^{i_{0}}, …, λ^{0}), since f̂_{i} ∩ V is f_{i} if i ≤ i_{0}, and f_{i−1} otherwise. Then the unique sequence of partitions ν^{i} for which the given conditions on configurations hold is readily constructed; we shall take this as definition of ν^{i}, and show that J(η̂|f̂_{i}) = ν^{i} holds for 0 ≤ i ≤ n + 1, provided (f, v) is chosen in an appropriate set. The statement for i < i_{0} is immediate. For the remaining statements we shall apply induction on n (fixing i_{0}), starting at n = i_{0}. Put ν = ν^{n+1} and let ν−λ = (r, c); then by lemma 1.5 (2), the statement J(η̂) = ν means that c is the minimal value with v ∈ im η+ker η^{c}. For n = i_{0} one has F_{η,T,i_{0}} = F_{η,T} ×V, r = 0, and c = ν_{0}^{t}, which is the least value for which im η +ker η^{c} = V (in fact ker η^{c} = V), so the subset of F_{η,T,i_{0}} of pairs (f, v) for which J(η̂) = ν is dense and open.

As preparation for the induction step, note that the statement of the lemma implies that the smallest subspace of V containing im η and all values v for generic (and hence for all) (f, v) ∈ F_{η,T,i_{0}}, which is necessarily Z_{u}-stable, equals im η + ker η^{c}. Now assume n > i_{0}, and choose an arbitrary hyperplane H ∈ ω(F_{η,T}). Defining ω̂: F_{η,T,i_{0}} → P^{∗}(V) by ω̂(f, v) = ω(f), it will suffice to show that the property in the lemma holds in a dense open subset of ω̂^{−1}(H) ≅ F_{η|_{H},T^{−},i_{0}}, as one can then use the action of Z_{u} to extend this subset to one of F_{η,T,i_{0}}. The induction hypothesis gives a dense open subset U of ω̂^{−1}(H) on which J(η̂|f̂_{i}) = ν^{i} for 0 ≤ i ≤ n; it remains to show that generically one also has J(η̂) = ν. If ν^{n} ≠ λ then this holds on all of U by proposition 1.2. Otherwise ({λ^{n} \atop λ} {ν^{n} \atop ν} ) is of type RS2; let ν^{n} − λ^{n} = λ − λ^{n} = (r − 1, c′). By the induction hypothesis, the smallest subspace of H containing { v | (f, v) ∈ U } is im(η|_{H}) + ker(η|_{H})^{c′}. Moreover, since H ∈ U_{c′}^{∗}(V) this is equal to im η + ker η^{c′} by lemma 1.5 (3), and since c = λ_{r} is the largest part ≤ c′ of λ, also to im η + ker η^{c}. If c = 0 one has J(η̂) = ν on all of U; otherwise this holds on the open subset { (f, v) ∈ U | v ∉ im η + ker η^{c−1} }, which is non-empty (since λ_{r} = c implies dim(im η + ker η^{c−1}) < dim(im η + ker η^{c})) and therefore dense.

We have now collected all the ingredients necessary to proceed with an inductive proof of theorem 6.3. Proof of theorem 6.3. For n < 2 the theorem is obvious, so assume n ≥ 2; we shall prove that for any choice of H ∈ ω(F_{η,Q}), the family J(η|_{f_{i}∩f′_{j}})_{0≤i,j≤n} is of type RS, for (f, f′) in a dense open subset of φ(H) = F_{η,P} × (ω^{−1}(H) ∩ F_{η,Q}). Let P′ and i_{0} be the result of applying Schensted extraction to P starting at square λ^{[n,n]} − λ^{[n,n−1]}, so that ch(P′) = (λ^{[n,n−1]}, …, λ^{[i_{0}+1,n−1]} = λ^{[i_{0},n−1]}, …, λ^{[0,n−1]}). Lemma 6.5 provides a dense open subset U′ of φ(H) on which the configurations ({λ^{[i−1,n−1]} \atop λ^{[i,n−1]}} {λ^{[i−1,n]} \atop λ^{[i,n]}} ) are all of the required types, which implies f ∩H ∈ F_{η|_{H},P′}. On the other hand the induction hypothesis provides a dense open subset U′′ of F_{η|_{H},P′} × F_{η|_{H},Q^{−}} such that remaining configurations ({λ^{[i−1,j−1]} \atop λ^{[i,j−1]}} {λ^{[i−1,j]} \atop λ^{[i,j]}} ) are of the required types whenever (f ∩ H, f^{′−}) ∈ U′′. (Here the family of partitions obtained for (P′, Q^{−}) has been enlarged by duplicating each λ^{[i_{0},j]}, to account for the fact that f_{i_{0}} ∩ H = f_{i_{0}+1} ∩ H.) The set U = { (f, f′) ∈ U′ | (f ∩ H, f^{′−}) ∈ U′′ } is open in φ(H), and it remains to show that U ≠ ∅.

The set U′′ and the dense open set of lemma 6.6, applied with η|_{H} for η and P′ for T, both project to a dense open subset of F_{η|_{H},P′}, and the intersection of these images is non-empty. For a choice of inverse images of any point in the intersection, one finds a nilpotent transformation η̂ of H × k with J(η̂) = λ and η̂|_{H} = η_{H}, and a pair (f̂, f′) ∈ F_{η̂,P} × F_{η̂,Q} with J(η̂|_{f̂_{i}∩f′_{j}}) = λ^{[i,j]} for 0 ≤ i, j ≤ n. Since J(η̂) = J(η) there exists a linear isomorphism g: H × k → V for which g ∘ η̂ = η ∘ g, and by the transitive action of Z_{u} on ω(F_{η,Q}) one can achieve that moreover g(H) = H; then g(f̂, f′) ∈ U so that U ≠ ∅, which completes the proof. Remark. Note that in the final argument we do not assume that g fixes H pointwise; indeed, this may not be possible, since it would imply im η̂ = g(im η̂) = im η (the latter identity follows from g ∘ η̂ = η ∘ g), but the whole point of the construction of η̂ was to avoid fixing im η̂ to any particular subspace of H.

§7. Interpretation of the transposed Robinson-Schensted algorithm. In this section we deduce, in close analogy to the previous section, an interpretation of the version of the Robinson-Schensted algorithm that is defined using column insertion instead of row insertion, and hence yields transposes of the tableaux P and Q. We start with a statement that is dual to lemma 1.5 (4).

7.1. Lemma. Let l ∈ U_{c}(η), and let ι: (V/l)^{∗} → V^{∗} be the map induced by the canonical projection V → V/l. For j ≠ c one has ι(W_{j}^{∗}(η_{/l})) = W_{j}^{∗}(η), while ι(W_{c}^{∗}(η_{/l})) has codimension 1 in W_{c}^{∗}(η).

Proof. Clearly ι is injective, and the image of im η + ker η^{j} under the projection V → V/l is contained in im η_{/l} + ker(η_{/l})^{j}, whence ι(W_{j}^{∗}(η_{/l})) ⊆ W_{j}^{∗}(η). The lemma follows by dimension consideration.

7.2. Definition. For any arrangement of partitions ({ν \atop κ} {μ \atop λ}) of type RSi (i = 0, …, 3), the corresponding arrangement of transposed partitions ({ν^{t} \atop κ^{t}} {μ^{t} \atop λ^{t}} ) is called a configuration of type RS^{t}i (the types RS^{t}0 and RS^{t}3 are identical to types RS0 and RS3, respectively). If a family of partitions (λ^{[i,j]}) is of type RS, then the family of transposed partitions is said to be of type RS^{t}.

7.3. Lemma. Let μ, μ′ ≺ λ, and let ν be determined by the condition that ({ν \atop μ′} {μ \atop λ}) is of one of the types RS^{t}1–RS^{t}3. Then for any l ∈ P(V)_{η} with J(η_{/l}) = μ′, there is a dense open subset of { H ∈ P^{∗}(V)_{η} | J(η|_{H}) = μ } on which J(η_{H/(l∩H)}) = ν holds.

Proof. If the configuration is of type RS^{t}3, the conclusion follows (without the need to restrict to a dense subset) by proposition 1.2. Otherwise μ = μ′, and we put λ − μ = (r, c), so that H ranges over the set U_{c}^{∗}(η) (of dimension r). By lemma 7.1, the subspace ι(W_{c}^{∗}(η_{/l})) of W_{c}^{∗}(η), has codimension 1; therefore, while H ⊇ ker η^{c} for all H ∈ U_{c}^{∗}(η), there is a dense open subset U on which H ⊉ η^{−c}(l). If the configuration is of type RS^{t}1 (i.e., c = 0), one has l ∩ H = {0} for H ∈ U, and therefore J(η_{H/(l∩H)}) = μ = ν. Finally if c > 0, so that the configuration is of type RS^{t}2, it follows from H ⊇ ker η or l ∈ im η that H ⊇ l; for H ∈ U one has H/l ⊉ ker(η_{/l})^{c}, but H/l ⊇ ker(η_{/l})^{c−1} by application of lemma 7.1 for j = c − 1, whence H/l ∈ U_{c−1}^{∗}(η_{/l}). Then J(η_{H/l}) differs from μ = J(η_{/l}) by a square in column c − 1, and is therefore equal to ν.

Note that the generic cases match those of Lemma 6.4, with all partitions transposed, but the nongeneric cases do not. We know of no geometric explanation for the first fact, but the latter is no surprise, since transposition reverses the dominance ordering on Jordan types that describes orbit closures.

7.4. Lemma. Let l ∈ P(V)_{η}. For all flags f in a dense open subset of F_{η}, the following holds: defining λ^{i} = J(η|_{f_{i}}) and μ^{i} = J(η_{f_{i}/l∩f_{i}}) for 0 ≤ i ≤ n, any configuration of the form ({μ^{i} \atop μ^{i+1}} {λ^{i} \atop λ^{i+1}} ) is of one of the types RS^{t}0–RS^{t}3.

Proof. This follows from lemma 7.3 just like lemma 6.5 follows from 6.4.

Similarly to the situation for the interpretation of the ordinary Robinson-Schensted correspondence, the sequence of spaces f_{i}/(l ∩ f_{i}) forms a complete η_{/l}-stable flag in V/l with one part repeated. For generic f ∈ F_{η,T} this flag lies in F_{η_{/l},T′} and has part i repeated, where this time T′ and i can be found by applying the Schensted column extraction procedure to T starting at square λ − J(η_{/l}), but again the set of flags so obtained is not generally dense in the indicated set. Here too the difficulty can be resolved by a converse construction to (in this case) dividing out the line l.

For 0 ≤ i_{0} ≤ n and define the following Z_{u}-stable set (a vector bundle over F_{η,T}):

F_{η,T,i_{0}^{∗}} = { (f, ϕ) ∈ F_{η,T} × V^{∗} | f_{i_{0}} ⊆ ker ϕ }.  (18)

To (f, ϕ) ∈ F_{η,T,i_{0}^{∗}} we associate in the n + 1-dimensional space V × k a nilpotent transformation η̃ and a flag f̃, as follows. For (v, x) ∈ V × k put η̃(v, x) = (η(v), ϕ(v)), and with l = {0} × k ⊆ V × k define

f̃_{i} = \{ \begin{matrix}f_{i} & if 0 ≤ i ≤ i_{0}, \\ f_{i−1} ⊕ l & if i_{0} ≤ i − 1 ≤ n. \end{matrix}  (19)

Since f_{i_{0}} ⊆ ker ϕ, the flag f̃ is η̃-stable. We identify (V × k)/l with V, so that f̃_{i}/l ≅ f_{i−1} for i > i_{0}.

7.5. Lemma. Let T ∈ T_{λ}, and 0 ≤ i_{0} ≤ n. For all (f, ϕ) in a Z_{u}-stable dense open subset of F_{η,T,i_{0}^{∗}}, the associated η̃ and f̃ satisfy the following: with ν^{i} = J(η̃|f̃_{i}) and λ^{i} = J(η_{f̃_{i}/(l∩f_{i})}) for 0 ≤ i ≤ n + 1, any configuration of the form ({λ^{i} \atop λ^{i+1}} {ν^{i} \atop ν^{i+1}} ) is of type RS^{t}0 if i < i_{0}, of type RS^{t}1 if i = i_{0}, and of type RS^{t}2 or RS3 if i > i_{0}.

Proof. The proof is analogous to that of lemma 6.6, with variations as noted below. Let the families ν^{i} and λ^{i} be determined by the requirements on the configurations; put ν = ν^{n+1} and ν − λ = (r, c).

References

Since (ker η̃)/l ≅ ker η ∩ ker ϕ, the statement J(η̃) = ν means that c = min { j | W_{j}(η) ⊆ ker ϕ }, by lemma 1.5 (1). In the starting case n = i_{0} of the induction this holds, as c = 0 and (f, ϕ) ∈ F_{η,T,n^{∗}} implies ϕ = 0. For n > i_{0} and H ∈ ω(F_{η,T}) there is a surjection (f, ϕ) ↦ (f^{−}, ϕ|_{H}) of the fibre ω̃^{−1}(H) (with ω̃(f, ϕ) = ω(f)) onto the variety F_{η|_{H},T^{−},i_{0}^{∗}} (not an isomorphism, as in the proof of lemma 6.6). The induction hypothesis provides dense open subset of F_{η|_{H},T^{−},i_{0}^{∗}}; let U ⊆ ω̃^{−1}(H) be its inverse image, and ν^{n} − λ^{n} = (r′, c′), then W_{c′}(η|_{H}) = ker(η|_{H}) ∩_{⋂(f,ϕ)∈U} ker(ϕ|_{H}). In the interesting case RS^{t}2 one has ν^{n} = λ and c′ = c + 1, whence W_{c′}(η) strictly contains W_{c′}(η|_{H}) by lemma 1.5 (4), and W_{c′}(η) ⊈ ker ϕ for some (f, ϕ) ∈ U. Therefore { (f, ϕ) ∈ U | W_{c′}(η) ⊈ ker ϕ } is dense in U, and on this subset c = min { j | W_{j}(η) ⊆ ker ϕ }, since W_{c}(η) = W_{c}(η|_{H}) ⊆ ker ϕ for all (f, ϕ) ∈ ω̃^{−1}(H).

7.6. Theorem. Let P, Q ∈ T_{λ}, and σ ∈ S_{n} with (P^{t}, Q^{t}) = RS(σ). Then for all (f, f′) in a dense open subset of F_{η,P} × F_{η,Q}^{∗}, the family J(η_{f_{i}/(f_{i}∩f′_{n−j})})_{0≤i,j≤n} is of type RS^{t}, and in particular π(f, f′)ñ = σ.

Proof. The proof is analogous to that of theorem 6.3, using lemmas 7.4 and 7.5 instead of 6.5 and 6.6.

Note that using theorem 3.3, the equivalence of the descriptions of the generic value of π(f, f′) given in theorems 6.3 and 7.6 follows from the purely combinatorial statement [vLee3, theorem 4.1.1]. We have preferred to give independent proofs of theorems 6.3 and 7.6, thereby giving a geometric explanation for the “witchcraft operating behind the scenes” (cf. [Kn2, p. 60]) of that combinatorial theorem.

References.

[Fom] S. V. Fomin, “Generalised Robinson-Schensted-Knuth correspondence”, Journal of Soviet Mathematics 41, (1988), 979–991.

[Haim] M. D. Haiman, “Dual equivalence with applications, including a conjecture of Proctor”, Discrete Mathematics 99, (1992), 79–113.

[Hes] W. H. Hesselink, “A classification of the nilpotent triangular matrices”, Compositio Mathematica 55, (1985), 89–133.

[Hum] J. E. Humphreys, Linear Algebraic Groups, Graduate Texts in Mathematics 21, Springer Verlag, 1975.

[Kn1] D. E. Knuth, “Permutations, matrices and generalized Young tableaux”, Pacific Journal of Math. 34, (1970), 709–727.

[Kn2] D. E. Knuth, The art of Computer programming, Vol. III Sorting and Searching, pp. 48–72, Addison-Wesley, 1973.

[vLee1] M. A. A. van Leeuwen, A Robinson-Schensted algorithm in the geometry of flags for Classical Groups, Thesis (Rijksuniversiteit Utrecht, the Netherlands), (1989).

[vLee2] M. A. A. van Leeuwen, “The Robinson-Schensted and Schützenberger algorithms and interpretations”, pp. 65–88 in Computational aspects of Lie group representations and related topics (A. M. Cohen, ed.), CWI Tract 84, Stichting Mathematisch Centrum, Amsterdam, 1991.

[vLee3] M. A. A. van Leeuwen, “The Robinson-Schensted and Schützenberger algorithms, an elementary approach”, Electronic J. of Combinatorics 3 (no. 2), R15, (1996), 32 pp.

[vLee4] M. A. A. van Leeuwen, “Tableau algorithms defined naturally for pictures”, Discrete Mathematics 157, (1996), 321–362.

[Macd] I. G. Macdonald, Symmetric Functions and Hall Polynomials, Oxford Mathematical Monographs, Clarendon press, Oxford, 1979.

[Rob] G. de B. Robinson, “On the representations of the symmetric group”, American Journal of Math. 60, (1938), 745–760.

[Sche] C. Schensted, “Longest increasing and decreasing subsequences”, Canadian Journal of Math. 13, (1961), 179–191.

[Schü1] M. P. Schützenberger, “Quelques remarques sur une construction de Schensted”, Math. Scandinavica 12, (1963), 117–128.

[Schü2] M. P. Schützenberger, “La correspondance de Robinson”, pp. 59–113 in Combinatoire et Représentation du Groupe Symétrique (D. Foata, ed.), Lecture Notes in Mathematics 579, Springer-Verlag, 1977.

[Spa1] N. Spaltenstein, “The fixed point set of a unipotent transformation on the flag manifold”, Proceedings of the Koninklijke Nederlandse Academie van Wetenschappen, Amsterdam, Series A 79(5), (1976), 452– 458.

References

[Spa2] N. Spaltenstein, Classes Unipotentes et Sous-groupes de Borel, Lecture Notes in Mathematics 946, Springer-Verlag, 1982.

[Spr1] T. A. Springer, “A construction of representations of Weyl groups”, Invent. Math. 44, (1978), 279–293.

[Spr2] T. A. Springer, “Geometric questions arising in the study of unipotent elements”, pp. 255–264 in The Santa Cruz conference on Finite Groups, Proceedings of Symposia in Pure Mathematics 37, 1980.

[Spr3] T. A. Springer, “Conjugacy classes in Algebraic Groups”, pp. 175–209 in Group Theory, Beijing, Lecture Notes in Mathematics 1185, Springer-Verlag, 1984.

[Sri] B. Srinivasan, “A geometrical approach to the Littlewood-Richardson rule”, J. of Algebra 187, (1997), 227–235.

[Stb1] R. Steinberg, “On the desingularisation of the unipotent variety”, Inventiones Math. 36, (1976), 209–224.

[Stb2] R. Steinberg, “An Occurrence of the Robinson-Schensted Correspondence”, Journal of Algebra 113, (1988), 523–528.