Multisegment Duality, Canonical Bases

and Total Positivity

Andrei Zelevinsky

Abstract. We illustrate recent interactions between algebraic combinatorics, representation theory and algebraic geometry with a piecewiselinear involution called the multisegment duality.

1991 Mathematics Subject Classification: 5, 14, 20

Keywords and Phrases: multisegments, Young tableaux, polyhedral combinatorics, quivers, canonical bases, total positivity

1. Introduction. We discuss some recent interactions between representation theory, algebraic geometry and algebraic combinatorics. Classically such an interaction involves:

• finite-dimensional representations of symmetric and general linear groups;

• geometry of flag varieties and Schubert varieties;

• combinatorics of Young tableaux and related algorithms such as the Robinson-Schensted-Knuth correspondence.

More recent advances in representation theory such as Lusztig’s canonical bases [14] and Kashiwara’s crystal bases [10] require new geometric and combinatorial tools. On the geometric side, an important role is played by quiver representation varieties and totally positive varieties. On the combinatorial side, the objects of interest become rational polyhedral convex cones and polytopes, their lattice points, and their piecewise-linear transformations.

We illustrate this interplay with a particular piecewise-linear involution, the multisegment duality. It was introduced in [20, 21] in the context of representations of general linear groups over a p-adic field. It also naturally appears in the geometry of quiver representations, and in the study of canonical bases for quantum groups. On the combinatorial side, it is closely related to Schützenberger’s involution on Young tableaux [19], as demonstrated in [4]. In this talk, we give a new combinatorial interpretation of the multisegment duality as an intertwining map between two piecewise-linear actions of the Lascoux-Schützenberger plactic monoid [12].

2. Multisegment duality and quiver representations. We fix a positive integer r and consider the set Σ = Σ_{r} of pairs of integers (i, j) such that 1 ≤ i ≤ j ≤ r. We regard a pair (i, j) ∈ Σ as a segment [i, j] := {i, i + 1, …, j} in [1, r]. Note that Σ can be identified with the set of positive roots of type A_{r}: each segment [i, j] corresponds to a root α_{i} + α_{i+1} + ⋯ + α_{j}, where α_{1}, …, α_{r} are the simple roots of type A_{r} in the standard numeration. Let ℕΣ denote the free abelian semigroup generated by Σ. We call its elements multisegments; they are formal linear combinations m = ∑_{(i,j)∈Σ} m_{ij}[i, j] with nonnegative integer coefficients.

Our main object of study will be the multisegment duality involution ζ on ℕΣ. Following [21], we define it in terms of quiver representations of the equidirected quiver of type A_{r}. Such a representation is a collection of finite-dimensional vector spaces V_{1}, …, V_{r} (say over C) and linear maps X_{k} : V_{k} → V_{k+1} for k = 1, …, r−1. Morphisms between and direct sums of representations are defined in an obvious way. As a special case of Gabriel’s classification [8], isomorphism classes of these quiver representations are in natural bijection with ℕΣ. That is, the multisegment m = ∑ m_{ij}[i, j] corresponds to the isomorphism class I(m) = ⊕m_{ij}I_{ij}, where the indecomposable representations I_{ij} are defined as follows: the space V_{k} in I_{ij} is one-dimensional for k ∈ [i, j], and zero otherwise, and X_{k}(V_{k}) = V_{k+1} for k ∈ [i, j − 1].

We also consider representations of the opposite quiver: such a representation is a collection of finite-dimensional vector spaces V_{1}, …, V_{r} and linear maps Y_{k} : V_{k} → V_{k−1} for k = 2, …, r. The isomorphism classes of these representations are also labeled by multisegments: now a multisegment m corresponds to the isomorphism class I^{op}(m) = ⊕m_{ij}I_{ij}^{op}, where I_{ij}^{op} is obtained by reversing arrows in I_{ij}.

