**Noncommutative Symmetric Functions IV:**

**Quantum Linear Groups and Hecke Algebras at q** = **0**

**Quantum Linear Groups and Hecke Algebras at q**

DANIEL KROB dk@litp.ibp.fr

*LIAFA (CNRS), Universit´e Paris 7, 2, place Jussieu, 75251 Paris Cedex 05, France*

JEAN-YVES THIBON jyt@univ-mlv.fr

*IGM, Universit´e de Marne-la-Vall´ee, 2, rue de la Butte-Verte, 93166 Noisy-le-Grand Cedex, France*
*Received March 28 , 1996; Revised July 30, 1996*

**Abstract.** We present representation theoretical interpretations of quasi-symmetric functions and noncommu-
*tative symmetric functions in terms of quantum linear groups and Hecke algebras at q*=0. We obtain in this
way a noncommutative realization of quasi-symmetric functions analogous to the plactic symmetric functions of
Lascoux and Sch¨utzenberger. The generic case leads to a notion of quantum Schur function.

**Keywords:** quasisymmetric function, quantum group, Hecke algebra

**1.** **Introduction**

This paper, which is intended as a sequel to [6, 9, 21], is devoted to the representation
theoretical interpretation of noncommutative symmetric functions and quasi-symmetric
functions. These objects, which are two different generalizations of ordinary symmetric
functions [9, 10], build up two Hopf algebras dual to each other, and have been shown
*to provide a Frobenius type theory for Hecke algebras of type A at q* = 0, playing the
same rˆole as the classical correspondence between symmetric functions and characters of
symmetric groups [7] (which extends to the case of the generic Hecke algebra).

In the classical case, the interpretation of symmetric functions in terms of representations of symmetric groups is equivalent, via Schur-Weyl duality, to the fact that Schur functions are the characters of the irreducible polynomial representations of general linear groups.

*Equivalently, instead of working with polynomial representations of GL*(*n*), one can use
*comodules over the Hopf algebra of polynomial functions over GL*(*n*)[11]. This Hopf
*algebra is known to admit interesting q-deformations (quantized function algebras; see [8]*

*for instance) to which Schur-Weyl duality can be extended for generic values of q, the*
symmetric group being replaced by the Hecke algebra.

*The standard version of the quantum linear group is not defined for q* =0. The theory of
*crystal bases [16], which allows to “take the limit q* →0” in certain modules by working
with renormalized operators modulo a lattice, describes the combinatorial aspects of the
generic case, and provides illuminating interpretations of classical constructions such as
the Robinson-Schensted correspondence, the Littlewood-Richardson rule and the plactic
monoid [3, 17, 24, 26].

P1: RPS/PCY P2: MVG/ASH QC: MVG

Journal of Algebraic Combinatorics KL472-03-Krob August 6, 1997 10:34

340 KROB AND THIBON

However, another version exists [4] which plays an equivalent rˆole for generic values of
*q, but in which one can specialize q to 0. This specialization is quite different of what is*
obtained with crystal bases, and leads to an new interpretation of quasi-symmetric functions
and noncommutative symmetric functions analogous to the interpretation of ordinary sym-
*metric functions as polynomial characters of GL*(*n*). Moreover, this interpretation allows
to give a realization of quasi-symmetric functions similar to the plactic interpretation of
symmetric functions (see Section 6.2). The plactic algebra is here replaced by one of its
quotients, and instead of ordinary Young tableaux one has to use skew tableaux of ribbon
shape, and dual objects called quasi-ribbons, for which Schensted type algorithms can be
constructed. In fact, most aspects of the classical theory can be adapted to this highly
degenerate case. As this is an example of a non-semisimple case for which everything can
be worked out explicitely, one can expect that this treatment could serve as a guide for
understanding the more complicated degeneracies at roots of unity.

This paper is structured as follows. We first recall the basic definitions concerning non-
commutative symmetric functions and quasisymmetric functions (Section 2) and review the
Frobenius correspondence for the generic Hecke algebras (Section 3). Next we introduce
*the Dipper-Donkin version of the quantized function algebra of the space of n*×*n matrices*
(Section 4). We describe some interesting subspaces (Sections 4.5 and 4.6), and prove that
*the q* = 0 specialization of the diagonal subalgebra is a quotient of the plactic algebra,
which we call the hypoplactic algebra (Section 4.7). Next, we review the representation
theory of the 0-Hecke algebra and its interpretation in terms of quasi-symmetric functions
and noncommutative symmetric functions, providing the details which were omitted in [7].

*In Section 6, we introduce a notion of noncommutative character for A**q*(*n*)-comodules, and
*prove that these characters live in the diagonal subalgebra. For generic q, the characters of*
*irreducible comodules are quantum analogues of Schur functions. For q*=0, we show that
*hypoplactic analogues of the fundamental quasi-symmetric functions F**I* (quasi-ribbons)
*can be obtained as the characters of irreducible A*0(*n*)comodules, and give a similar con-
struction for the ribbon Schur functions. These constructions lead to degenerate versions
of the Robinson-Schensted correspondence, which are discussed in Section 7.

**2.** **Noncommutative symmetric functions and quasi-symmetric functions**

*2.1.* *Noncommutative symmetric functions*

*The algebra of noncommutative symmetric functions [9] is the free associative algebra*
**Sym** = Qh*S*1,*S*2, . . .i generated by an infinite sequence of noncommutative indetermi-
*nates S**k**, called the complete symmetric functions. One defines S** ^{I}*=

*S*

*i*

_{1}

*S*

*i*

_{2}· · ·

*S*

*i*

*for any*

_{r}*composition I*=(

*i*1,

*i*2, . . . ,

*i*

*r*)∈(N

^{∗})

*. The family(*

^{r}*S*

*)*

^{I}**is a linear basis of Sym. Although**

**it is convenient to define Sym as an abstract algebra, a useful realisation can be obtained**

*by taking an infinite alphabet A*= {

*a*1,

*a*2, . . .}and defining its complete homogeneous symmetric functions by

−→Y

*i*≥1

(1−*ta**i*)^{−}^{1}=X

