The Robinson-Schensted correspondence, crystal bases, and the quantum straightening at q = 0 ^{∗}

Bernard Leclerc^{†}and Jean-Yves Thibon^{‡}

Submitted: March 14, 1995; Accepted: July 12, 1995

Dedicated to Dominique Foata

Abstract We show that the quantum straightening for Young tableaux and Young bitableaux

reduces in the crystal limit q ↦ 0 to the Robinson-Schensted correspondence.

1 Introduction

Let K be a field of characteristic 0, and X = (x_{ij})_{1≤i, j≤n} a matrix of commutative indeterminates. The ring K[x_{ij}] may be regarded as the algebra F[Mat_{n}] of polynomial functions on the space of n × n matrices over K. A linear basis of this algebra is given by the bitableaux of Désarménien, Kung, Rota [6], which are defined in the following way.

Given two (semistandard) Young tableaux τ and τ′ of the same shape, with columns c_{1}, …, c_{k} and c′_{1}, …, c′_{k}, the Young bitableau (τ | τ′) is the product of the k minors of X whose row indices belong to c_{i} and column indices to c′_{i}, i = 1, …, k. For example,

57 3 4  4 125 26 15 13

:= | \begin{matrix}x_{11} & x_{12} & x_{15} \\ x_{31} & x_{32} & x_{35} \\ x_{41} & x_{42} & x_{45} \end{matrix} | × | \begin{matrix}x_{13} & x_{14} \\ x_{53} & x_{54} \end{matrix} | × | \begin{matrix}x_{25} & x_{27} \\ x_{65} & x_{67} \end{matrix} | .

More generally, we shall call tabloid a sequence of column-shaped Young tableaux, and we shall associate to each pair δ, δ′ of tabloids of the same shape a bitabloid (δ | δ′) defined as the product of minors indexed by the columns of δ and δ′.

∗Partially supported by PRC Math-Info and EEC grant n^{0} ERBCHRXCT930400

†L.I.T.P., Université Paris 7, 2 place Jussieu, 75251 Paris cedex 05, France

‡Institut Gaspard Monge, Université de Marne-la-Vallée, 2 rue de la Butte-Verte, 93166 Noisy-le-Grand cedex, France

There exists an algorithm due to Désarménien [5] for expanding any polynomial in K[x_{ij}] on the basis of bitableaux. This is the so-called straightening algorithm (for bitableaux). In particular, the monomials x_{i_{1}j_{1}} ⋯ x_{i_{k}j_{k}}, which obviously form another linear basis of K[x_{ij}], can be expressed in a unique way as linear combinations of bitableaux. Thus, the straightening of x_{23} x_{11} x_{32} reads

13 2  13 2 1 2 3  1 2 3 2 1 3  3 1 2  − =  321 321 +  +  −  + 1  13 2  13 2  1  1  1 2 3  2 3  2 3  2 3

On the other hand, the Robinson-Schensted correspondence [26, 27, 28, 17] associates to any word w on the alphabet of symbols {1, …, n} a pair (P (w), Q(w)) of Young tableaux of the same shape. For example, the image of the word w = 2 1 4 3 5 1 2 under this correspondence is the pair

, 421 31 52  621 43 57

Both the straightening algorithm and the Robinson-Schensted algorithm are strongly connected with the representation theory of GL_{n}. Indeed, the straightening algorithm allows to compute the action of GL_{n} in (polynomial) irreducible representations, while the Robinson-Schensted correspondence was devised by Robinson to obtain a proof of the Littlewood-Richardson rule for decomposing into irreducibles the tensor product of two irreducible representations. The problem that we want to investigate is whether there exists any relation between the straightening algorithm and the Schensted algorithm. It turns out that to answer this question, one has to replace the algebra F[Mat_{n}] by its quantum analogue F_{q}[Mat_{n}] [25]. This is the associative algebra over K(q) generated by n^{2} letters t_{ij}, i, j = 1, …, n subject to the relations

t_{ik} t_{il} = q^{−1} t_{il} t_{ik} ,  (1)
t_{ik} t_{jk} = q^{−1} t_{jk} t_{ik} ,  (2)
t_{il} t_{jk} = t_{jk} t_{il} ,  (3)
t_{ik} t_{jl} − t_{jl} t_{ik} = (q^{−1}−q) t_{il} t_{jk} ,  (4)

for 1 ≤ i < j ≤ n and 1 ≤ k < l ≤ n. The quantum determinant of T = (t_{ij}) is the element

det_{q} = det_{q} T := ∑_{w∈S_{n}} (−q)^{−ℓ(w)} t_{1w_{1}} … t_{nw_{n}}

of F_{q}[Mat_{n}]. Here S_{n} is the symmetric group on {1, …, n} and ℓ(w) denotes the length of the permutation w. The quantum determinant of T belongs to the center of F_{q}[Mat_{n}]. More generally, for I = (i_{1}, …, i_{k}) and J = (j_{1}, …, j_{k}) one defines the quantum minor of the submatrix T_{IJ} as

det_{q} T_{IJ} := ∑_{w∈S_{k}} (−q)^{−ℓ(w)} t_{i_{1}j_{w_{1}}} … t_{i_{k}j_{w_{k}}} ,

and the quantum bitableau (τ|τ′) (resp. quantum bitabloid (δ | δ′)) as the product of the quantum minors indexed by the columns of the Young tableaux τ and τ′ (resp. of the tabloids δ and δ′). As proved by Huang, Zhang [10], the set of quantum bitableaux is again a linear basis of F_{q}[Mat_{n}]. For example, the expansion of the monomial t_{23} t_{11} t_{32} on this basis is

2 1 3  3 1 2  1 2 3  1 2 3  1  1 2 3  2 3 321 321 13 2  12 3 1  13 2 2 3  13 2  13 2 =  − +  − q^{3}  q^{3} (1 − q^{2} + q^{4})  q^{4} q^{5} +  q^{5} +

In the present example the coefficients of the expansion are polynomials in q, and only one of them has a nonzero constant term. In other words, denote by B the linear basis of quantum bitableaux in F_{q}[Mat_{n}], and let L be the lattice generated over K[q] by the elements of B. Then

2 1 3  3 1 2  1  13 2 2 3 ≡  mod qL

This is an illustration of the following

Theorem 1.1 Let u = i_{1} ⋯ i_{k} and v = j_{1} ⋯ j_{k} be two words on {1, …, n}, and denote by (P (u), Q(u)), (P (v), Q(v)) their images under the Robinson-Schensted correspondence. Then,