Now let (V; X) be a quiver representation in the isomorphism class I(m). Let Z(V; X) be the variety of opposite quiver representations (V; Y) on the same collection of vector spaces V_{k} such that Y_{k+1}X_{k} = X_{k−1}Y_{k} for k ∈ [1, r] (with the convention that X_{0} = X_{r} = Y_{1} = Y_{r+1} = 0). It is easy to show that all generic representations from Z(V; X) belong to the same isomorphism class (here “generic” means that, for any (i, j) ∈ Σ, the composition Y_{i+1} ⋯ Y_{j} : V_{j} → V_{i} has the maximal possible rank). We define ζ(m) to be the multisegment corresponding to a generic representation in Z(V; X); that is, the isomorphism class of this generic representation is I^{op}(ζ(m)). The definition readily implies that the map ζ : ℕΣ → ℕΣ is an involution.

3. Formula for the multisegment duality. We now present a closed formula for ζ obtained in [11]. For (i, j) ∈ Σ, let T_{ij} denote the set of all maps ν : [1, i] × [j, r] → [i, j] such that ν(k, l) ≤ ν(k′, l′) whenever k ≤ k′ and l ≤ l′ (in other words, ν is a morphism of posets, where [1, i] × [j, r] is supplied with the product order). For any multisegment m = ∑ m_{ij}[i, j], we set

ρ_{ij}(m) = min_{ν∈T_{ij}} ∑_{(k,l)∈[1,i]×[j,r]} m_{ν(k,l)+k−i,ν(k,l)+l−j} (1)

(with the understanding that ρ_{ij}(m) = 0 for (i, j) ∉ Σ).

Multisegment Duality, … 411

Theorem 1. For every multisegment m, the multisegment ζ(m) = ∑ m′_{ij}[i, j] is given by

m′_{ij} = ρ_{ij}(m) − ρ_{i−1,j}(m) − ρ_{i,j+1}(m) + ρ_{i−1,j+1}(m) . (2)

The function ρ_{ij}(m) in (1) has the following meaning: it is the rank of the map Y_{i+1} ⋯ Y_{j} : V_{j} → V_{i} for any quiver representation (V; Y) in the isomorphism class I^{op}(ζ(m)).

The proof of Theorem 1 in [11] is elementary, using only linear algebra and combinatorics. The main ingredients of the proof are: the “Max Flow = Min Cut” theorem from the network flow theory [7], and the result of S. Poljak describing the maximal possible rank for a given power of a matrix with a given pattern of zeros [18].

4. Representation-theoretic connections. It was conjectured in [20, 21] that the multisegment duality describes a natural duality operation acting on irreducible smooth representations of general linear groups over p-adic fields. In [17], this conjecture was reformulated in terms of representations of affine Hecke algebras and then proved. We recall (see [17, I.2]) that the affine Hecke algebra H_{n} can be defined as the associative algebra with unit over Q(q) generated by the elements S_{1}, …, S_{n−1}, X_{1}^{±1}, …, X_{n}^{±1} subject to the relations:

(S_{i} − q)(S_{i} + 1) = 0, S_{i}S_{i+1}S_{i} = S_{i+1}S_{i}S_{i+1},
X_{j}X_{k} = X_{k}X_{j}, S_{i}X_{j} = X_{j}S_{i} (j ≠ i, i + 1), S_{i}X_{i+1}S_{i} = qX_{i}.

As shown in [17] using the results of [20], irreducible finite-dimensional representations of H_{n} are naturally indexed by multisegments m = ∑ m_{ij}[i, j] with ∑_{i,j}(j +1−i)m_{ij} = n (here we have to take the multisegments supported on some segment [a, b] ⊂ Z, not only on [1, r]). According to [17, Proposition I.7.3], the involution ζ corresponds to the following involution on irreducible finite-dimensional representations of H_{n}: π ↦ π ∘ φ, where φ is the automorphism of H_{n} defined by

φ(S_{i}) = −qS_{n−i}^{−1}, φ(X_{j}) = X_{n+1−j}.

(This result was extended from GL_{n} to other reductive groups in [1].)