*n*≥0

*t*^{n}*S**n*(*A*) (1)

Although these elements are not symmetric for the usual action of permutations on the
free algebra, they are invariant under the Lascoux-Sch¨utzenberger action of the symmetric
group [23], which can now be interpreted as a particular case of Kashiwara’s action of the
*Weyl group on the U** _{q}*(sln)-crystal graph of the tensor algebra [24].

*The set of all compositions of a given integer n is equipped with the reverse refinement*
*order, denoted*¹*. For instance, the compositions J of 4 such that J*¹(1,2,1)are exactly
*(1, 2, 1), (3, 1), (1, 3) and (4). The ribbon Schur functions*(*R** _{I}*)can then be defined by

*S** ^{I}* =X

*J*¹*I*

*R**J* or *R**I* =X

*J*¹*I*

(−1)^{`(}^{I}^{)−`(}^{J}^{)}*S** ^{J}*,

where`(*I*)*denotes the length of I . The family*(*R**I*)**is another homogeneous basis of Sym.**

*The commutative image of a noncommutative symmetric function F is the ordinary*
*symmetric function f obtained by applying to F the algebra morphism which maps S**n*to
*the complete homogeneous function h**n*(our notations for commutative symmetric functions
*will be those of [28]). The ribbon Schur function R** _{I}* is then mapped to the corresponding

*ordinary ribbon Schur function, which will be denoted by r*

*.*

_{I}Ordinary symmetric functions are endowed with an extra product∗, called the internal
product, which corresponds to the multiplication of central functions on the symmetric
group. A noncommutative analog of this product can be defined, the character ring ofS* _{n}*
being replaced by its descent algebra [35] (see also below) .

*Recall that i is said to be a descent of*σ∈S*n* ifσ (*i*) > σ(*i* +1). The set Des(σ )of
*these integers is called the descent set of*σ*. If I* =(*i*1, . . . ,*i**r*)*is a composition of n, one*
*associates with it the subset D*(*I*)= {*d*1, . . . ,*d**r*−1}of [1,*n*−*1] defined by d**k*=*i*1+ · · · +*i**k*

*for k*∈[1,*r*−*1]. Let D**I* be the sum inZ[S*n**] of all permutations with descent set D*(*I*).
*As shown by Solomon [35], the D**I* form a basis of a subalgebra ofZ[S*n**] called the descent*
*algebra of*S*n*and denoted by6*n*. One can define an isomorphism of graded vector spaces

α**: Sym**=M

*n*≥0

**Sym*** _{n}* →6=M

*n*≥0

6*n*

by settingα(*R** _{I}*)=

*D*

*. Observe thatα(*

_{I}*S*

*)*

^{I}*is then equal to D*

_{⊆}

*, i.e., to the sum of all permutations ofS*

_{I}

_{n}*whose descent set is contained in D*(

*I*).

*2.2.* *Quasi-symmetric functions*

As proved in [29] (see also [9]), the algebra of noncommutative symmetric functions is
in natural duality with the algebra of quasi-symmetric functions, introduced by Gessel in
*[10]. Let X*= {*x*1,*x*2, . . . ,*x**n* · · ·}be a totally ordered set of commutative indeterminates.

*An element f* ∈ C*[X ] is said to be a quasi-symmetric function if for each composition*
*K* =(*k*1, . . . ,*k**m*)*all the monomials x*_{i}^{k}_{1}^{1}*x*_{i}^{k}_{2}^{2}· · ·*x*_{i}^{k}_{m}^{m}*with i*1 <*i*2 <· · ·<*i**m*have the same
*coefficient in f . The quasi-symmetric functions form a subalgebra QSym of*C*[X ].*

*One associates with a composition I* =(*i*_{1}, . . . ,*i** _{m}*)

*the quasi-monomial function*

*M**I* = X

*j*_{1}<···<*j*_{m}

*x*^{i}_{j}^{1}

1· · ·*x*^{i}_{j}^{m}

*m*.

P1: RPS/PCY P2: MVG/ASH QC: MVG

Journal of Algebraic Combinatorics KL472-03-Krob August 6, 1997 10:34

342 KROB AND THIBON

*The family of quasi-monomial functions is clearly a basis of QSym. Another important*
*basis of QSym is formed by quasi-ribbon functions which are defined by*

*F**I* =X

*I*¹*J*

*M**J*,

*e.g., F*122= *M*122+*M*1112+*M*1211+*M*11111. The pairingh·,·i* between Sym and QSym*
[29] is then defined byh

*S*

*,*

^{I}*M*

*J*i =δ

*IJ*or equivalently byh

*R*

*I*,

*F*

*J*i =δ

*IJ*. This duality is essentially equivalent to the noncommutative Cauchy identity

−→Y

*i*≥1

Ã_{−→}

Y

*j*≥1

(1−*x**i**a**j*)^{−}^{1}

!

=X

*I*

*F**I*(*X*)*R**I*(*A*), (2)

and can also be interpreted as the canonical duality between Grothendieck groups asociated to 0-Hecke algebras [7] (see Section 5).

**3.** **Hecke algebras and their representations**

*3.1.* *Hecke algebras*

*The Hecke algebra H**N*(*q*)*of type A**N*−1is theC(*q*)*-algebra generated by N*−1 elements
(*T**i*)*i*=1,*N*−1with relations

*T*_{i}^{2}=(*q*−1)*T**i*+*q* *for i* ∈[1,*N*−1],
*T**i**T**i*+1*T**i*=*T**i*+1*T**i**T**i*+1 *for i* ∈[1,*N* −2],
*T**i**T**j* =*T**j**T**i* for |*i*− *j*|>1.

*The Hecke algebra H**N*(*q*)is a deformation of theC-algebra of the symmetric groupS*N*

*(obtained for q* =*1). For generic complex values of q, it is isomorphic to*C[S*N*] (and
*hence semi-simple) except when q* =*0 or when q is a root of unity. The first relation is*
often replaced by

*T*_{i}^{2}=(*q*−*q*^{−}^{1})*T**i*+1 (3)

*which is invariant under the substitution q* → −*q*^{−}^{1} and is more convenient for working
with Kazhdan-Lusztig polynomials and canonical bases. However the convention adopted
here, i.e.,

*T*_{i}^{2}=(*q*−1)*T** _{i}*+

*q*, (4)

*is the natural one when q is interpreted as the cardinality of a finite field and H** _{N}*(

*q*)as

*the endomorphism algebra of the permutation representation of GL*

*(F*

_{N}*q*)on the set on

*complete flags [14]. Moreover one can specialize q*= 0 in relation (4). In the modular

*representation theory of GL*

*N*(F

*q*), the Hecke algebra corresponding to this specialization

*occurs when q is a power of the characteristic of the ground field. For this reason, among*
*others, it is interesting to consider the 0-Hecke algebra H**N*(0) which is theC-algebra
*obtained by specialization of the generic Hecke algebra H** _{N}*(

*q*)

*at q*=0. This algebra is therefore presented by

*T*_{i}^{2}= −*T**i* *for i* ∈[1,*N* −1],
*T**i**T**i*+1*T**i*=*T**i*+1*T**i**T**i*+1 *for i* ∈[1,*N* −2],
*T**i**T**j* =*T**j**T**i* for |*i*− *j*|>1.

*The representation theory of H**N*(0)was investigated by Norton who obtained a fairly
*complete picture [31]. Important specific features of the type A are described by Carter*
in [1]. The 0-Hecke algebra can also be realized as an algebra of operators acting on the
equivariant Grothendieck ring of the flag manifold [22].

*3.2.* *The Frobenius correspondence*

We will see that the 0-Hecke algebra is the right object for giving a representation theoretical interpretation of noncommutative symmetric functions and of quasi-symmetric functions.

To emphasize the parallel with the well-known correspondence between representations of the symmetric group and symmetric functions, we first recall the main points of the classical theory.

*Let Sym be the ring of symmetric functions and let*
*R[S]*= M

*N*≥0

*R[S**N*]

be the ring of equivalence classes of finitely generated C[S*N*]-modules (with sum and
product corresponding to direct sum and induction product). We know from the work of
Frobenius that the character theory of the symmetric groupS* _{N}* can be described in terms

*of the characteristic map*F

*: R[S]*→

*Sym which sends the class of a Specht module V*

_{λ}

*to the Schur function s*

_{λ}. The first point is thatFis a ring homomorphism. That is,

F³

*[U*⊗*V ]* ↑^{S}_{S}^{N+M}

*N*×S*M*

´=F(*[U ]*)F(*[V ]*)

for a S*N**-module U and a* S*M**-module V . The second one is the character formula,*
which can be stated as follows: for any finite dimensionalS*N**-module V , the value of the*
*chararacter of V on a permutation of the conjugacy class labelled by the partition*µis equal
to the scalar product

χ(µ)= hF(*V*),*p*_{µ}i

*where p*_{µ}*is the product of power sums p*_{µ}_{1}· · ·*p*_{µ}* _{r}*.

*This theory can be extended to the Hecke algebra H** _{N}*(

*q*)

*when q is neither 0 nor a root*

*of unity. The characteristic map is independent of q, and still maps the q-Specht module*

P1: RPS/PCY P2: MVG/ASH QC: MVG

Journal of Algebraic Combinatorics KL472-03-Krob August 6, 1997 10:34

344 KROB AND THIBON

*V*_{λ}(*q*)*to the Schur function s*_{λ}. The induction formula remains valid and the character
formula has to be modified as follows (see [2, 18, 19, 32, 36, 37]). Define for a partition
µ=(µ1, µ2, . . . , µ*r*)*of N the element*

wµ=¡

σ1· · ·σµ1−1

¢¡σµ1+1· · ·σµ1+µ2−1

¢· · ·¡

σµ1+···+µ*r−1*+1· · ·σ*N*−1

¢

(whereσ*i*is the elementary transposition(*i i*+1)*). The character formula for H**N*(*q*)gives
the valueχ_{µ}^{λ}*on T*_{w}_{µ}*of the character of the irreducible q-Specht module V*_{λ}(*q*). It reads

χ_{µ}^{λ}=tr_{V}_{λ}_{(}_{q}_{)}¡
*T*_{w}_{µ}¢

= hF(*V*_{λ}(*q*)),*C*_{µ}(*q*)i = h*s*_{λ},*C*_{µ}(*q*)i

*where C*_{µ}(*q*)=(*q*−1)^{l}^{(µ)}*h*^{µ}((*q* −1)*X*)(inλ*-ring notation, h*^{µ}((*q* −1)*X*)denotes the
*image of the homogeneous symmetric function h*^{µ}(*X*)*under the ring homomorphism p** _{k}* 7→

(*q** ^{k}*−1)

*p*

*).*

_{k}**4.** **The quantum coordinate ring A****q****(n)**

*4.1.* *Tensor representations of H**N**(q)*
*Let E*= {*e*_{1}, . . . ,*e** _{n}*}be a finite set and let

*V* =
M*n*

*i*=1

C(*q*)*e**i*

be theC(*q*)-vector space with basis(*e**i*)**. For v**=*e**k*_{1}⊗· · ·⊗*e**k** _{N}* ∈

*V*

^{⊗}

^{N}*and i*∈[1,

*N*−1],

**we define v**

^{σ}

*by setting*

^{i}**v**^{σ}* ^{i}* =

*e*

*k*

_{1}⊗ · · ·

*e*

*k*

*⊗*

_{i−1}*e*

*k*

*⊗*

_{i+1}*e*

*k*

*⊗*

_{i}*e*

*k*

*⊗ · · · ⊗*

_{i+2}*e*

*k*

*.*

_{N}*Following [4, 5, 15], one defines a right action of H**N*(*q*)*on V*^{⊗}* ^{N}* by

**v**·*T**i* =**v**^{σ}^{i}*if k**i* <*k**i*+1,
**v**·*T** _{i}* =

**qv***if k*

*=*

_{i}*k*

_{i}_{+}

_{1},

**v**·

*T*

*=*

_{i}

**qv**^{σ}

*+(*

^{i}*q*−1)

**v**

*if k*

*>*

_{i}*k*

_{i}_{+}

_{1}. This is a variant of Jimbo’s action [15] itself defined by

**v**·*T**i* =*q*^{1}^{/}^{2}**v**^{σ}^{i}*if k**i* <*k**i*+1,
**v**·*T**i* =**qv***if k**i* =*k**i*+1,
**v**·*T**i* =*q*^{1}^{/}^{2}**v**^{σ}* ^{i}*+(

*q*−1)

**v**

*if k*

*i*>

*k*

*i*+1.

Let(*e*_{i}^{∗})1≤*i*≤*n* *be the basis of V*^{∗}dual to the basis(*e**i*)*of V . The dual (right) action of*
*H**N*(*q*)on(*V*^{∗})^{⊗}* ^{N}*is given by

**v**^{∗}·*T** _{i}* =

*q*(

**v**

^{∗})

^{σ}

^{i}*if k*

*<*

_{i}*k*

_{i}_{+}

_{1},

**v**

^{∗}·

*T*

*=*

_{i}

**qv**^{∗}

*if k*

*=*

_{i}*k*

_{i}_{+}

_{1},

**v**

^{∗}·

*T*

*=(*

_{i}**v**

^{∗})

^{σ}

*+(*

^{i}*q*−1)

**v**

^{∗}

*if k*

*>*

_{i}*k*

_{i}_{+}

_{1}.

**Example 4.1** *Let V* =C(*q*)*e*1⊕C(*q*)*e*2*. The matrices describing the right action of T*1

*on V* ⊗*V and on V*^{∗}⊗*V*^{∗}in the canonical bases of these spaces are

*R*ˇ=

*q* 0 0 0

0 0 *q* 0

0 1 *q*−1 0

0 0 0 *q*

, *R*ˇ^{∗} =

*q* 0 0 0

0 0 1 0

0 *q* *q*−1 0

0 0 0 *q*

.

*We also need the left actions of H**N*(*q*)*on V*^{⊗}* ^{N}* and(

*V*

^{∗})

^{⊗}

*defined by*

^{N}½*T**i*·**v**= −* qv*·

*T*

_{i}^{−}

^{1}= −

**v**·

*T*

*i*+(

*q*−1)

**v**,

*T*

*·*

_{i}**v**

^{∗}= −

**qv**^{∗}·

*T*

_{i}^{−}

^{1}= −

**v**

^{∗}·

*T*

*+(*

_{i}*q*−1)

**v**

^{∗}.

**Equivalently, for v**=

*e*

_{k}_{1}⊗ · · · ⊗

*e*

_{k}*∈(*

_{N}*V*)

^{⊗}

^{N}**and v**

^{∗}=

*e*

_{k}^{∗}

1⊗ · · · ⊗*e*^{∗}_{k}

*N* ∈(*V*^{∗})^{⊗}* ^{N}*,

*T**i*·**v**= −**v**^{σ}* ^{i}*+(

*q*−1)

**v**,

*T*

*i*·

**v**

^{∗}= −

*q*(

**v**

^{∗})

^{σ}

*+(*

^{i}*q*−1)

**v**

^{∗}

*if k*

*i*<

*k*

*i*+1,

*T*

*i*·

**v**= −

**v**,

*T*

*i*·

**v**

^{∗}= −

**v**

^{∗}

*if k*

*i*=

*k*

*i*+1,

*T*

*i*·

**v**= −

**qv**^{σ}

*,*

^{i}*T*

*i*·

**v**

^{∗}= −(

**v**

^{∗})

^{σ}

^{i}*if k*

*i*>

*k*

*i*+1.

*4.2.* *The Hopf algebra A**q**(n)*

*The quantum group A**q*(*n*)is theC(*q*)*-algebra generated by the n*^{2}elements(*x**i j*)1≤*i*,*j*≤*n*

subject to the defining relations

*x**j k**x**il* =*q x**il**x**j k* *for i* < *j*, *k*≤*l*,
*x*_{i k}*x** _{il}*=

*x*

_{il}*x*

_{i k}*for every i*,

*k*,

*l*,

*x*

_{jl}*x*

*−*

_{i k}*x*

_{i k}*x*

*=(*

_{jl}*q*−1)

*x*

_{il}*x*

_{j k}*for i*<

*j*,

*k*<

*l*.

This algebra is a quantization of the Hopf algebra of polynomial functions on the variety
*of n*×*n matrices introduced by Dipper and Donkin in [4]. It is not isomorphic to the*
classical quantization of Faddeev-Reshetikin-Takhtadzhyan [8], and although for generic
*values of q both versions play essentially the same rˆole, an essential difference is that the*
*Dipper-Donkin algebra is defined for q* =0.

*A**q*(*n*)is a Hopf algebra with comultiplication1defined by
1(*x**i j*)=

X*n*
*k*=1

*x**i k*⊗*x**k j*.

P1: RPS/PCY P2: MVG/ASH QC: MVG

Journal of Algebraic Combinatorics KL472-03-Krob August 6, 1997 10:34

346 KROB AND THIBON

Moreover one can define a left coactionδ*of A**q*(*n*)*on V*^{⊗}* ^{N}*by
δ(

*e*

*)=*

_{i}X*n*
*j*=1

*x** _{i j}*⊗

*e*

_{j}*and the following property shows that A** _{q}*(

*n*)is related to the Hecke algebras in a similar

*way as GL*

*and the symmetric groups.*

_{n}**Proposition 4.2 [4]** *The left coaction*δ*of A** _{q}*(

*n*)

*on V*

^{⊗}

^{N}*commutes with the right action*

*of H*

*(*

_{N}*q*)

*on V*

^{⊗}

^{N}*. That is*,

*the following diagram is commutative*

*V*^{⊗}^{N}^{δ}^{⊗N} → *A** _{q}*(

*n*)⊗

*V*

^{⊗}

^{N}*h*

↓ ↓

*Id*⊗*h*

*V*^{⊗}* ^{N}* →

*A*

*(*

_{q}*n*)⊗

*V*

^{⊗}

^{N}δ^{⊗N}

*for every element h*∈*H**N*(*q*)*considered as an endomorphism of V*^{⊗}^{N}*.*

*This property still holds for q* =*0. Thus, for any h* ∈ *H**N*(0)*, V*^{⊗}^{N}*h will be a sub-*
*A*0(*n*)*-comodule of V*^{⊗}* ^{N}*. This is this property which will allow us to define a plactic-like
realization of quasi-symmetric functions. For later reference, note that the defining relations

*of A*0(

*n*)are

*x**j k**x**il* =0 *for i* < *j*, *k*≤*l*,
*x**i k**x**il* =*x**il**x**i k* *for every i*,*k*,*l*,
*x**jl**x**i k*=*x**i k**x**jl*−*x**il**x**j k* *for i* < *j*, *k*<*l*.

(5)

*4.3.* *Some notations for the elements of A**q**(n)*

*Each generator x**i j**of A**q*(*n*)will be identified with a two row array and with an element of
*V* ⊗*V*^{∗}modulo certain relations as described below:

*x** _{i j}* =

·*i*
*j*

¸

=*e** _{i}*⊗

*e*

^{∗}

*.*

_{j}**For i**=(*i*1, . . . ,*i**r*)**, j** =(*j*1, . . . ,*j**r*)∈ [1,*n]*^{r}*, let e***i** =*e**i*1⊗ · · · ⊗*e**i**r* *and e*^{∗}** _{j}** =

*e*

^{∗}

_{j}_{1}⊗ · · ·

⊗*e*^{∗}_{j}

*r**. One can then identify the monomial x*** _{ij}** =

*x*

_{i}_{1}

_{j}_{1}· · ·

*x*

_{i}

_{r}

_{j}

_{r}*of A*

*(*

_{q}*n*)with the two row array

·*i*1 *i*2 · · · *i**r*

*j*1 *j*2 · · · *j**r*

¸ ,

*itself regarded as the class of the tensor e***i**⊗*e*_{j}^{∗}∈*T** ^{r}*(

*V*⊗

*V*

^{∗})modulo the relations (

*e*

**⊗**

_{i}*e*

^{∗}

**≡**

_{j}*e*

^{σ}

_{i}*⊗(*

^{r}*e*

_{j}^{∗}·

*T*

*)*

_{r}*for each r such that i*

*>*

_{r}*i*

_{r}_{+}

_{1},

*e*** _{i}**⊗

*e*

^{∗}

**≡**

_{j}*e*

**⊗(**

_{i}*e*

^{∗}

**)**

_{j}^{σ}

^{r}*for each r such that i*

*=*

_{r}*i*

_{r}_{+}

_{1}. (6) These relations are equivalent to

*e***i**⊗*e*_{j}^{∗}≡ −*T**r* ·*e***i**⊗(*e*^{∗}** _{j}**)

^{σ}

^{r}*for each r such that j*

*r*≤

*j*

*r*+1. (7)

*4.4.*

*Linear bases of A*

*q*

*(n)*

**For every i**=(*i*1, . . . ,*i**r*)∈[1,*n]*^{r}*, let I*(**i**)∈N* ^{n}*be defined by

*I*(

**i**)

*p*=Card{

*i*

*,*

_{k}*k*∈[1,

*r ]*,

*i*

*=*

_{k}*p*}

*for p*∈[1,*n]. For I*,*J* ∈N* ^{n}*, set

*A*

*q*(

*I*,

*J*)= X

*I*(**i**)=*I*,*I*(**j**)=*J*

C(*q*)*x***ij**.

Observe that(*A** _{q}*(

*I*,

*J*))

*I*,

*J*∈N

^{n}*defines a grading of A*

*(*

_{q}*n*)compatible with multiplication.

A monomial basis compatible with this grading is constructed in [4]. The basis vectors,
*which are labelled by matrices M*=(*m** _{i j}*)1≤

*i*,

*j*≤

*n*∈M

*n*(N)are

*x**M* =¡

*x*_{11}^{m}^{11}*x*_{12}^{m}^{12}· · ·*x*_{1n}^{m}* ^{1n}*¢

· · ·¡

*x*_{n1}^{m}^{n1}*x*_{n2}^{m}* ^{n2}*· · ·

*x*

_{nn}

^{m}*¢*

^{nn}∈ *A**q*(*n*).

It will be useful to introduce another monomial basis(*x** ^{M}*)

*of A*

*q*(

*n*), labelled by the same matrices, and defined by

*x** ^{M}*=¡

*x*_{1n}^{m}^{1n}*x*^{m}_{2n}* ^{2n}*· · ·

*x*

_{nn}

^{m}*¢*

^{nn}· · ·¡

*x*_{11}^{m}^{11}*x*_{21}^{m}^{21} · · · *x*_{n1}^{m}* ^{n1}*¢

∈ *A**q*(*n*).

**Proposition 4.3** *For any q*∈C,*the family*(*x** ^{M}*)

*M*∈M

*n*(N)

*is a homogeneous linear basis*

*of A*

*q*(

*n*)

*.*

**Proof:** *It is clearly sufficient to prove that each basis element x** _{M}* can be expressed in

*terms of the x*

*. Using the array and tensor notations, such an element can be represented by*

^{N}*x** _{M}* =

·· · · *i*_{1} *i*_{2} · · ·

· · · *j*1 *j*2 · · ·

¸

=*e*** _{i}**⊗

*e*

^{∗}

**,**

_{j}*where j*1 *is the maximal element of the second row of this array and where i*1 ≤ *i*2. The
*maximality of j*1and relation (7) imply

*x**M* =(−1)^{`(σ)}*T*_{σ}*e***i**⊗*e***j** =