t_{i_{1}j_{1}} ⋯ t_{i_{k}j_{k}} ≡ \{ \begin{matrix}(P (u)|P (v)) & mod qL & if Q(u) = Q(v) \\ 0 & mod qL & otherwise \end{matrix} .

More generally, as will be proved in Section 5, any quantum bitabloid lies in the K[q]- linear span L of quantum bitableaux, and is congruent modulo qL to a unique quantum bitableau (or to 0) described by means of the Robinson-Schensted correspondence.

As a corollary we obtain an unexpected characterization of the plactic congruence on words [17, 20], defined by

u ∼ v ⟺ P (u) = P (v) .

Corollary 1.2 With the same notations as above,

u ∼ v ⟺ t_{i_{1}i_{1}} ⋯ t_{i_{k}i_{k}} ≡ t_{j_{1}j_{1}} ⋯ t_{j_{k}j_{k}} mod qL .

At this point, it is important to recall that the existence of a connection between the Robinson-Schensted correspondence and the representation theory of the quantized enveloping algebra U_{q}(𝔤𝔩_{n}) at q = 0 was first discovered by Date, Jimbo, Miwa [4]. The results presented here are in fact of the same kind as those of [4], namely, it is shown in [4] that if V_{(1)} denotes the basic representation of U_{q}(𝔤𝔩_{n}), the transition matrix in V_{(1)}^{⊗k} from the basis of monomial tensors to the Gelfand-Zetlin basis specializes when q = 0 to a permutation matrix given by the Robinson-Schensted map. Similarly, Theorem 1.1 states that the transition matrix in the U_{q}(𝔤𝔩_{n})-module F_{q}[Mat_{n}] from the basis of monomials

B_{τ} = {t_{i_{1}j_{1}} ⋯ t_{i_{k}j_{k}} | Q(i_{1} ⋯ i_{k}) = Q(j_{1} ⋯ j_{k}) = τ_{ν} for some ν}

to the basis of quantum bitableaux is equal at q = 0 to a permutation matrix also computed from the Robinson-Schensted algorithm. Here, τ_{ν} denotes for each partition ν a fixed standard Young tableau of shape ν.

The work of Date, Jimbo, Miwa, provided the starting point from which Kashiwara developed his theory of crystal bases for quantized enveloping algebras [13, 14]. We shall use crystal bases as the main tool for proving Theorem 1.1.

The paper is organized as follows. In Section 2, we collect the necessary material about U_{q}(𝔤𝔩_{n}), U_{q}(𝔰𝔩_{n}) and their representation theory. In Section 3, we review the definition and basic properties of Kashiwara’s crystal bases at q = 0. These two sections are intended to provide a leisurely introduction to quantum groups and crystal bases, in order to make the paper more self-contained and more accessible. The new results appear in Section 4 and Section 5. In Section 4, we formulate and prove a version of Theorem 1.1 for the case of (single) tableaux, that is, we work in the subring of F_{q}[Mat_{n}] generated by the quantum minors taken on the initial rows of T. Finally in Section 5 we prove Theorem 1.1, and its above-mentioned generalization.

2 U_{q}(𝔤𝔩_{n}) and U_{q}(𝔰𝔩_{n})

A general reference for this Section and the following one is the nice exposition [3]. We first recall the definition of the quantized enveloping algebras U_{q}(𝔤𝔩_{n}) [12] and U_{q}(𝔰𝔩_{n}) [11, 7]. U_{q}(𝔤𝔩_{n}) is the associative algebra over K(q) generated by the 4n − 2 symbols e_{i}, f_{i}, i = 1, …, n − 1 and q^{ϵ_{i}}, q^{−ϵ_{i}}, i = 1, …, n, subject to the relations

q^{ϵ_{i}}q^{−ϵ_{i}} = q^{−ϵ_{i}}q^{ϵ_{i}} = 1 , [q^{ϵ_{i}}, q^{ϵ_{j}}] = 0 ,  (5)

q^{ϵ_{i}}e_{j}q^{−ϵ_{i}} = \{ \begin{matrix}qe_{j} & for i = j \\ q^{−1}e_{j} & for i = j + 1 \\ e_{j} & otherwise \end{matrix} ,  (6)

q^{ϵ_{i}}f_{j}q^{−ϵ_{i}} = \{ \begin{matrix}q^{−1}f_{j} & for i = j \\ qf_{j} & for i = j + 1 \\ f_{j} & otherwise \end{matrix} ,  (7)

[e_{i}, f_{j}] = δ_{ij} \frac{q^{ϵ_{i}}q^{−ϵ_{i+1}} − q^{−ϵ_{i}}q^{ϵ_{i+1}}}{q − q^{−1}} ,  (8)
[e_{i}, e_{j}] = [f_{i}, f_{j}] = 0 for |i − j| > 1 ,  (9)
e_{j}e_{i}^{2} − (q + q^{−1})e_{i}e_{j}e_{i} + e_{i}^{2}e_{j} = f_{j}f_{i}^{2} − (q + q^{−1})f_{i}f_{j}f_{i} + f_{i}^{2}f_{j} = 0 for |i − j| = 1 . (10)

The subalgebra of U_{q}(𝔤𝔩_{n}) generated by e_{i}, f_{i}, and

q^{h_{i}} = q^{ϵ_{i}}q^{−ϵ_{i+1}}, q^{−h_{i}} = q^{−ϵ_{i}}q^{ϵ_{i+1}}, i = 1, …, n − 1,  (11)

is denoted by U_{q}(𝔰𝔩_{n}).

The representation theories of U_{q}(𝔤𝔩_{n}) and U_{q}(𝔰𝔩_{n}) are closely parallel to those of their classical counterparts U(𝔤𝔩_{n}) and U(𝔰𝔩_{n}). Let M be a U_{q}(𝔤𝔩_{n})-module and μ = (μ_{1}, …, μ_{n}) be a n-tuple of nonnegative integers. The subspace

M_{μ} = {v ∈ M | q^{ϵ_{i}}v = q^{μ_{i}}v , i = 1, …, n}

is called a weight space and its elements are called weight vectors (of weight μ). Relations (6) (7) show that

e_{i}M_{μ} ⊂ M_{μ+α_{i}} , f_{i}M_{μ} ⊂ M_{μ−α_{i}} ,

where μ+α_{i} = (μ_{1}, …, μ_{i}+1, μ_{i+1}−1, …, μ_{n}) and μ−α_{i} = (μ_{1}, …, μ_{i}−1, μ_{i+1}+1, …, μ_{n}). Thus, ordering the weights in the usual way by setting

μ ≤ λ ⟺ ∑_{i=1}^{k} μ_{i} ≤ ∑_{i=1}^{k} λ_{i} , k = 1, …, n,

we see that the e_{i}’s act as raising operators and the f_{i}’s as lowering operators. A weight vector is said to be a highest weight vector if it is annihilated by the e_{i}’s. M is called a highest weight module if it contains a highest weight vector v such that M = U_{q}(𝔤𝔩_{n}) v. If v is of weight λ, it follows that dim M_{λ} = 1 and M = ⊕_{μ≤λ}M_{μ}. One then shows that there exists for each partition λ of length ≤ n a unique highest weight finite-dimensional irreducible U_{q}(𝔤𝔩_{n})-module V_{λ}, with highest weight λ.

Example 2.1 The basic representation V = V_{(1)} of U_{q}(𝔤𝔩_{n}) is the n-dimensional vector space over K(q) with basis {v_{i}, 1 ≤ i ≤ n}, on which the action of U_{q}(𝔤𝔩_{n}) is as follows:

q^{ϵ_{i}}v_{j} = q^{δ_{ij}}v_{j}, e_{i}v_{j} = δ_{i+1 j}v_{i}, f_{i}v_{j} = δ_{ij}v_{i+1} .

Example 2.2 More generally, the U_{q}(𝔤𝔩_{n})-module V_{(1^{k})} is a \binom{n}{k}-dimensional vector space with basis {v_{c}} labelled by the subsets c of {1, …, n} with k elements (i.e. by the Young tableaux of shape (1^{k}) over {1, …, n}). The action of U_{q}(𝔤𝔩_{n}) on this basis is given by

q^{ϵ_{i}}v_{c} = \{ \begin{matrix}v_{c} & if i ∉ c \\ qv_{c} & otherwise \end{matrix} ,

e_{i}v_{c} = \{ \begin{matrix}0 & if i + 1 ∉ c or i ∈ c \\ v_{d} & otherwise, where d = (c \ \{i + 1\}) ∪ \{i\} \end{matrix} ,

f_{i}v_{c} = \{ \begin{matrix}0 & if i + 1 ∈ c or i ∉ c \\ v_{d} & otherwise, where d = (c \ \{i\}) ∪ \{i + 1\} \end{matrix} .

We see that the action of the lowering operators f_{i} does not depend on q, and can be recorded on a colored graph whose vertices are the column-shaped Young tableaux c and whose arrows are given by:

c ⟶^{i} d ⟺ f_{i}v_{c} = v_{d} .

Thus for k = 2, n = 4, one has the following graph:

12  13  14 23  2434 2  3 1  1 3  2

This is one of the simplest examples of crystal graphs (cf. Section 3).

In order to construct more interesting U_{q}(𝔤𝔩_{n})-modules, we use the tensor product operation. Given two U_{q}(𝔤𝔩_{n})-modules M, N, we can define a structure of U_{q}(𝔤𝔩_{n})- module on M ⊗ N by putting

q^{ϵ_{i}}(u ⊗ v) = q^{ϵ_{i}}u ⊗ q^{ϵ_{i}}v,  (12)
e_{i}(u ⊗ v) = e_{i}u ⊗ v + q^{−h_{i}}u ⊗ e_{i}v,  (13)
f_{i}(u ⊗ v) = f_{i}u ⊗ q^{h_{i}}v + u ⊗ f_{i}v.  (14)

Indeed, the formulas

Δq^{ϵ_{i}} = q^{ϵ_{i}} ⊗ q^{ϵ_{i}}, Δe_{i} = e_{i} ⊗ 1 + q^{−h_{i}} ⊗ e_{i}, Δf_{i} = f_{i} ⊗ q^{h_{i}} + 1 ⊗ f_{i},

make U_{q}(𝔤𝔩_{n}) into a bialgebra. One shows that the decomposition into irreducible components of the tensor product of two irreducible U_{q}(𝔤𝔩_{n})-modules is given by

V_{λ} ⊗ V_{μ} ≃ ⨁_{ν} c_{λ μ}^{ν} V_{ν} ,  (15)

where the c_{λ μ}^{ν} are the classical Littlewood-Richardson numbers. In particular, it follows that

V^{⊗k} ≃ ⨁_{ν⊢k} f_{ν} V_{ν} ,  (16)

where f_{ν} denotes the number of standard Young tableaux of shape ν.

Example 2.3 The n^{2}-dimensional U_{q}(𝔤𝔩_{n})-module V^{⊗2} decomposes into the q-symmetric square V_{(2)} and the q-alternating square V_{(1,1)}. For n = 2 this decomposition is described by the following diagram:

0 ⟵^{e_{1}} v_{1} ⊗ v_{1} ⟶^{f_{1}} v_{1} ⊗ v_{2} + qv_{2} ⊗ v_{1} ⟶^{f_{1}} (q + q^{−1}) v_{2} ⊗ v_{2} ⟶^{f_{1}} 0 ≃ V_{(2)}

0 ⟵^{e_{1}} v_{2} ⊗ v_{1} − qv_{1} ⊗ v_{2} ⟶^{f_{1}} 0 ≃ V_{(1,1)}

The algebra F_{q}[Mat_{n}] defined in Section 1 is also endowed with a natural structure of U_{q}(𝔤𝔩_{n})-module via the action defined by

q^{ϵ_{i}} t_{kl} = q^{δ_{il}} t_{kl}, e_{i} t_{kl} = δ_{i+1 l} t_{k l−1}, f_{i} t_{kl} = δ_{il} t_{k l+1},  (17)

and the Leibniz formulas

q^{ϵ_{i}}(P Q) = (q^{ϵ_{i}}P) . (q^{ϵ_{i}}Q),  (18)
e_{i}(P Q) = (e_{i}P) . Q + (q^{−h_{i}}P) . (e_{i}Q),  (19)
f_{i}(P Q) = (f_{i}P) . (q^{h_{i}}Q) + P . (f_{i}Q),  (20)

for P, Q in F_{q}[Mat_{n}]. This provides a very convenient realization of the irreducible modules V_{λ} as natural subspaces of F_{q}[Mat_{n}]. To describe it, we introduce some notations. We shall write y_{λ} for the unique Young tableau of shape and weight λ. This is the socalled Yamanouchi tableau of shape λ. Let τ be any Young tableau of shape λ. The quantum bitableau (y_{λ} | τ) will be simply denoted by (τ) and will be called a quantum tableau. This is a product of quantum minors taken on the first rows of the matrix T. Quantum tabloids are defined similarly. Finally, denote by T_{λ} the subspace of F_{q}[Mat_{n}] spanned by quantum tableaux (τ) of shape λ. Then one can show [19, 23] the following q-analogue of a classical result of Deruyts (see [9]).

Theorem 2.4 The subspace T_{λ} is invariant under the action of U_{q}(𝔤𝔩_{n}) on F_{q}[Mat_{n}], and is isomorphic as a U_{q}(𝔤𝔩_{n})-module to the simple module V_{λ}.

The action of U_{q}(𝔤𝔩_{n}) on T_{λ} is computed by means of the q-straightening formula. Namely, for column-shaped quantum tableaux one checks easily that the action coincides with the one previously described in Example 2.2. For general quantum tableaux we use Leibniz formulas (18) (19) (20), and when necessary we use the q-straightening algorithm (cf. Section 4) for converting the quantum tabloids of the right-hand side into a linear combination of quantum tableaux.

Example 2.5 We choose n = 3 and λ = (2, 1). T_{(2,1)} is 8-dimensional and one has for instance

f^{1}  =  + q  = (1 + q^{2})  −q^{3} 31 1  31 2  32 1  31 2  21 3

In this example, the quantum tableaux (τ) have been written for short τ (without brackets). This small abuse of notation will be used freely in the sequel.

This realization of V_{λ} is, up to some minor changes of convention, the same as the one described in [2] via the q-Young symmetrizers of the Hecke algebra of type A.

We denote by F_{q}[GL_{n}/B] the subspace of F_{q}[Mat_{n}] spanned by the quantum tableaux. It follows from the q-straightening formula that this is in fact a subalgebra of F_{q}[Mat_{n}]. It coincides for q = 1 with the ring of polynomial functions on the flag variety GL_{n}/B, hence the notation. The quantum deformation F_{q}[GL_{n}/B] has been studied by Lakshmibai, Reshetikhin [19] and Taft, Towber [29]. As a U_{q}(𝔤𝔩_{n})-module it decomposes into:

F_{q}[GL_{n}/B] ≃ ⨁_{ℓ(λ)≤n} V_{λ} .  (21)

Returning to F_{q}[Mat_{n}] and its linear basis formed by quantum bitableaux, we note that the action of U_{q}(𝔤𝔩_{n}) defined by (17) involves only the column indices of the variables t_{ij}. The defining relations (1) (2) (3) (4) being invariant under transposition of the matrix T, we see that we have another action of U_{q}(𝔤𝔩_{n}) given by

(q^{ϵ_{i}})^{†}t_{kl} = q^{δ_{ik}} t_{kl}, e_{i}^{†}t_{kl} = δ_{i+1 k} t_{k−1 l}, f_{i}^{†}t_{kl} = δ_{ik} t_{k+1 l},  (22)

(where the symbol † has been added to distinguish this action from the previous one), and the Leibniz formulas (18) (19) (20). These two actions obviously commute with each other, so that F_{q}[Mat_{n}] is now endowed with the structure of a (left) bimodule over U_{q}(𝔤𝔩_{n}). The quantum version of the Peter-Weyl theorem provides the decomposition [23]

F_{q}[Mat_{n}] ≃ ⨁_{ℓ(λ)≤n} V_{λ} ⊗ V_{λ} .  (23)

Here, the irreducible bimodule V_{λ} ⊗ V_{λ} is generated by applying all possible products of lowering operators f_{i}^{†}, f_{j} to the highest weight vector (y_{λ}|y_{λ}).

We end this Section by noting that every U_{q}(𝔤𝔩_{n})-module M can be regarded by restriction as a U_{q}(𝔰𝔩_{n})-module (that we still denote by M). In particular, the V_{λ} are also irreducible under U_{q}(𝔰𝔩_{n}). However we point out that, as U_{q}(𝔰𝔩_{n})-modules,

V_{λ} ≃ V_{μ} ⟺ λ_{i} − λ_{i+1} = μ_{i} − μ_{i+1} , i = 1, …, n − 1 .

Example 2.6 The U_{q}(𝔰𝔩_{2})-modules V_{(l)} will be very important in the sequel and we describe them precisely. For l ≥ 0, V_{(l)} is a (l + 1)-dimensional vector space over K(q) with basis {u_{k}, 0 ≤ k ≤ l}, on which the action of U_{q}(𝔰𝔩_{2}) is as follows:

q^{h_{1}} u_{k} = q^{l−2k} u_{k} , e_{1} u_{k} = [l − k + 1] u_{k−1} , f_{1} u_{k} = [k + 1] u_{k+1} .

In these formulas [m] denotes the q-integer (q^{m} − q^{−m})/(q − q^{−1}), and we understand u_{−1} = u_{l+1} = 0. Setting [m]! = [m][m − 1] ⋯ [1] and f_{1}^{(m)} = f_{1}^{m}/[m]!, we see that the basis {u_{k}} is characterized by u_{k} = f_{1}^{(k)} u_{0}. Also, we note that the weight spaces being one-dimensional, there is up to normalization a unique basis of V_{(l)} whose elements are weight vectors. The basis {u_{k}} may therefore be regarded as canonical. This will provide the starting point for defining the crystal basis of a U_{q}(𝔤𝔩_{n})-module.

3 Crystal bases

In this Section, we give, following [15], a self-contained introduction to crystal bases of U_{q}(𝔤𝔩_{n})-modules.

It follows from relations (6) (7) (8) (11) that for any i = 1, …, n − 1, the subalgebra U_{i} generated by e_{i}, f_{i}, q^{h_{i}}, q^{−h_{i}} is isomorphic to U_{q}(𝔰𝔩_{2}). Hence a U_{q}(𝔤𝔩_{n})-module M can be regarded by restriction to U_{i} as a U_{q}(𝔰𝔩_{2})-module. We shall assume from now on that the weight spaces M_{μ} are finite-dimensional, that M = ⊕_{μ}M_{μ}, and that for any i, M decomposes into a direct sum of finite-dimensional U_{i}-modules. Such modules M are said to be integrable. It follows from the representation theory of U_{q}(𝔰𝔩_{2}) that for any i, the integrable module M is a direct sum of irreducible U_{i}-modules V_{(l)}.

Example 3.1 Let M denote the U_{q}(𝔤𝔩_{3})-module V_{(2,1)} in the realization given by Theorem 2.4. As a U_{1}-module, M decomposes into 4 irreducible components, as shown by the following diagram:

12 1  12 2 13 1  13 2  12 3  2 2 3 12 3 13 3  23 3 e_{1} e_{1} e_{1} e_{1}  f_{1}  f_{1} f_{1}  f_{1}/[2]  f_{1} f_{1} f_{1}  f_{1} 0000  0  0 0  0 (1 + q^{2})  − q^{3}

On the other hand, as a U_{2}-module, M decomposes into:

1  1  3 f_{2}/[2]  f_{2} 0 2 3  3 2  1 3 + q f_{2} 0 12 1  1 113  23 3 e_{2} e_{2} e_{2} e_{2}  f_{2}  f_{2} f_{2} f_{2}  f_{2} 0000  00 3 2 2 2 2  1 − q  1 3 2  2 3

We observe that the U_{1}-decomposition leads to the basis

13 2  12 3 (1 + q^{2})  − q^{3}  12 3 (  ;  ) B^{1} =

for the 2-dimensional weight space M_{(1,1,1)}, while the U_{2}-decomposition leads to

1  1 2 3  3 2 + q  1  1 − q 3 2  2 3 (  ;  ) B^{2} =

These two bases are different and therefore one cannot find a basis B of weight vectors in M compatible with both decompositions. However, as noted by Kashiwara, ‘at q = 0’ the bases B_{1} and B_{2} coincide. The next definitions will allow us to state this in a more formal way.

Consider the simple U_{q}(𝔰𝔩_{2})-module V_{(l)} with basis {u_{k}} (cf. Example 2.6). Kashiwara [13, 14] introduces the endomorphisms ẽ, f̃ of V_{(l)} defined by

ẽu_{k} = u_{k−1} , f̃u_{k} = u_{k+1} , k = 0, …, l,

where u_{−1} = u_{l+1} = 0. More generally, if M is a direct sum of modules V_{(l)}, that is, if there exists an isomorphism of U_{q}(𝔰𝔩_{2})-modules ϕ : M ⟶^{∼} ⊕V_{(l)}^{⊕α_{l}}, one defines endomorphisms ẽ, f̃ of M by means of ϕ in the obvious way, and one checks easily that they do not depend on the choice of ϕ. In particular, if M is an integrable U_{q}(𝔤𝔩_{n})-module, regarding M as a U_{i}-module we define operators ẽ_{i}, f̃_{i} on M for i = 1, …, n − 1.

Example 3.2 We keep the notations of Example 3.1. We have

1  3 f̃_{2} 3 2  1 3 12 3 + q  f̃_{2} 0 12 3 1  − q 3 2

Hence,

31 3 31 3 12 3 13 2  f̃_{2} f̃_{2}  \frac{1}{1 + q^{2}} \frac{q}{1 + q^{2}}

Since we want to let q tend to 0, we introduce the subring A of K(q) consisting of rational functions without pole at q = 0. A crystal lattice of M is a free A-module L such that M = K(q) ⊗_{A} L, L = ⊕_{μ}L_{μ} where L_{μ} = L ∩ M_{μ}, and

ẽ_{i}L ⊂ L , f̃_{i}L ⊂ L , i = 1, …, n − 1 .  (24)

In other words, L spans M over K(q), L is compatible with the weight space decomposition of M and is stable under the operators ẽ_{i} and f̃_{i}. It follows that ẽ_{i}, f̃_{i} induce endomorphisms of the K-vector space L/qL that we shall still denote by ẽ_{i}, f̃_{i}. Now Kashiwara defines a crystal basis of M (at q = 0) to be a pair (L, B) where L is a crystal lattice in M and B is a basis of L/qL such that B = ⊔B_{μ} where B_{μ} = B ∩ (L_{μ}/qL_{μ}), and

ẽ_{i}B ⊂ B ⊔ {0} , f̃_{i}B ⊂ B ⊔ {0} , i = 1, …, n − 1 ,  (25)
ẽ_{i}v = u ⟺ f̃_{i}u = v, u, v ∈ B, i = 1, …, n − 1 .  (26)

Example 3.3 We continue Examples 3.1 and 3.2. Denote by B the basis of quantum tableaux in M, and let L be the A-lattice in M spanned by the elements of B. Let B be the projection of B in L/qL. Then, Example 3.1 shows that (L, B) is a crystal basis of M.

Kashiwara has proven the following existence and uniqueness result for crystal bases [13, 14].

Theorem 3.4 Any integrable U_{q}(𝔤𝔩_{n})-module M has a crystal basis (L, B). Moreover, if (L′, B′) is another crystal basis of M, then there exists a U_{q}(𝔤𝔩_{n})-automorphism of M sending L on L′ and inducing an isomorphism of vector spaces from L/qL to L′/qL′ which sends B on B′. In particular, if M = V_{λ} is irreducible, its crystal basis (L(λ), B(λ)) is unique up to an overall scalar multiple. It is given by

L(λ) = ∑_{1≤i_{1},i_{2},...,i_{r}≤n−1} A f̃_{i_{1}} f̃_{i_{2}} ⋯ f̃_{i_{r}} u_{λ},  (27)
B(λ) = {f̃_{i_{1}} f̃_{i_{2}} ⋯ f̃_{i_{r}} u_{λ} mod qL(λ) | 1 ≤ i_{1}, …, i_{r} ≤ n}\{0},  (28)

where u_{λ} is a highest weight vector of V_{λ}.

It follows that one can associate to each integrable U_{q}(𝔤𝔩_{n})-module M a well-defined colored graph Γ(M) whose vertices are labelled by the elements of B and whose edges describe the action of the operators f̃_{i} :

u ⟶^{i} v ⟺ f̃_{i}u = v .

Γ(M) is called the crystal graph of M.

2 1 1  3 1 1  3 1 2 2 1 2  1 3  3 2 2 3 2 3 3 1 3 2  1  1 2 1 2 2 1  2

Figure 1: Crystal graph of the U_{q}(𝔤𝔩_{3})-module V_{(2, 1)}

Example 3.5 The crystal graph of the U_{q}(𝔤𝔩_{3})-module V_{(2,1)} is readily deduced from Examples 3.1, 3.2 and 3.3. It is shown in Figure 1.

It is clear from this definition that the crystal graph Γ(M) of the direct sum M = M_{1} ⊕ M_{2} of two U_{q}(𝔤𝔩_{n})-modules is the disjoint union of Γ(M_{1}) and Γ(M_{2}). It follows from the complete reducibility of M that the connected components of Γ(M) are the crystal graphs of the irreducible components of M. Note also that if one restricts the crystal graph Γ(M) to its edges of colour i, one obtains a decomposition of this graph into strings of colour i corresponding to the U_{i}-decomposition of M. For a vertex v of Γ(M), we shall denote by ϵ_{i}(v) (resp. ϕ_{i}(v)) the distance of v to the origin (resp. end) of its string of colour i, that is,

ϵ_{i}(v) = max{k | ẽ_{i}^{k}v ≠ 0} , ϕ_{i}(v) = max{k | f̃_{i}^{k}v ≠ 0} .

The integers ϵ_{i}(v), ϕ_{i}(v) give information on the geometry of the graph Γ(M) around the vertex v. They seem to be very significant from a representation theoretical point of view. Indeed, both the Littlewood-Richardson multiplicities c_{λ μ}^{ν} and the q-weight multiplicities K_{λ μ}(q) can be computed in a simple way from the integers ϵ_{i}(v), ϕ_{i}(v) attached to the crystal graph Γ(V_{λ}) [1, 18].

One of the nicest properties of crystal bases is that they behave well under the tensor product operation. We shall first consider an example, from which Kashiwara deduces by induction the general description of the crystal basis of a tensor product [13].

Example 3.6 We slightly modify the notations of Example 2.6 and write {u_{k}^{(l)}, k = 0, …, l} for the canonical basis of the U_{q}(𝔰𝔩_{2})-module V_{(l)}. We recall that for convenience we set u_{−1}^{(l)} = u_{l+1}^{(l)} = 0. A first basis of the tensor product V_{(1)} ⊗ V_{(l)} is {u_{j}^{(1)} ⊗ u_{k}^{(l)}, j = 0, 1, k = 0, …, l}. We define

w_{k} = u_{0}^{(1)} ⊗ u_{k}^{(l)} + q^{l−k+1}u_{1}^{(1)} ⊗ u_{k−1}^{(l)} , k = 0, …, l + 1 ,  (29)
z_{k} = q^{l−k−1} [l − k] u_{1}^{(1)} ⊗ u_{k}^{(l)} − q^{l} [k + 1] u_{0}^{(1)} ⊗ u_{k+1}^{(l)} , k = 0, …, l − 1 . (30)

It is straightforward to check that e_{1}w_{0} = e_{1}z_{0} = 0, f_{1}w_{l+1} = f_{1}z_{l−1} = 0, and

f_{1}w_{k} = [k + 1] w_{k+1} , f_{1}z_{k} = [k + 1] z_{k+1} .

Hence {w_{k}} and {z_{k}} span submodules of V_{(1)} ⊗ V_{(l)} isomorphic to V_{(l+1)} and V_{(l−1)} respectively, and are the canonical bases of these irreducible representations of U_{q}(𝔰𝔩_{2}). Therefore, the A-lattice L spanned by {w_{k}}, {z_{k}} is a crystal lattice and if we define B = {w_{k} mod qL}⊔{z_{k} mod qL}, then (B, L) is a crystal basis of V_{(1)} ⊗V_{(l)}. On the other hand, equations (29) (30) show that L coincides with the tensor product L(1) ⊗ L(l) of the crystal lattices of V_{(1)} and V_{(l)}, and that

w_{k} ≡ u_{0}^{(1)} ⊗ u_{k}^{(l)} mod qL , k = 0, …, l , w_{l+1} ≡ u_{1}^{(1)} ⊗ u_{l}^{(l)} mod qL .
z_{k} ≡ u_{1}^{(1)} ⊗ u_{k}^{(l)} mod qL , k = 0, …, l − 1 .

Thus, (L, B) coincides with (L(1) ⊗ L(l), B(1) ⊗ B(l)), where we have denoted by B(1) ⊗ B(l) the basis {u_{j}^{(1)} ⊗ u_{k}^{(l)}, mod qL , j = 0, 1, k = 0, …, l}. Finally, the action of f̃_{1} on B(1) ⊗ B(l) is described by the crystal graph:

u_{0}^{(1)} ⊗ u_{0}^{(l)} → u_{0}^{(1)} ⊗ u_{1}^{(l)} → ⋯ → u_{0}^{(1)} ⊗ u_{l−1}^{(l)} → u_{0}^{(1)} ⊗ u_{l}^{(l)}
↓
u_{1}^{(1)} ⊗ u_{0}^{(l)} → u_{1}^{(1)} ⊗ u_{1}^{(l)} → ⋯ → u_{1}^{(1)} ⊗ u_{l−1}^{(l)}  u_{1}^{(1)} ⊗ u_{l}^{(l)}

More generally, we have the following property [13].

Theorem 3.7 Let (L_{1}, B_{1}) and (L_{2}, B_{2}) be crystal bases of integrable U_{q}(𝔤𝔩_{n})-modules M_{1} and M_{2}. Let B_{1} ⊗ B_{2} denote the basis {u ⊗ v, u ∈ B_{1}, v ∈ B_{2}} of (L_{1}/qL_{1}) ⊗ (L_{2}/qL_{2}) (which is isomorphic to (L_{1} ⊗ L_{2})/q(L_{1} ⊗ L_{2})). Then, (L_{1} ⊗ L_{2}, B_{1} ⊗ B_{2}) is a crystal basis of M_{1} ⊗ M_{2}, the action of ẽ_{i}, f̃_{i} on B_{1} ⊗ B_{2} being given by

f̃_{i}(u ⊗ v) = \{ \begin{matrix}u ⊗ f̃_{i}v & if & ϵ_{i}(u) < ϕ_{i}(v) \\ f̃_{i}u ⊗ v & if & ϵ_{i}(u) ≥ ϕ_{i}(v) \end{matrix} ,  (31)
ẽ_{i}(u ⊗ v) = \{ \begin{matrix}ẽ_{i}u ⊗ v & if & ϵ_{i}(u) > ϕ_{i}(v) \\ u ⊗ ẽ_{i}v & if & ϵ_{i}(u) ≤ ϕ_{i}(v) \end{matrix} .  (32)

Theorem 3.7 enables one to describe the crystal graph of V_{(1)}^{⊗m} for any m, and to deduce from that the description of the crystal graph Γ_{λ} of the simple U_{q}(𝔤𝔩_{n})-module V_{λ}. For convenience, we shall identify the tensor algebra T (V_{(1)}) with the free associative algebra K(q)⟨A⟩ over the alphabet A = {1, …, n} via the isomorphism v_{i} ↦ i, where {v_{i}} is the canonical basis of V_{(1)} defined in Example 2.1. Accordingly, the crystal lattice L spanned by the monomials in the v_{i} is identified with A⟨A⟩ and the K-vector space L/qL with K⟨A⟩.

We recall some terminology on words. A subword of a word w = x_{1} ⋯ x_{m} is a word of the form u = x_{i_{1}} ⋯ x_{i_{k}} with 1 ≤ i_{1} < ⋯ < i_{k} ≤ m. A factor of w is a subword consisting of consecutive letters of w.

Define linear operators ê_{i}, f̂_{i} on K⟨A⟩ in the following way. Consider first the case of a two-letter alphabet A = {i, i+1}. Let w = x_{1} ⋯ x_{m} be a word on A. Delete every factor ((i+1) i) of w. The remaining letters constitute a subword w_{1} of w. Then, delete again every factor ((i+1) i) of w_{1}. There remains a subword w_{2}. Continue this procedure until it stops, leaving a word w_{k} = x_{j_{1}} ⋯ x_{j_{r+s}} of the form w_{k} = i^{r}(i+1)^{s}. The image of w_{k} under ê_{i}, f̂_{i} is the word y_{j_{1}} ⋯ y_{j_{r+s}} given by

ê_{i}(i^{r}(i+1)^{s}) = \{ \begin{matrix}i^{r+1}(i+1)^{s−1} & (s ≥ 1) \\ 0 & (s = 0) \end{matrix} , f̂_{i}(i^{r}(i+1)^{s}) = \{ \begin{matrix}i^{r−1}(i+1)^{s+1} & (r ≥ 1) \\ 0 & (r = 0) \end{matrix} .

The image of the initial word w is then w′ = y_{1} ⋯ y_{m}, where y_{k} = x_{k} for k ∉ {j_{1} , …, j_{r+s}}. For instance, if

w = (2 1) 1 1 2 (2 1) 1 1 1 2 ,

we shall have

w_{1} = . . 1 1 (2 . . 1) 1 1 2 ,
w_{2} = . . 1 1 …. 1 1 2 .

Thus,

ê_{1}(w) = 2 1 1 1 2 2 1 1 1 1 1 ,
f̂_{1}(w) = 2 1 1 1 2 2 1 1 1 2 2 ,

where the letters printed in bold type are those of the image of the subword w_{2}. Finally, in the general case, the action of the operators ê_{i}, f̂_{i} on w is defined by the previous rules applied to the subword consisting of the letters i, i+1, the remaining letters being unchanged.

The operators ê_{i}, f̂_{i} have been considered in [21], where they were used as building blocks for defining noncommutative analogues of Demazure symmetrization operators. It follows from Theorem 3.7 that they coincide in the above identification with the endomorphisms ẽ_{i}, f̃_{i} on the K-space L/qL [16].

It is straightforward to deduce from the definition of ê_{i}, f̂_{i} the following compatibility properties with the Robinson-Schensted correspondence:

(a) for any word w on A such that ê_{i}w ≠ 0, we have Q(ê_{i}w) = Q(w),

(b) for any pair of words w, u such that P (w) = P (u) and ê_{i}w ≠ 0, we have P (ê_{i}w) = P (ê_{i}u).

In other words, the operators ê_{i}, f̂_{i} do not change the insertion tableau and are compatible with the plactic equivalence. Moreover, the words y such that ê_{i}y = 0 for any i are characterized by the Yamanouchi property: each right factor of y contains at least as many letters i than i + 1, and this for any i. It is well-known that for any standard Young tableau τ there exists a unique Yamanouchi word y such that Q(y) = τ. This yields the following crystallization of (16).

Theorem 3.8 The crystal graph of the U_{q}(𝔤𝔩_{n})-module V_{(1)}^{⊗m} is the colored graph whose vertices are the words of length m over A, and whose edges are given by:

w ⟶^{i} u ⟺ f̂_{i}w = u .

The connected components Γ_{τ} of Γ(V_{(1)}^{⊗m}) are parametrized by the set of Young tableaux τ of weight (1^{m}). The vertices of Γ_{τ} are those words w which satisfy Q(w) = τ. Moreover, if λ denotes the shape of τ, then Γ_{τ} is isomorphic to the crystal graph Γ(V_{λ}).

Replacing the vertices w of Γ_{τ} by their associated Young tableaux P (w), we obtain a labelling of Γ(V_{λ}) by the set of Young tableaux of shape λ, as shown in Example 3.5. It follows from property (b) above that this labelling does not depend on the particular choice of τ among the standard Young tableaux of shape λ. We end this section by showing a less trivial example of crystal graph, which is computed easily using the previous description of f̂_{i}.

Example 3.9 The crystal graph of the U_{q}(𝔤𝔩_{4})-module V_{(2,2)} is shown in Figure 2.

4 F_{q}[GL_{n}/B]

The subalgebra F_{q}[GL_{n}/B] of F_{q}[Mat_{n}] generated by quantum column-shaped tableaux can also be defined by generators and relations [29, 19]. The generators are denoted by columns

i_{k} ; ⋮ ; i_{2} ; i_{1} 1 ≤ k ≤ n, 1 ≤ i_{1}, …, i_{k} ≤ n,

and their products are written by juxtaposition. The relations are

(R_{1}) if i_{r} = i_{s} for some indices r, s, then

i_{k} ; ⋮ ; i_{2} ; i_{1} = 0 ,

(R_{2}) for w ∈ S_{k} and i_{1} < i_{2} < ⋯ < i_{k}, we have

i_{w_{k}} ; ⋮ ; i_{w_{2}} ; i_{w_{1}} = (−q)^{−ℓ(w)} i_{k} ; ⋮ ; i_{2} ; i_{1} ,

(R_{3}) for k ≤ l and j_{1} < j_{2} < ⋯ < j_{l}, we have

2  2  2 2  2  2  2 2  2  2 1  1  1 1  1  1 1  1 1  1 3  3  3 3  3  3 3 3 3  3 2 2 1 1  2 3 1 1  2 3 1 2  3 3 1 2  3 3 2 2 3 3 1 1 2 4 1 1  3 4 1 1 2 4 1 2  3 4 1 2 2 4 1 3  3 4 2 2 3 4 1 3  3 4 2 3 4 4 1 1  4 4 1 2  4 4 1 3 4 4 2 2  4 4 2 3  4 4 3 3

Figure 2: Crystal graph of the U_{q}(𝔤𝔩_{4})-module V_{(2, 2)}

i^{1} ⋮i_{k} j^{1} ⋮j_{k} j_{k+1} ⋮j_{l}  i^{1} ⋮i_{k} j_{w_{k+1}} ⋮j_{w_{l}} j^{w_{1}} ⋮ j_{w_{k}} = ∑_{w}(−q)^{ℓ(w)}

where the sum runs through all w ∈ S_{l} such that w_{1} < ⋯ < w_{k} and w_{k+1} < ⋯ < w_{l},

(R_{4}) for k + s ≤ l − 1 and j_{1} < j_{2} < ⋯ < j_{l}, we have

i^{1} ⋮i_{k−1} j_{w_{k+1}} j_{w_{k+2}} ⋮j_{w_{l}} j^{w_{1}} ⋮j_{w_{k−1}} j_{w_{k}} r_{1} ⋮r_{s} ∑_{w}(−q)^{ℓ(w)}  = 0

where the sum runs through all permutations w ∈ S_{l} such that w_{1} < ⋯ < w_{k} and w_{k+1} < ⋯ < w_{l}.

Relations (R_{1}), (R_{2}) express the q-alternating property of quantum minors, while relations (R_{3}), (R_{4}) are the natural q-analogues of Sylvester’s and Garnir’s identities respectively (cf. [22]). Using (R_{1}), (R_{2}), (R_{3}) one can express every element of F_{q}[GL_{n}/B] as a linear combination of products of columns, the size of which weakly decreases from left to right. After that, following the same strategy as in the classical straightening algorithm, one can by means of (R_{4}) express all such products as linear combinations of quantum tableaux. Note that it follows from (R_{3}), (R_{4}) that all the quantum tableaux (τ) appearing in the straightening of a given tabloid (δ) have the same shape λ obtained by reordering the sizes of the columns of δ, which means that (δ) falls in the irreducible component V_{λ} of F_{q}[GL_{n}/B].

Example 4.1 We apply the q-straightening algorithm to

(δ) = 15 236

It follows from (R_{1}), (R_{2}), (R_{3}) that

15 236  156 23  135 26  125 36 =  +  −q

Using (R_{4}) for straightening the first term of the right-hand side, we obtain

15 236 =(1 − q^{2}) 135 26  125 36  136 25  123 56 126 35 +(q^{3} − q)  + q  − q^{4} − q^{2}

Letting q tend to 0 in this expansion, we get an illustration of the next Theorem, which can be regarded as a version of Theorem 1.1 for F_{q}[GL_{n}/B].

Theorem 4.2 Let B denote the linear basis of F_{q}[GL_{n}/B] consisting of quantum tableaux, and let L be the K[q]-lattice generated by B. Let λ be a partition, and (δ) a quantum tabloid in V_{λ}. Denote by w the word obtained by reading the columns of δ from top to bottom and left to right. Then,

(δ) ≡ \{ \begin{matrix}(P (w)) & mod qL & if P(w) has shape λ \\ 0 & mod qL & otherwise \end{matrix} .

We shall not try, though this might be interesting, to derive Theorem 4.2 from a precise analysis of the q-straightening algorithm. The only consequence of this algorithm that we shall need is the following:

Proposition 4.3 Any quantum tabloid lies in the K[q, q^{−1}]-linear span of the set of quantum tableaux.

Our proof of Theorem 4.2 will be derived from the following result which describes several interesting bases of V_{λ}, and states that each of them gives rise to the same crystal basis at q = 0. We first introduce some notations. Let λ be a partition, λ′ = (λ′_{1}, …, λ′_{r}) its conjugate, and σ(λ′) = (λ′_{σ_{1}}, …, λ′_{σ_{r}}) the composition obtained by permuting the parts of λ′ using the permutation σ ∈ S_{r}. A tabloid δ is said to have shape σ(λ′) if it is a sequence of column-shaped Young tableaux (c_{1}, …, c_{r}), the size of the column c_{i} being equal to λ′_{σ_{i}}, i = 1, …, r. The column reading of δ is the word u_{δ} obtained by reading the columns of δ from top to bottom and left to right.

Theorem 4.4 For any σ ∈ S_{r}, the set of quantum tabloids

B_{σ} = {(δ) | δ has shape σ(λ′) and P (u_{δ}) has shape λ}

is a linear basis of V_{λ}. The A-lattice L spanned by B_{σ} is independent of σ as well as the projection B of B_{σ} in L/qL, and (L, B) is a crystal basis of V_{λ}. For (δ) ∈ B_{σ} and (γ) ∈ B_{ζ}, we have

(δ) ≡ (γ) mod qL ⟺ P (u_{δ}) = P (u_{γ}) .

Finally, if (δ) is such that P (u_{δ}) has not shape λ, then (δ) ≡ 0 mod qL.

Proof: We fix σ ∈ S_{r} and we write μ = (μ_{1}, …, μ_{r}) := σ(λ′). Recall from Example 2.2 that the q-analogue V_{(1^{k})} of the k th exterior power of the basic representation has a natural basis labelled by column-shaped Young tableaux. We introduce the K(q)-linear map φ_{μ}:

V_{(1^{μ_{1}})} ⊗ V_{(1^{μ_{2}})} ⊗ ⋯ ⊗ V_{(1^{μr})} ⟶ V_{λ}

b ; ⋮ ; a ⊗ d ; ⋮ ; ⋮ ; c ⊗ ⋯ ⊗ f ; ⋮ ; e ⟶ a ⋮b c⋮⋮d ⋯ e⋮f

Comparing (12) (13) (14) to (18) (19) (20) we see immediately that φ_{μ} commutes with the action of U_{q}(𝔤𝔩_{n}) and hence is in fact a morphism of U_{q}(𝔤𝔩_{n})-modules. The image V_{λ} is irreducible and by (15) it appears with multiplicity one in V_{(1^{μ_{1}})} ⊗ ⋯ ⊗ V_{(1^{μr})}. Therefore, the restriction of φ_{μ} to the irreducible component of V_{(1^{μ_{1}})} ⊗ ⋯ ⊗ V_{(1^{μr})} with highest weight vector the tensor product y^{μ} := (y_{(1^{μ_{1}})}) ⊗ ⋯ ⊗ (y_{(1^{μr})}) of all highest weight vectors in V_{(1^{μ_{1}})}, …, V_{(1^{μr})} is an isomorphism, and the kernel of φ_{μ} is the sum of all components V_{ν}, ν ≠ λ appearing in V_{(1^{μ_{1}})} ⊗ ⋯ ⊗ V_{(1^{μr})}.

We now turn to the crystal bases of these various U_{q}(𝔤𝔩_{n})-modules. It follows from Example 2.2 and Theorem 3.4 that, if we choose u_{(1^{k})} = y_{(1^{k})}, L(1^{k}) is the A-lattice spanned by the basis of column-shaped quantum tableaux, while B(1^{k}) is the projection of this basis in L(1^{k})/qL(1^{k}). Using Theorem 3.7 we deduce that a crystal basis of V_{(1^{μ_{1}})}⊗⋯⊗V_{(1^{μr})} can be constructed by tensoring the crystal bases of the factors. Denote this basis by (L^{μ}, B^{μ}). Then φ_{μ}(L^{μ}) is a crystal lattice in V_{λ}. According to Theorem 3.4 such a lattice is unique up to an overall scalar multiple which can be determined by considering the highest weight space. Here we have (L^{μ})_{λ} = A y^{μ} and φ_{μ}(y^{μ}) = (y_{λ}). Therefore, φ_{μ}(L^{μ}) is the crystal lattice L of V_{λ} specified by L_{λ} = A (y_{λ}), and it does not depend on σ. Now φ_{μ} induces an isomorphism from the K-subspace of L^{μ}/qL^{μ} spanned by the subset of B^{μ} consisting of those b in the connected component of the crystal graph with source y^{μ} mod qL^{μ}, to the K-space L/qL. It is easy to check from Theorem 3.7 and the explicit description of the operators ê_{i}, f̂_{i} which follows it that this connected component is labelled by the elements b = c_{1} ⊗ ⋯ ⊗ c_{r} mod L^{μ} such that the word u_{b} obtained by reading c_{1} from top to bottom, then c_{2} from top to bottom, and so on, satisfies: P (u_{b}) has shape λ. Hence its image is B_{σ} mod qL. This proves that B_{σ} is a basis of V_{λ} and that L = ∑_{b∈B_{σ}} A b. Moreover, (L, B_{σ} mod qL) is a crystal basis, which proves by unicity that B_{σ} mod qL does not depend on σ. On the other hand, the elements b of B^{μ} which belong to the other connected components are sent to 0 in L/qL. This means that the tabloids (δ) such that P (u_{δ}) has not shape λ belong to qL.

Finally, if ζ is another permutation and γ a tabloid of shape ζ(λ′), the fact that (δ) ≡ (γ) mod qL means exactly that the words u_{δ} and u_{γ} label the same vertex in the two copies of Γ(V_{λ}) to which they belong in Γ(V_{(1)}^{⊗k}), that is, by Theorem 3.8, P (u_{δ}) = P (u_{γ}). □

Proof of Theorem 4.2: Let (δ) be a quantum tabloid in V_{λ}. Proposition 4.3 shows that (δ) is a K[q, q^{−1}]-linear combination of quantum tableaux. On the other hand, Theorem 4.4 shows that (δ) belongs to the A-lattice L spanned by the set B = B_{id} of quantum tableaux. Therefore, (δ) is in fact an element of the K[q]-lattice L spanned by B. The other statements of Theorem 4.2 follow immediately from Theorem 4.4. □

We point out that the quantum tabloids (δ) ∈ B_{σ} are easily computed using Schützenberger’s jeu de taquin [28]. For example, the following graph shows the δ’s giving rise to quantum tabloids (δ) which are congruent to the quantum tableau (τ) modulo qL:

3 4 1 32 5 431 32 5  431 3 52  31 4 532 3 431 52  3 41 532 1  2  1 2  1  2 τ =

The edges labelled i connect tabloids δ, γ obtained one from the other by permuting the column lengths of the i th and (i+1) th columns by means of jeu de taquin. The column readings u_{δ} of these tabloids are distinguished words of the plactic class of u_{τ}, called frank words [21]. The combinatorics of frank words occurs in several interesting problems (see [21, 24, 8]).

5 Proof of Theorem 1.1

The proof of Theorem 1.1 follows the same lines as that of Theorem 4.2, namely we first describe several realizations of the crystal basis of the bimodule F_{q}[Mat_{n}] and then deduce Theorem 1.1 by comparing them, using the unicity property stated in Theorem 3.4.

We retain the notations of Section 4 (before Theorem 4.4). In particular, we fix a partition λ of k, and set μ = σ(λ′) for σ ∈ S_{r}. We denote by W_{λ} the subspace of F_{q}[Mat_{n}] whose decomposition as a U_{q}(𝔤𝔩_{n})-bimodule is W_{λ} ≃ ⊕_{ν≤λ}V_{ν} ⊗ V_{ν}. Thus, W_{(k)} is the homogeneous component of degree k of F_{q}[Mat_{n}]. For each ν ≤ λ, we choose a standard Young tableau τ_{ν} of shape ν. We can now state

Theorem 5.1 Let B_{λ,σ} denote the following set of quantum bitabloids:

B_{λ,σ} = {(δ|δ′) | δ, δ′ have shape μ and Q(u_{δ}) = Q(u′_{δ}) = τ_{ν} for some ν ≤ λ} .

Then B_{λ,σ} is a basis of W_{λ}. The A-lattice L_{λ} spanned by B_{λ,σ} does not depend on σ or on the particular choice of Young tableaux {τ_{ν}}. The projection B_{λ} of B_{λ,σ} in L_{λ}/qL_{λ} is also independent of σ, and (L_{λ}, B_{λ}) is a crystal basis of W_{λ}. Moreover for (δ|δ′) ∈ B_{λ,σ} and (γ|γ′) ∈ B_{λ,ζ}, we have

(δ|δ′) ≡ (γ|γ′) mod qL_{λ} ⟺ P (u_{δ}) = P (u_{γ}) and P (u_{δ′}) = P (u_{γ′}) .

Finally, the crystal graph attached to (L_{λ}, B_{λ}) is the coloured graph given by

(δ|δ′) ⟶^{i_{l}^{†}} (γ|δ′) ⟺ f_{i}^{†}(δ|δ′) = (γ|δ′) ⟺ f̂_{i}u_{δ} = u_{γ} ,

(δ|δ′) ⟶^{i_{r}} (δ|γ′) ⟺ f_{i}(δ|δ′) = (δ|γ′) ⟺ f̂_{i}u_{δ′} = u_{γ′} .

Proof: We imitate the proof of Theorem 4.4 and introduce the K(q)-linear map Φ_{μ}:

\begin{matrix}(V_{(1^{μ_{1}})} ⊗ ⋯ ⊗ V_{(1^{μr})}) ⊗ (V_{(1^{μ_{1}})} ⊗ ⋯ ⊗ V_{(1^{μr})}) & ⟶ & W_{λ} \\ (c_{1} ⊗ ⋯ ⊗ c_{r}) ⊗ (d_{1} ⊗ ⋯ ⊗ d_{r}) & ⟶ & (c_{1} ⋯ c_{r}|d_{1} ⋯ d_{r}) \end{matrix}

Here c_{i}, d_{j} denote elements of the canonical bases of V_{(1^{μ_{i}})}, V_{(1^{μ_{j}})}, i.e. columns of size μ_{i}, μ_{j}, and (c_{1} ⋯ c_{r}|d_{1} ⋯ d_{r}) is the quantum bitabloid formed on these columns. The map Φ_{μ} is in fact a homomorphism of U_{q}(𝔤𝔩_{n})-bimodules, and therefore sends the crystal lattice L_{λ,σ} spanned by the tensors (c_{1} ⊗ ⋯ ⊗ c_{r}) ⊗ (d_{1} ⊗ ⋯ ⊗ d_{r}) onto a crystal lattice L_{λ,σ} in W_{λ}. To describe precisely L_{λ,σ}, it is enough to determine its submodule L_{λ,σ}^{+} of highest weight vectors. We shall prove that L_{λ,σ}^{+} = ⊕_{ν≤λ}A (y_{ν}|y_{ν}).

To do this we have to introduce some notation. We write for short V^{μ} := V_{(1^{μ_{1}})} ⊗⋯⊗ V_{(1^{μr})}, and we consider a source vertex

y = y_{1} ; ⋮ ; y_{μ_{1}} ⊗ ⋯ ⊗ y_{k−μ_{r}+1} ; ⋮ ; y_{k}

of the crystal graph of V^{μ}. This means that y_{1} ⋯ y_{k} is a Yamanouchi word on {1, …, n} such that the columns of y are increasing from bottom to top. By definition of a crystal basis, there exists a highest weight vector T_{y} in V^{μ} such that T_{y} ≡ y mod qL_{λ,σ}. Now, let

w = w_{1} ; ⋮ ; w_{μ_{1}} ⊗ ⋯ ⊗ w_{k−μ_{r}+1} ; ⋮ ; w_{k}

be any monomial tensor of the same weight ν as y. Then Φ_{μ}(T_{y} ⊗ w) = α_{y,w}(q) (y_{ν}|y_{ν}) for some scalar α_{y,w}(q) ∈ K(q). Indeed,

e_{i}^{†}Φ_{μ}(T_{y} ⊗ w) = Φ_{μ}(e_{i}^{†}T_{y} ⊗ w) = Φ_{μ}((e_{i}T_{y}) ⊗ w) = 0 ,

and on the other hand Φ_{μ}(T_{y} ⊗ w) has weight (ν, ν). Therefore Φ_{μ}(T_{y} ⊗ w) is a scalar multiple of the highest weight vector (y_{ν}|y_{ν}). But from the definition of Φ_{μ}, we have

Φ_{μ}(T_{y} ⊗ w) = ∑_{u} κ_{u}(q) (u|w) .  (33)

Here w is the tabloid made of the columns of w, u runs through the tabloids of the same shape and weight as w, and κ_{u}(q) ∈ A. Moreover, κ_{y}(0) = 1 and κ_{u}(0) = 0 for u ≠ y. Expanding (33) on the basis

β_{w} = {t_{u_{1}w_{1}} ⋯ t_{u_{k}w_{k}} | u_{1} ⋯ u_{k} has weight ν and w_{i} = w_{j} ⟹ u_{i} ≤ u_{j}}

and comparing to the similar expansion of (y_{ν}|y_{ν}), we obtain by checking the coefficient of t_{w_{1}w_{1}} ⋯ t_{w_{k}w_{k}} that α_{y,w}(q) = κ_{w}(q). Therefore, Φ_{μ}(T_{y} ⊗w) ≡ δ_{w y} (y_{ν}|y_{ν}) mod q(y_{ν}|y_{ν}), and if y′ is another source vertex of Γ(V^{μ}), we have

Φ_{μ}(T_{y} ⊗ T_{y′}) ≡ δ_{y y′} (y_{ν}|y_{ν}) mod q(y_{ν}|y_{ν}) .  (34)

This proves that L_{λ,σ}^{+} = ⊕_{ν≤λ}A (y_{ν}|y_{ν}), as stated.

It follows that L_{λ,σ} does not in fact depend on σ or on {τ_{ν}}, and we may write L_{λ,σ} = L_{λ}. We can now consider the map induced by Φ_{μ} from L_{λ,σ}/qL_{λ,σ} to L_{λ}/qL_{λ} (we still denote it by Φ_{μ}). By (34), it maps to zero all the connected components of the crystal graph of V^{μ} ⊗ V^{μ} with source vertex y ⊗ y′ such that y ≠ y′. This means precisely that (δ|δ′) ≡ 0 mod qL_{λ} whenever Q(u_{δ}) ≠ Q(u_{δ′}). On the other hand, to each τ_{ν} corresponds a unique source vertex y = y(τ_{ν}) such that Q(u_{y}) = τ_{ν}. The vertices w ⊗ w′ of the connected components of Γ(V^{μ} ⊗ V^{μ}) with origin y(τ_{ν}) ⊗ y(τ_{ν}), ν ≤ λ, span a subspace of L_{λ,σ}/qL_{λ,σ} isomorphic under Φ_{μ} to L_{λ}/qL_{λ}. Therefore (L_{λ}, B_{λ,σ} mod qL_{λ}) is a crystal basis of W_{λ}, and this implies that B_{λ,σ} mod qL_{λ} is independent of σ. The other statements follow now easily from Theorem 3.8. □

Proof of Theorem 1.1: Denote by L the crystal lattice of F_{q}[Mat_{n}] whose submodule of highest weight vectors is equal to ⊕_{ν} A (y_{ν}|y_{ν}). It follows from the proof of Theorem 5.1 that the crystal lattice L_{λ} of W_{λ} is nothing but L ∩ W_{λ}. We also see that L is spanned over A by the set of bitableaux (τ | τ′). Indeed, if we choose τ_{λ} to be the standard Young tableau whose first column contains 1, 2, …, λ′_{1}, whose second column contains λ′_{1} + 1, …, λ′_{1} + λ′_{2}, and so on, we have

BT_{λ} := {(τ | τ′) | τ, τ′ are Young tableaux of shape λ} ⊂ B_{λ,id}

and BT_{λ} mod L_{λ} is the part of B_{λ} which labels the connected component of Γ(W_{λ}) corresponding to V_{λ} ⊗ V_{λ}. Therefore, (L, ⊔_{λ}BT_{λ} mod L) is a crystal basis of F_{q}[Mat_{n}] and L = ⊕_{λ} A BT_{λ}. On the other hand, taking λ = (k) in Theorem 5.1, we find that the set of monomials

B_{k} = {t_{i_{1}j_{1}} ⋯ t_{i_{k}j_{k}} | Q(i_{1} ⋯ i_{k}) = Q(j_{1} ⋯ j_{k}) = τ_{ν} for some ν}

gives rise to the same crystal basis under the guise (L, ⊔_{k}B_{k} mod L). Hence, applying again Theorem 3.4, it follows from the description of the crystal graph that

t_{i_{1}j_{1}} ⋯ t_{i_{k}j_{k}} ≡ \{ \begin{matrix}(P (i_{1} ⋯ i_{k})|P (j_{1} ⋯ j_{k})) & mod qL & if Q(i_{1} ⋯ i_{k}) = Q(j_{1} ⋯ j_{k}) \\ 0 & mod qL & otherwise \end{matrix} (35)

Finally, Proposition 4.3 extends to the case of bitableaux [10], that is, the coefficients of the straightening of a bitabloid belong to K[q, q^{−1}]. Since we have just proved that they also belong to A, we can replace in (35) the crystal lattice L by the K[q]-lattice L spanned by the quantum bitableaux. □

References

[1] A. D. Berenstein, A. V. Zelevinsky, Canonical bases for the quantum group of type A_{r} and piecewise-linear combinatorics, Preprint Institut Gaspard Monge, 1994.

[2] C. Burdík, R. C. King, T. A. Welsh, The explicit construction of irreducible representations of the quantum algebras U_{q}(sl_{n}), preprint 1993.

[3] V. Chari, A. Pressley, A guide to quantum groups, Cambridge Universty Press, 1994.

the electronic journal of combinatorics 3 (2) (1996), #R11 23

[4] E. Date, M. Jimbo, T. Miwa, Representations of U_{q}(gl_{n}) at q = 0 and the Robinson-Schensted correspondence, in Physics and mathematics of strings, Memorial volume of V. Knizhnik, L. Brink, D. Friedan, A.M. Polyakov eds., World Scientific, 1990.

[5] J. Désarménien, An algorithm for the Rota straightening formula, Discrete Math. 30 (1980), 51-68.

[6] J. Désarménien, J.P.S. Kung, G.C. Rota, Invariant theory, Young bitableaux and combinatorics, Adv. Math. 27 (1978), 63-92.

[7] V. G. Drinfeld, Hopf algebras and the quantum Yang-Baxter equation, Soviet Math. Dokl. 32 (1985), 254-258.

[8] W. Fulton, A. Lascoux, A Pieri formula in the Grothendieck ring of a flag bundle, Duke Math. J., 76 (1994), 711-729.

[9] J.A. Green, Classical invariants and the general linear group, in Representation theory of finite groups and finite dimensional algebras, G.O. Michler, C.M. Ringel eds., Progress in Mathematics 95, Birkhäuser, 1991.

[10] R.Q. Huang, J.J. Zhang, Standard basis theorem for quantum linear groups, Adv. Math. 102 (1993), 202-229.

[11] M. Jimbo, A q-difference analogue of U(g) and the Yang-Baxter equation, Lett. Math. Phys. 10 (1985), 63-69.

[12] M. Jimbo, A q-analogue of U(gl(N + 1)), Hecke algebra, and the Yang-Baxter equation, Lett. Math. Phys. 11 (1986), 247-252.

[13] M. Kashiwara, Crystalizing the q-analogue of universal enveloping algebras, Commun. Math. Phys. 133 (1990), 249-260.

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

[15] M. Kashiwara, Crystallization of quantized enveloping algebras, Sugaku Expositiones, 7 (1994), 99-115.

[16] M. Kashiwara, T. Nakashima, Crystal graphs for representations of the q-analogue of classical Lie algebras, J. Algebra, 165 (1994), 295-345.

[17] D.E. Knuth, Permutations, matrices and generalized Young tableaux, Pacific. J. Math. 34 (1970), 709-727.

[18] A. Lascoux, B. Leclerc, J.Y. Thibon, Crystal graphs and q-analogues of weight multiplicities for root systems of type A_{n}, Lett. Math. Phys. to appear.

[19] V. Lakshmibai, N. Yu. Reshetikhin, Quantum deformations of SL_{n}/B and its Schubert varieties, in Special Functions, ICM-90 Satellite Conference Proceedings, M. Kashiwara, T. Miwa eds., Springer.

[20] A. Lascoux, M. P. Schützenberger, Le monoïde plaxique, in Noncommutative structures in algebra and geometric combinatorics A. de Luca Ed., Quaderni della Ricerca Scientifica del C. N. R., Roma, 1981

[21] A. Lascoux, M.P. Schützenberger, Keys and standard bases, in Invariant theory and tableaux, D. Stanton ed., Springer, 1990.

[22] B. Leclerc, On identities satisfied by minors of a matrix, Adv. in Math., 100 (1993), 101-132.

[23] M. Noumi, H. Yamada, K. Mimachi, Finite dimensional representations of the quantum group GL_{q}(n; C) and the zonal spherical functions on U_{q}(n − 1)\U_{q}(n), Japan. J. Math., 19 (1993), 31-80.

the electronic journal of combinatorics 3 (2) (1996), #R11 24

[24] V. Reiner, M. Shimozono, Key polynomials and a flagged Littlewood-Richardson rule, J. Comb. Theory A, 70 (1995), 107-143.

[25] N.Y. Reshetikhin, L.A. Takhtadzhyan, L.D. Faddeev, Quantization of Lie groups and Lie algebras, Leningrad Math. J.,1 (1990), 193–225.

[26] G. de B. Robinson, On the representation theory of the symmetric group, Amer. J. Math. 60 (1938), 745-760.

[27] C. Schensted, Longest increasing and decreasing subsequences, Canad. J. Math. 13 (1961), 179-191.

[28] M. P. Schützenberger, La correspondance de Robinson, in Combinatoire et représentation du groupe symétrique, Strasbourg 1976, D. Foata ed., Springer Lect. Notes in Math. 579.

[29] E. Taft, J. Towber, Quantum deformation of flag schemes and Grassman schemes I – A q-deformation of the shape-algebra for GL(n), J. of Algebra, 142 (1991), 1–36.