Another interpretation of ζ is in terms of quantum groups. Let C_{q}[N] be the q-deformation of the algebra of regular functions on the group N of unipotent upper triangular (r + 1) × (r + 1) matrices (see, e.g., [4]). We recall that C_{q}[N] is an associative algebra with unit over Q(q) generated by the elements x_{1}, …, x_{r} subject to the relations:

x_{i}x_{j} = x_{j}x_{i} for |i − j| > 1,
x_{i}^{2}x_{j} − (q + q^{−1})x_{i}x_{j}x_{i} + x_{j}x_{i}^{2} = 0 for |i − j| = 1.

This algebra has a distinguished basis B, the dual canonical basis (it is dual to Lusztig’s canonical basis constructed in [14]). It follows from the results in [14] that B is invariant under the involutive antiautomorphism b ↦ b^{∗} of C_{q}[N] such that x_{i}^{∗} = x_{i} for all i. As shown in [4], there exists a natural labeling m ↦ b(m) of B by multisegments such that b(m)^{∗} = b(ζ(m)) for every m ∈ Σ.

Recently in [13], a duality similar to the multisegment duality was introduced and studied; it involves affine Hecke algebras at roots of unity, modular representations of the groups GL_{n} over p-adic fields, and Kashiwara’s crystal bases for affine Lie algebras.

5. Mœglin–Waldspurger rule. We now turn to a more detailed discussion of combinatorial properties and connections of the multisegment duality ζ. We start with a recursive description of ζ given in [17].

Take any nonzero multisegment m = ∑_{(i,j)∈Σ} m_{ij}[i, j]. Let k be the minimal index such that m_{kj} ≠ 0 for some j. Define the sequence of indices j_{1}, j_{2}, …, j_{p} as follows:

j_{1} = min {j : m_{kj} ≠ 0}, j_{t+1} = min {j : j > j_{t}, m_{k+t,j} ≠ 0} (t = 1, …, p − 1) .

The sequence terminates when j_{p+1} does not exist: that is, when m_{k+p,j} = 0 for j_{p} < j ≤ r. We associate to m the multisegment m′ given by

m′ = m + ∑_{t=1}^{p}([k + t, j_{t}] − [k + t − 1, j_{t}]) (3)

(with the convention [i, j] = 0 unless 1 ≤ i ≤ j ≤ r). The Mœglin–Waldspurger rule states that

ζ(m) = ζ(m′) + [k, k + p − 1] . (4)

Setting |m| := ∑(j + 1 − i)m_{ij} ∈ ℕ, we see that |m′| = |m| − p < |m| for any nonzero multisegment m; thus (4) (combined with ζ(0) = 0) indeed provides a recursive description of ζ.

6. Relations with plactic monoid. We now give a new combinatorial interpretation of the multisegment duality as an intertwining map between two piecewise-linear actions of the Lascoux-Schützenberger plactic monoid [12]. Let Pl_{r} denote the plactic monoid on r + 1 letters. By definition, Pl_{r} is an associative monoid with unit generated by r + 1 elements p_{1}, p_{2}, …, p_{r+1} subject to the relations

p_{j}p_{i}p_{k} = p_{j}p_{k}p_{i}, p_{i}p_{k}p_{j} = p_{k}p_{i}p_{j} (1 ≤ i < j < k ≤ r + 1) ,
p_{j}p_{i}p_{j} = p_{j}^{2}p_{i}, p_{i}p_{j}p_{i} = p_{j}p_{i}^{2} (1 ≤ i < j ≤ r + 1)

(sometimes called the Knuth relations). As shown by A. Lascoux and M.-P. Schützenberger, this structure provides a natural algebraic framework for the study of Young tableaux and symmetric polynomials.

We now define two right actions of Pl_{r} on ℕΣ, which we shall denote (m, p) ↦ m·p and (m, p) ↦ m∗p, respectively. Given a multisegment m = ∑_{(i,j)∈Σ} m_{ij}[i, j] and an index k ∈ [1, r + 1], the multisegments m · p_{k} and m ∗ p_{k} are defined as follows.