µ(−1)^{l}^{(σ)}*T*_{σ}
*Id*

¶

·

·*i*1 · · · *i*2 · · ·
*j*1 · · · *j*2 · · ·

¸

P1: RPS/PCY P2: MVG/ASH QC: MVG

Journal of Algebraic Combinatorics KL472-03-Krob August 6, 1997 10:34

348 KROB AND THIBON

for some permutationσ*. By induction on the length of x**M*, there exists some other permu-
tationτ such that

*x**M* =

µ(−1)^{l}^{(τ)}*T*_{τ}
*Id*

¶

·

·*i*1 · · · *i**r* · · · *k*1 · · · *k**s*

*j*1 · · · *j*1 · · · 1 · · · 1

¸ .

*Going back to the definition of the left action of H**N*(*q*)and to relations (6), this implies
*that x**M*is aZ*[q]-linear combination of elements of the form*

·*i*1 · · · *i**r* · · · *k*1 · · · *k**s*

*n* · · · *n* · · · 1 · · · 1

¸ ,

from which the conclusion follows immediately. 2

*4.5.* *The standard subspace of A**q**(n)*

*The restrictions to the standard component of A** _{q}*(

*n*)of the transition matrices between the two bases(

*x*

*)and(*

_{M}*x*

*)have an interesting description.*

^{M}**Definition 4.4** *The standard subspace S**q*(*n*)*of A**q*(*n*)is
*S**q*(*n*)=*A**q*(1* ^{n}*,1

*)= M*

^{n}σ∈S*n*

C(*q*)*x*_{σ}

*where x*_{σ} =*x*1σ (1)*x*2σ (2)· · ·*x**n*σ(*n*)forσ ∈S*n*.

The following result is an immediate consequence of Proposition 4.3.

**Proposition 4.5** *One has*
*S**q*(*n*)= M

σ∈S*n*

C(*q*)*x*^{σ}

*where x*^{σ} =*x*_{σ(}*n*)*n* · · · *x*_{σ (}2)2*x*_{σ (}1)1*.*

The elements of the transition matrices between the two bases(*x*_{σ})_{σ∈}S*n* and(*x*^{σ})_{σ∈}S*n*

*of S**q*(*n*)*are R-polynomials. Recall that the family*(*R*_{τ,σ}(*q*))_{σ,τ∈}S*n* *of R-polynomials is*
defined by

(*T*_{σ}−1)^{−}^{1}=ε(σ)*q*^{−}^{l}^{(σ )} X

τ≤σ

ε(τ)*R*_{τ,σ}(*q*)*T*_{τ}∈*H**n*(*q*)