To define m · p_{k}, let j_{1}, j_{2}, …, j_{p} be a sequence of indices given recursively as follows:

j_{1} = k − 1, j_{t+1} = min {j : j_{t} < j ≤ r, m_{tj} > 0} (t = 1, …, p − 1) .

The sequence terminates when the set under the minimum sign becomes empty: that is, when m_{pj} = 0 for j_{p} < j ≤ r. Now we set

m · p_{k} = m + ∑_{t=1}^{p}([t, j_{t}] − [t − 1, j_{t}]) . (5)

To define m∗p_{k}, we construct recursively two sequences of indices c_{0}, c_{1}, …, c_{p} and i_{1}, i_{2}, …, i_{p+1}:

c_{0} = r, i_{1} = k; c_{t} = max ({c : 0 ≤ c < c_{t−1}, m_{i_{t},i_{t}+c} > 0} ∪ {−1}) ,
i_{t+1} = max ({i : 1 ≤ i < i_{t}, m_{i,i+c_{t}} = 0} ∪ {0}) (t = 1, …, p) .

The process terminates when i_{p+1} = 0. Now we define

m ∗ p_{k} = m + ∑_{t=1}^{p} ∑_{i_{t+1}<i≤i_{t}}([i − 1, i + c_{t}] − [i, i + c_{t}]) . (6)

Theorem 2. (a) Each of the correspondences given by (5) and (6) extends by associativity to a right action of Pl_{r} on ℕΣ.

(b) Each of the two actions in (a) is transitive: i.e., for every two multisegments m_{1} and m_{2}, there exist p, p′ ∈ Pl_{r} such that m_{2} = m_{1} · p = m_{1} ∗ p′.

(c) The multisegment duality ζ intertwines the two actions: ζ(m · p) = ζ(m) ∗ p for any multisegment m and any p ∈ Pl_{r}.

In view of part (b), ζ is uniquely determined by the intertwining property (c) combined with the normalization ζ(0) = 0. The following proposition, a direct consequence of the definitions, shows that the Mœglin–Waldspurger rule (4) is a special case of Theorem 2 (c).

Proposition 3. Let m be a nonzero multisegment. Suppose k is the minimal index such that m_{kj} ≠ 0 for some j, and l is the maximal index such that m_{kl} ≠ 0. Then m · (p_{k}p_{k−1} ⋯ p_{1}) is the multisegment m′ in (3), while m ∗ (p_{k}p_{k−1} ⋯ p_{1}) = m − [k, l].

The idea to relate the multisegment duality with the plactic monoid was suggested to the author by M.-P. Schützenberger during the author’s visit to Université de Marne-la-Vallée in May-June 1994. Theorem 2 was proved soon after, but never published.

7. Schützenberger involution. Let us now explore the relation between the multisegment duality and the Schützenberger involution on Young tableaux. We need some terminology and notation related to tableaux. Let λ = (λ_{1} ≥ ⋯ ≥ λ_{r} ≥ 0) be a partition of length ≤ r. We identify λ with its diagram (denoted by the same letter)

λ = {(i, j) ∈ Z × Z : 1 ≤ i ≤ r, 1 ≤ j ≤ λ_{i}} .

An A_{r}-tableau of shape λ is a map τ : λ → [1, r + 1] satisfying

τ(i, j + 1) ≥ τ(i, j), τ(i + 1, j) > τ(i, j)

for all (i, j) ∈ λ (with the convention that τ(i, j) = +∞ for i > r or j > λ_{i}). The Schützenberger involution τ ↦ η(τ) (also known as the evacuation involution) is an involution on the set of A_{r}-tableaux of shape λ which can be defined recursively as follows (cf. [19]).

To any A_{r}-tableau τ of shape λ we associate a sequence of entries (i_{1}, j_{1}), …, (i_{p}, j_{p}) ∈ λ in the following way. We set (i_{1}, j_{1}) = (1, 1) and

(i_{t+1}, j_{t+1}) = \{ \begin{matrix}(i_{t}, j_{t} + 1) & if τ(i_{t}, j_{t} + 1) < τ(i_{t} + 1, j_{t}) ; \\ (i_{t} + 1, j_{t}) & if τ(i_{t}, j_{t} + 1) ≥ τ(i_{t} + 1, j_{t}) . \end{matrix}

The sequence terminates at a corner point (i_{p}, j_{p}) ∈ λ, i.e., when none of (i_{p}+1, j_{p}) and (i_{p}, j_{p}+1) belong to λ. Now we set λ′ = λ−{(i_{p}, j_{p})} and consider the tableau τ′ of shape λ′ obtained from τ by changing the values at (i_{1}, j_{1}), …, (i_{p−1}, j_{p−1}) according to τ′(i_{t}, j_{t}) = τ(i_{t+1}, j_{t+1}). The tableau η(τ) is defined recursively as the tableau η(τ′) of shape λ′ extended to a tableau of shape λ by setting η(τ)(i_{p}, j_{p}) = r + 2 − τ(1, 1).

There are (at least) two natural ways to encode tableaux by multisegments: to each tableau τ : λ → [1, r + 1] we associate two multisegments ∂(τ) and ∂′(τ) given by

∂(τ)_{ij} = #{s : τ(i, s) = j + 1}, ∂′(τ)_{ij} = #{s : τ(i, s) ≤ j, τ(i + 1, s) ≥ j + 2} .

For a given shape λ, a tableau τ is uniquely recovered from each of the multisegments ∂(τ) and ∂′(τ). More precisely, the correspondence τ ↦ ∂(τ) is a bijection between the set of all A_{r}-tableaux of shape λ and the set of multisegments m satisfying

∑_{k=j}^{r}(m_{i,k} − m_{i+1,k+1}) ≤ λ_{i} − λ_{i+1} (1 ≤ i ≤ j ≤ r) ;

and the multisegments m = ∂(τ) and m′ = ∂′(τ) are related as follows:

m′_{ij} = λ_{i} − λ_{i+1} − ∑_{k=j}^{r}(m_{i,k} − m_{i+1,k+1}) ;

m_{ij} = λ_{r−j+i} − λ_{r−j+i+1} − ∑_{k=j}^{r}(m′_{k−j+i,k} − m′_{k−j+i,k+1}) .

The relationship between the Schützenberger involution η and the multisegment duality ζ is now given as follows.

Theorem 4. For every tableau τ, the multisegment ∂′(η(τ)) is obtained from ζ(∂(τ)) by the following permutation of indices: ∂′(η(τ))_{j−i+1,r−i+1} = ζ(∂(τ))_{ij}.

Theorem 4 was formulated in [11] and proved in [4]; the proof uses some properties of canonical bases, and an equivalent definition of the Schützenberger involution in terms of the so-called Bender-Knuth operators (this definition is due to Gansner [9]).

8. Lusztig’s transition maps and total positivity. We now show that the multisegment duality is a special case of Lusztig’s piecewise-linear transition maps between various parametrizations of the (dual) canonical basis B. This will require some terminology.

Recall that Σ = Σ_{r} stands for the set of all segments [i, j] ⊂ [1, r]. We say that a triple of distinct segments is dependent if one of these segments is the disjoint union of two remaining ones; the largest segment in a dependent triple will be called the support of the triple, and two remaining ones the summands. Let ν = (ν_{1}, …, ν_{m}) be a total ordering of Σ; here m = r(r + 1)/2, the cardinality of Σ. We say that ν is normal if the support of every dependent triple of segments lies between its summands. The bijection between segments and positive roots given in Section 2 identifies normal orderings of Σ with the well-known normal orderings of positive roots; thus normal orderings are in natural bijection with reduced words for w_{0}, the longest permutation in the symmetric group S_{r+1} (see e.g., [3, Proposition 2.3.1]). Two examples: in the lexicographic normal ordering ν_{min} a segment [i, j] precedes [i′, j′] if i < i′ or i = i′, j < j′; the reverse lexicographic normal ordering ν_{max} is obtained from ν_{min} by replacing each segment [i, j] with [r + 1 − j, r + 1 − i].

Now consider the dual canonical basis B in C_{q}[N] (see Section 4). Translating results of [15, 16] (see also [3]) into the language of segments, we see that every normal ordering ν of Σ gives rise to a bijective parametrization b_{ν} : ℕΣ → B. (In particular, b_{ν_{min}} is the parametrization m → b(m) discussed in Section 4.) For any two normal orderings ν and ν′, Lusztig’s transition map between ν and ν′ is a bijection R_{ν}^{ν′} of ℕΣ onto itself given by

R_{ν}^{ν′} = b_{ν′}^{−1} ∘ b_{ν} . (7)

The multisegment duality turns out to be one of these maps (see [3, Theorem 4.2.2 and Remark 4.2.3]):

ζ = R_{ν_{min}}^{ν_{max}} . (8)

In [3], closed formulas for the transition maps R_{ν}^{ν′} were obtained using a parallelism discovered by Lusztig [16] between canonical bases and total positivity. In particular, a new proof of Theorem 1 was obtained. We conclude with a brief discussion of the ideas and methods used in [3].

Clearly, the set of all normal orderings of Σ is closed under the following elementary moves:

2-move. In a normal ordering ν, interchange two consecutive (with respect to ν) segments provided they do not belong to a dependent triple.

3-move. Interchange the summands of a dependent triple that occupies three consecutive positions in ν.

As a consequence of the corresponding well-known property of reduced words, every two normal orderings of Σ can be obtained from each other by a sequence of 2- and 3-moves. It follows that every transition map can be expressed as a composition of “elementary” transition maps R_{ν}^{ν′} for pairs (ν, ν′) related by a 2or 3-move. These elementary transition maps were computed by Lusztig in [15]. Translated into the language of multisegments they take the following form:

• if ν and ν′ are related by a 2-move then R_{ν}^{ν′} is the identity map;

• if ν′ is obtained from ν by a 3-move

⋯ α, α ∪ β, β ⋯ → ⋯ β, α ∪ β, α ⋯

then the only components of the multisegment m′ = R_{ν}^{ν′}(m) different from the corresponding components of m are

m′_{α} = m_{α} + m_{α∪β} − min (m_{α}, m_{β}), m′_{α∪β} = min (m_{α}, m_{β}) ,

m′_{β} = m_{β} + m_{α∪β} − min (m_{α}, m_{β}) .

(9)

The key observation now is as follows: the piecewise-linear expressions that appear in (9) can be interpreted as rational expressions if one uses an exotic “semifield” structure on Z, where the usual addition plays the role of multiplication, and taking the minimum plays the role of addition. The semifield (Z, min, +) is known under various names. We use the term tropical semifield, which we learned from M.-P. Schützenberger. A detailed study of its algebraic properties, along with numerous applications, can be found in [2].

The “rational” version of (9) takes the form

m′_{α} = \frac{m_{α}m_{α∪β}}{m_{α} + m_{β}} , m′_{α∪β} = m_{α} + m_{β}, m′_{β} = \frac{m_{β}m_{α∪β}}{m_{α} + m_{β}} . (10)

We use this version to define rational transition maps R_{ν}^{ν′} : R_{>0}Σ → R_{>0}Σ; here the components m_{ij} of multisegments can be any positive real numbers, and the algebraic operations in (10) are understood in the most common sense. It is not hard to show that a closed formula for some rational transition map R_{ν}^{ν′} would imply such a formula for the corresponding piecewise-linear transition map, by simply translating it into the tropical language; the only caveat is that the formula in question must be subtraction-free because the tropical structure does not allow subtraction.

This is precisely the method used in [3]. To compute rational transition maps, we use the observation (due to Lusztig) that they have another interpretation parallel to that in (7). Namely, they describe the relationships between different parametrizations of the variety N_{>0} of all totally positive unipotent upper triangular matrices (recall that a matrix x ∈ N is totally positive if all the minors that do not identically vanish on N take positive values at x). We refer the reader to [3] for the details; let us only mention that the computations in [3] are based on algebraic and geometric study of totally positive varieties. This study is put into a much more general context in [5, 6].

References

[1] A.-M. Aubert, Dualité dans le groupe de Grothendieck de la catégorie des representations lisses de longueur finie d’un groupe réductif p-adique, Trans. A.M.S. 347 (1995), 2179–2189; Erratum: Trans. A.M.S. 348 (1996), 4687– 4690.

[2] F. Baccelli, G. Cohen, G. J. Olsder, and J.-P. Quadrat, Synchronization and linearity, Wiley, 1992.

[3] A. Berenstein, S. Fomin and A. Zelevinsky, Parametrizations of canonical bases and totally positive matrices, Adv. in Math. 122 (1996), 49–149.

[4] A. Berenstein and A. Zelevinsky, Canonical bases for the quantum group of type A_{r} and piecewise-linear combinatorics, Duke Math. J. 82 (1996), 473–502.

[5] A. Berenstein and A. Zelevinsky, Total positivity in Schubert varieties, Comment. Math. Helv. 72 (1997), 128–166.

[6] S. Fomin and A. Zelevinsky, Double Bruhat cells and total positivity, Prépublication 1998/08, IRMA, Université Louis Pasteur, Strasbourg, 1998.

[7] L.R. Ford and D. R. Fulkerson, Flows in Networks, Princeton University Press, 1962.

[8] P. Gabriel, Unzerlegbare darstellungen I, Manuscripta Math. 6 (1972), 71–103.

[9] E. R. Gansner, On the equality of two plane partition correspondences, Discrete Math. 30 (1980), 121–132.

[10] M. Kashiwara, On crystal bases of the q-analogue of universal enveloping algebras, Duke Math. J. 63 (1991), 465–516.

[11] H. Knight and A. Zelevinsky, Representations of quivers of type A and the multisegment duality, Adv. in Math. 117 (1996), 273–293.

[12] A. Lascoux and M.-P. Schützenberger, Le monoide plaxique, in: Noncommutative structures in algebra and geometric combinatorics (Naples, 1978), pp. 129–156, Quad. “Ricerca Sci.” 109, CNR, Rome, 1981.

[13] B. Leclerc, J.-Y. Thibon and E. Vasserot, Zelevinsky’s involution at roots of unity, E-print math. archive QA/9806060, June 1998.

[14] G. Lusztig, Canonical basis arising from quantised enveloping algebras, J. Amer. Math. Soc. 3 (1990), 447–498.

[15] G. Lusztig, Introduction to quantum groups, Progress in Mathematics 110, Birkhäuser, 1993.

[16] G. Lusztig, Total positivity in reductive groups, in: Lie theory and geometry: in honor of Bertram Kostant, Progress in Mathematics 123, Birkhäuser, 1994.

[17] C. Mœglin and J. L. Waldspurger, Sur l’involution de Zelevinski, J. Reine Angew. Math. 372 (1986), 136–177.

[18] S. Poljak, Maximum rank of powers of a matrix of a given pattern, Proc. A.M.S. 106 (1989), 1137–1144.

[19] M.-P. Schützenberger, Promotion des morphismes d’ensembles ordonnés, Discrete Math. 2 (1972), 73–94.

[20] A. Zelevinsky, Induced representations of reductive p-adic groups II, Ann. Sci. E.N.S. 13 (1980), 165–210.

[21] A. Zelevinsky, A p-adic analog of the Kazhdan-Lusztig conjecture, Funct. Anal. Appl. 15 (1981), 83–92.

Andrei Zelevinsky

Department of Mathematics Northeastern University Boston, MA 02115, USA andrei@neu.edu 418

Documenta Mathematica · Extra Volume ICM 1998 · III ·