forσ ∈S_{n}*(cf. [13]). The R-polynomial R*_{τ,σ}(*q*)is inZ*[q], has degree l*(σ)−*l*(τ)and
its constant term isε(σ τ).

**Proposition 4.6** *The bases*(*x*^{σ})*and*(*x*_{σ})*are related by*
*x*^{σ} =X

τ≤σ

*R*_{τ,σ}(*q*)*x*_{ωτ} *and* *x*_{σ} =X

τ≤σ

*R*_{τ,σ}(−*q*)*x*^{ωτ}

*where*ω=(*n n*−1· · ·1)*and where*≤*is the Bruhat order.*

**Proof:** In the notation of Section 4.3, we can write
*x*^{σ} =*e*_{σ}⊗*e*_{ω}^{∗} =*e*^{σ}_{12}_{···}* _{n}*⊗

*e*

^{∗}

_{ω}≡

*e*12···

*n*⊗

*e*

^{∗}

_{ω}·

*T*

_{σ}−1

≡*e*12···*n*⊗(−*q*)^{l}^{(σ )}*T*_{σ}^{−}_{−1}^{1} ·*e*^{∗}_{ω}≡ *e*12···*n*⊗
ÃX

τ≤σ

ε(τ)*R*_{τ,σ}(*q*)*T*_{τ}

!

·*e*_{ω}^{∗}

≡*e*12···*n*⊗
ÃX

τ≤σ

*R*_{τ,σ}(*q*)*e*_{ωτ}^{∗}

!

=X

τ≤σ

*R*_{τ,σ}(*q*)*x*_{ωτ}.

The second relation can be proved in the same way. 2

**Corollary 4.7** *In A*_{0}(*n*),*one has*
*x*^{σ} =X

τ≤σ

ε(στ)*x*_{ωτ} *and* *x*_{σ} =X

τ≤σ

ε(σ τ)*x*_{ωτ}.

*4.6.* *Decomposition of left and right standard subspaces at q*=*0*

In the array notation, the standard subspace is spanned by arrays whose both rows are
permutations. If one requires one row to be a fixed permutationσ, one obtains the left and
*right subcomodules of A**q*(*n*)which are independent ofσ*for generic q, but not for q*=0.

**Definition 4.8** *The left and right standard subspaces of A**q*(*n*), respectively denoted by
*L**q*(*n*)*and R**q*(*n*), are defined by

*L**q*(*n*)= M

*J*=(*j*1,...,*j**n*)∈N^{n}

C(*q*)*x*1,*j*_{1}*x*2,*j*_{2}· · ·*x**n*,*j** _{n}*,

*R*

*q*(

*n*)= M

*I*=(*i*_{1},...,*i** _{r}*)∈N

^{r}C(*q*)*x**i** _{n}*,

*n*· · ·

*x*

*i*

_{2},2

*x*

*i*

_{1},1.

We associate with a permutationσ ∈S*n**the subspaces of A**q*(*n*)
*L**q*(*n*;σ)= X

*J*=(*j*1,...,*j**n*)∈N^{n}

C(*q*)*x*_{σ(}1),*j*_{1}*x*_{σ(}2),*j*_{2}· · ·*x*_{σ(}*n*),*j** _{n}*,

*R*

*(*

_{q}*n*;σ)= X

*I*=(*i*_{1},...,*i** _{r}*)∈N

^{r}C(*q*)*x*_{i}_{n}_{,σ(}_{n}_{)}· · ·*x*_{i}_{2}_{,σ(}_{2}_{)}*x*_{i}_{1}_{,σ(}_{1}_{)}.

*For generic q, all the left (resp. right) subspaces are the same.*

P1: RPS/PCY P2: MVG/ASH QC: MVG

Journal of Algebraic Combinatorics KL472-03-Krob August 6, 1997 10:34

350 KROB AND THIBON

**Proposition 4.9** *If q* ∈C*is nonzero and not a root of unity*,
*L**q*(*n*;σ )=*L**q*(*n*) *and* *R**q*(*n*;σ )=*R**q*(*n*).

**Proof:** Using the tensor notation of Section 4.3, we can write

*e*_{σ}⊗*e*^{∗}* _{J}* =

*e*

^{σ}

_{12}

_{···}

*⊗*

_{n}*e*

^{∗}

*≡*

_{J}*e*

_{12}

_{···}

*⊗*

_{n}*e*

^{∗}

*·*

_{J}*T*

_{σ}−1≡(

*e*

_{12}

_{···}

*⊗*

_{n}*e*

^{∗}

*)·(*

_{J}*Id*⊗

*T*

_{σ}−1)

*for every J* ∈N^{n}*, so that L**q*(*n*;σ) ⊂ *L**q*(*n*)*. Moreover the asumptions on q imply that*
*T*_{σ}−1is invertible. The previous relation can therefore be read as

*e*_{12}_{...}* _{n}*⊗

*e*

^{∗}

*≡(*

_{J}*e*

_{σ}⊗

*e*

^{∗}

*)·(*

_{J}*Id*⊗(

*T*

_{σ}−1)

^{−}

^{1}),

*from which we get that L** _{q}*(

*n*)⊂

*L*

*(*

_{q}*n*;σ ). The second equality is obtained in the same

way. 2

*When q* = *0, the subspaces L*0(*n*;σ )*and R*0(*n*;σ )*are not equal to L*0(*n*)*and R*0(*n*).
*However, the proof of Proposition 4.9 shows that L*0(*n*;σ)⊂*L*0(*n*)*and R*0(*n*;σ)⊂*R*0(*n*).
*The subspaces L*0(*n*;σ )*(resp. R*0(*n*;σ )*are right (resp. left) sub- A*0(*n*)*-comodules of L*0(*n*)
*(resp. R*0(*n*)), of which they form a filtration with respect to the weak order on the symmetric
group. To prove this, let us introduce some notations. We associate to an integer vector
*I* =(*i*_{1}, . . . ,*i** _{n}*)ofN

*the two sets*

^{n}Inv(*I*)= {(*k*,*l*),1≤*k*<*l* ≤*n*−1,*i**k*>*i**l*},
Pos(*I*)= {(*k*,*l*),1≤*k*<*l* ≤*n*−1,*i** _{k}*<

*i*

*}.*

_{l}**Proposition 4.10** *For every permutation*σ ∈S*n*,*one has*
*L*0(*n*;σ )= M

*J*=(*j*1,...,*j**n*)
Inv(σ)⊂Inv(*J*)

C*x*_{σ (}1),*j*_{1}· · ·*x*_{σ(}*n*),*j** _{n}*,

*R*0(*n*;σ )= M

*I*=(*i*_{1},...,*i** _{n}*)
Pos(

*I*)⊂Pos(σ)

C*x**i** _{n}*,σ(

*n*)· · ·

*x*

*i*

_{1},σ(1).

**Proof:** We only show the first identity, the second one being proved in the same way.

**Lemma 4.11** *Let l*≥*1 be such that*σ(*i*) > σ (*i*+*l*)*and j**i*≤ *j**i*+*l**. Then*,*in A*0(*n*)
*x*_{σ (}*i*),*j** _{i}*· · ·

*x*

_{σ(}

*i*+

*l*),

*j*

*=0.*

_{i+l}**Proof of the lemma:** *The result is obvious when l*=*1. Let then l*≥2 and suppose that
*the result holds for l*−1. Two cases are to be considered.

1) σ(*i*+*l*−1) > σ(*i*+*l*)*. If j**i*+*l*−1≤ *j**i*+*l*, one clearly has

*x*_{σ(}*i*),*j** _{i}*· · ·

*x*

_{σ(}

*i*+

*l*),

*j*

*=*

_{i+l}*x*

_{σ (}

*i*),

*j*

*· · ·*

_{i}*x*

_{σ(}

*i*+

*l*−1),

*j*

_{i+l−1}*x*

_{σ (}

*i*+

*l*),

*j*

*=0.*

_{i+l}*On the other hand, if j**i*+*l*−1> *j**i*+*l*, we can write

*x*_{σ(}_{i}_{),}_{j}* _{i}*· · ·

*x*

_{σ(}

_{i}_{+}

_{l}_{),}

_{j}*=*

_{i+l}*x*

_{σ(}

_{i}_{),}

_{j}*· · ·*

_{i}*x*

_{σ(}

_{i}_{+}

_{l}_{),}

_{j}

_{i+l}*x*

_{σ (}

_{i}_{+}

_{l}_{−}

_{1}

_{),}

_{j}

_{i+l−1}−*x*_{σ(}*i*),*j** _{i}*· · ·

*x*

_{σ (}

*i*+

*l*),

*j*

_{i+l−1}*x*

_{σ(}

*i*+

*l*−1),

*j*

*.*

_{i+l}*We have here j*

*i*≤

*j*

*i*+

*l*−1so that the right hand side is zero, as required.

2) σ(*i*+*l*−1) < σ (*i*+*l*). Thusσ (*i*) > σ (*i*+*l*−1)and we just have to check the case
*j** _{i}* >

*j*

_{i}_{+}

_{l}_{−}

_{1}

*. Then, j*

_{i}_{+}

_{l}_{−}

_{1}<

*j*

_{i}_{+}

*so that*

_{l}*x*_{σ(}*i*),*j** _{i}*· · ·

*x*

_{σ(}

*i*+

*l*),

*j*

*=*

_{i+l}*x*

_{σ(}

*i*),

*j*

*· · ·*

_{i}*x*

_{σ(}

*i*+

*l*),

*j*

_{i+l}*x*

_{σ (}

*i*+

*l*−1),

*j*

_{i+l−1}+*x*_{σ(}*i*),*j**i*· · ·*x*_{σ (}*i*+*l*−1),*j*_{i+l}*x*_{σ (}*i*+*l*),*j** _{i+l−1}*,

which is indeed zero by induction. 2

It follows from the lemma that
*L*0(*n*;σ) = X

*J*=(*j*_{1},...,*j** _{n}*)
Inv(σ )⊂Inv(

*J*)

C*x*_{σ (}1),*j*_{1}· · ·*x*_{σ (}*n*),*j** _{n}*,

*and it remains to prove that the sum is direct. Let J*=(*j*1, . . . ,*j**n*)∈N* ^{n}*such that Inv(σ)⊂
Inv(

*J*). Using the same argument as in the proof of Proposition 4.6 we can write

*x*_{σ (}1),*j*_{1}· · ·*x*_{σ(}*n*),*j** _{n}* =

*e*

_{σ}⊗

*e*

^{∗}

*=*

_{J}*e*

^{σ}

_{12}

_{···}

*⊗*

_{n}*e*

^{∗}

*≡*

_{J}*e*12···

*n*⊗(

*e*

^{∗}

*·*

_{J}*T*

_{σ}−1)

=X

τ≤σ

ε(σ τ)*e*_{12}_{···}* _{n}*⊗

*e*

_{J}_{·τ}

where≤is the Bruhat order onS*n**and J*·τ =(*j*_{τ(}1), . . . ,*j*_{τ(}*n*)). This last formula clearly
shows that the family(*x*_{σ(}1),*j*1· · ·*x*_{σ (}*n*),*j**n*)Inv(σ)⊂Inv(*J*)is free. 2
*We can now prove that the “left cells” L*_{0}(*n*;σ)form a filtration of the right comodule
*L*_{0}(*n*)with respect to the weak order.

**Proposition 4.12** *Let*σ ∈ S*n* *and let i* ∈ [1,*n*−*1] such that*σ(*i*) > σ (*i* +1)*. Then*
*L*0(*n*;σ)*is strictly included into L*0(*n*;σ σ*i*)*.*

**Proof:** *The inclusion L*0(*n*;σ )⊂*L*0(*n*;σ σ*i*)is immediate. Thus it suffices to show that
**this inclusion is strict. One can easily construct an element x**∈*L*0(*n*;σ σ*i*)**of the form x**=

· · · *x*_{σ(}_{i}_{+}_{1}_{),}_{k}*x*_{σ (}_{i}_{),}* _{k}*· · ·Using the formalism of Section 4.3, one checks that(

*T*

*⊗*

_{i}*Id*)·

**x**=

−**x**6=0. On the other hand,(*T** _{i}*⊗

*Id*)·

*L*

_{0}(

*n*;σ )=

**0. Thus x**∈/

*L*

_{0}(

*n*;σ). 2

*4.7.* *The diagonal subalgebra and the quantum pseudoplactic algebra*

**Definition 4.13** *The quantum diagonal algebra*1*q*(*n*)*is the subalgebra of A**q*(*n*)gener-
*ated by x*11, . . . ,*x**nn*.

P1: RPS/PCY P2: MVG/ASH QC: MVG

Journal of Algebraic Combinatorics KL472-03-Krob August 6, 1997 10:34

352 KROB AND THIBON

*The character theory of A**q*(*n*)-comodules described in Section 6 will show that the
noncommutative algebra1*q*(*n*)contains a subalgebra isomorphic to the algebra of ordinary
symmetric polynomials, exactly as in the case of the plactic algebra.

**Definition 4.14** *Let A be a totally ordered alphabet. The quantum pseudoplactic algebra*
*PPl** _{q}*(

*A*)is the quotient ofC(

*q*)h

*A*iby the relations

*qaab*−(*q*+1)*aba*+*baa*=0 *for a*<*b*,
*qabb*−(*q*+1)*baa*+*bba*=0 *for a*<*b*,
*cab*−*acb*−*bca*+*bac*=0 *for a*<*b*<*c*.

*The third relation is the Lie relation [[a*,*c]*,*b]*=*0 where [x*,*y] is the usual commutator*
*xy*−*yx. For q* =*1, the first two relations become [a*,*[a*,*b]]*=*[b*,*[b*,*a]]*=*0 and PPl*1(*A*)
is the universal enveloping algebra of the Lie algebra defined by these relations.

It should be noted that the classical plactic algebra is not obtained by any specialization
*of PPl** _{q}*(

*A*)

*. The motivation for the introduction of PPl*

*(*

_{q}*A*)comes from the following conjecture.

**Conjecture 4.15** *Let A* = {*a*1, . . . ,*a**n*}*be a totally ordered alphabet of cardinality n.*

*For generic q*,*the mapping*ϕ*: a**i* →*x**ii**induces an isomorphism between PPl**q*(*A*)*and the*
*diagonal algebra*1*q*(*n*)*.*

*Our conjecture is stated for generic values of q, i.e., when q is considered as a free*
variable, or avoiding a discrete set inC. It is clearly not true for arbitrary complex values
*of q. For example, for q* = 1, the diagonal algebra11(*n*)is an algebra of commutative
*polynomials. The diagonal algebra at q*=0 is also particularly interesting, and its structure
will be investigated in the forthcoming section.

*4.8.* *The hypoplactic algebra*

*Let again A be a totally ordered alphabet. We recall that the plactic algebra on A is the*
C*-algebra Pl*(*A*), quotient ofCh*A*iby the relations

½*aba*=*baa*, *bba*=*bab* *for a*<*b*,
*acb*=*cab*, *bca*=*bac* *for a*<*b*<*c*.

These relations, which were obtained by Knuth [20], generate the equivalence relation
*identifying two words which have the same P-symbol under the Robinson-Schensted cor-*
*respondence. Though Schensted had shown that the construction of the P-symbol is an*
associative operation on words, the monoid structure on the set of tableaux has been mostly
studied by Lascoux and Sch¨utzenberger [23] under the name ‘plactic monoid’. These au-
thors showed, for example, that the Littlewood-Richardson rule is essentially equivalent to
the fact that plactic Schur functions, defined as sums of all tableaux with a given shape,
are the basis of a commutative subalgebra of the plactic algebra. This point of view is now