• 検索結果がありません。

Character Formulas for q-Rook Monoid Algebras

N/A
N/A
Protected

Academic year: 2022

シェア "Character Formulas for q-Rook Monoid Algebras"

Copied!
25
0
0

読み込み中.... (全文を見る)

全文

(1)

Character Formulas for q-Rook Monoid Algebras

MOMAR DIENG momar@math.ucdavis.edu

Department of Mathematics, University of California, Davis, CA 95616, USA

TOM HALVERSON halverson@macalester.edu

Department of Mathematics and Computer Science, Macalester College, Saint Paul, Minnesota 55105, USA

VAHE POLADIAN vahe.poladian@cs.cmu.edu

Department of Computer Science, Carnegie Mellon University, Pittsburg, PA 15231, USA Received March 5, 2002; Revised August 19, 2002

Abstract. Theq-rook monoidRn(q) is a semisimpleC(q)-algebra that specializes whenq 1 toC[Rn], whereRnis the monoid ofn×nmatrices with entries from{0, 1}and at most one nonzero entry in each row and column. We use a Schur-Weyl duality betweenRn(q) and the quantum general linear groupUqgl(r) to compute a Frobenius formula, in the ring of symmetric functions, for the irreducible characters ofRn(q). We then derive a recursive Murnaghan-Nakayama rule for these characters, and we use Robinson-Schensted-Knuth insertion to derive a Roichman rule for these characters. We also define a class of standard elements on which it is sufficient to compute characters. The results forRn(q) specialize whenq=1 to analogous results forRn.

Keywords: rook monoid, character, Hecke algebra, symmetric functions

0. Introduction

The rook monoidRnis the monoid ofn×nmatrices with entries from{0, 1}and at most one nonzero entry in each row and column (these correspond with the possible placements of nonattacking rooks on ann×nchessboard). It contains an isomorphic copy of the symmetric groupSn as the rankn (permutation) matrices. Theq-rook monoidRn(q) is an “Iwahori- Hecke algebra” ofRn. It is a semisimpleC(q)-algebra so that whenq →1,Rn(q) specializes to the complex monoid algebraC[Rn]. Recently, the representation theory of Rn(q) was analyzed. Solomon [20] found a faithful action of Rn(q) on tensor space. Halverson [10]

showed that Rn(q) and the quantum general linear group are in Schur-Weyl duality and found explicit combinatorial constructions for the irreducibleRn(q)-representations.

In this paper we study the combinatorics ofRn(q)-characters. First, we use Schur-Weyl duality to prove the following identity in the ring of symmetric functions

qµ(1,x1, . . . ,xr;q)= n k=0

λk

χλRn(q)(Tµ)sλ(x1, . . . ,xr). (0.1)

Supported in part by National Science Foundation grant DMS-9800851.

Supported in part by National Science Foundation grant DMS-9800851 and by the Institute for Advanced Study under National Science Foundation grant DMS-9729992.

(2)

Hereqµis aq-analog of the power sum symmetric function pµ,sλis the Schur function, andχλRn(q)(Tµ) is the irreducible character ofRn(q) indexed byλand evalauated at a certain elementTµ. This is a generalization of the Frobenius formula of Ram [15] for the Iwahori- Hecke algebra Hn(q) of the symmetric group Sn, which in turn is a generalization of Frobenius’ [5] original formula from 1900,

pµ(x1, . . . ,xr)=

λn

χSλn(µ)sλ(x1, . . . ,xr). (0.2)

HereχSλn(µ) is the irreducible character ofSnindexed byλand evaluated on the conjugacy class with cycle typeµ.

We use our Frobenius formula to derive two combinatorial methods for computing χRλn(q)(Tµ):

(1) We give a recursive rule for computingχRλn(q)(Tµ) by removing broken border strips fromλ. This rule is an analog of the Murnaghan-Nakayama rule for Sn characters, which was generalized toHn(q)-characters in [15].

(2) We give a rule for computing χRλn(q)(Tµ) as weighted sums of standard tableaux.

This rule is a generalization of Roichman’s rule [17] for the irreducible characters of Hn(q).

We use our Frobenius formula to show that the character table ofRn(q), denotedRn(q), is of the form

Rn(q) = Rn−1(q)

0 Hn(q)

, (0.3)

whereRn−1(q)is the character table ofRn1(q) andHn(q)is the character table ofHn(q).

The elements in∗are explicitly determined by either our Murnaghan-Nakayama rule or our Roichman rule.

The characters of the rook monoid Rn(q = 1) were originally studied in the 1950s by Munn [14], who writes Rn characters in terms of Sk characters with 0 ≤ kn. As an example, Munn produces the character table of R4. In the Appendix we produce the character table of R4(q). Setting q = 1 in our table gives Munn’s table, exactly.

Munn also determines a “cycle-link” type for the elements of Rn, and he shows that Rn- characters are constant on cycle-link classes. In Section 5, we show that the irreducible Rn(q)-characters are completely determined by their values on the set of standard ele- ments Tµ, µ k,0 ≤ kn. Our elementTµ specializes atq = 1 to a rook element with “cycle-link” typeµ, and we show how to use “rook diagrams” determine cycle-link type.

Solomon [19] determined yet another way to compute Rn(q =1) characters. He writes the Rncharacter table as a product AY =YBwhereY is a block diagonal matrix whose

(3)

blocks are the characters of the symmetric groupsSk,0≤kn, andAandBare matrices that can be computed combinatorially.

Theq-rook monoid was first introduced by Solomon [18] as an analog of the Iwahori- Hecke algebra for the finite algebraic monoid Mn(Fq) of n ×n matrices over a finite field withq elements with respect to its “Borel subgroup” of invertible upper triangular matrices. In [20], Solomon gives a presentation of Rn(q) and defines a faithful action of Rn(q) on tensor space. In [8], Halverson and A. Ram show that Rn(q) is a quo- tient of the Iwahori-Hecke algebra of type Bn and prove that Rn(q) is semisimple over C whenever [n]! = 0, where [n]! = [n][n −1]· · ·[1] and [k] = qk1 +qk2 + · · · +1.

1. q-Rook monoid algebras

1.1. The rook monoid

LetSn denote the group of permutations of the set{1,2, . . . ,n}. IdentifyσSnwith the matrix having a 1 in the (i,j)-position ifσ(i)= j. For 1in−1, letsiSn be the transposition ofi andi+1.

Therook monoid Rn is the monoid ofn×nmatrices having entries from{0,1}withat mostone nonzero entry in each row and column. There are (nk)2k! matrices in Rn having rankk, and thus

|Rn| = n k=0

n k

2

k!. (1.1)

We haveSnRnas the ranknmatrices.

LetEi,j be then×nmatrix unit with a 1 in the (i,j)-position and 0s everywhere else.

In Rn, define

ν=E1,2+E2,3+ · · · +En−1,n,

πj =Ej+1,j+1+Ej+2,j+2+ · · · +En,n, 1≤ jn−1 (1.2)

εj =InEj,j, 1≤ jn,

whereInis the identity matrix. Letπnbe the zero matrix, and note thatπ1=ε1. Munn [14]

shows that the complex monoid algebra

C[Rn]=

xRn

αxx|αx∈C

is semisimple. Note thatπn is the zero matrix but it is not the zero element inC[Rn] (the zero element inC[Rn] is the linear combination withαx=0 for allx).

(4)

1.2. The q-rook monoid

Letqbe an indeterminate. Forn≥2, define theq-rook monoid Rn(q) to be the associative C(q)-algebra with generators 1,T1, . . . ,Tn1,P1, . . . ,Pnand defining relations

(A1) Ti2=q·1+(q−1)Ti, for 1≤in−1, (A2) TiTi+1Ti =Ti+1TiTi+1, for 1≤in−2, (A3) TiTj =TjTi, when|i− j| ≥2, (A4) TiPj =PjTi =qPj, for 1≤i < jn, (A5) TiPj =PjTi, for 1≤ j <in−1, (A6) Pi2=Pi, for 1≤in,

(A7) Pi+1=qPiTi1Pi, for 2≤in.

(1.3)

DefineR0(q)=C(q) and defineR1(q) to be the associativeC(q)-algebra spanned by 1 and P1subject toP12 = P1. The subalgebra ofRn(q) generated byT1, . . . ,Tn1is isomorphic to the Iwahori-Hecke algebra of typeHn(q) of typeAn1(see [20] or [10] for a proof that they can be identified).

Solomon definedRn(q) in [18] and gave it a presentation in [20]. The presentation (1.3) is proved in [10]. Solomon [18, 20] shows thatRn(q) is semisimple with dimension

dim(Rn(q))= n k=0

n k

2

k!. (1.4)

Whenq→1,Rn(q) specializes toC[Rn]. Under this specialization, we haveTisi and Piπi.

1.3. Partitions and tableaux

We use the notation of [12] for partitions and compositions. A compositionλof the positive integer n, denoted λ |= n, is a sequence of nonnegative integers λ = (λ1, λ2, . . . , λt) such that|λ| = λ1+ · · · +λt = n. The compositionλis a partition, denotedλ n, if λ1λ2≥ · · · ≥λt. The length(λ) is the number of nonzero parts ofλ. The Young diagram of a partitionλis the left-justified array of boxes withλiboxes in theith row. We letmi(λ) be the number of parts ofλequal toi, and we sometimes writeλ=(1m1(λ),2m2(λ), . . .). For example,

ifλ=(5,5,3,1)=(1,3,52)= , then|λ| =14 and(λ)=4.

Ifλis a partition with 0≤ |λ| ≤n, then we say that ann-standard tableau of shapeλis a filling of the diagram ofλwith numbers from{1,2, . . . ,n}such that

(5)

(1) each number from{1,2, . . . ,n}appears inλat most once, (2) the rows ofλincrease from left to right, and

(3) the columns ofλincrease from top to bottom.

Similarly, ann-column strict tableaux of shapeλis the same as ann-standard tableau except that we allow the rows to weakly increase. Thus,

2 3 9 10 5 7 12 15 6 11 13

is a 16-standard tableau of shape (4, 4, 3)

1 1 3 4 3 3 8 8 8 8 9

is a 16-column strict tableau of shape (4, 4, 3).

1.4. Irreducible representations

The irreducible representations ofRn(q) andC[Rn] are indexed by partitions in the set

n = {λk|0≤kn}. (1.5)

Forλn, we letMλbe the irreducibleC[Rn]-module indexed byλand let χRλn be its character, and we let Mqλ be the irreducible C[Rn]-module indexed by λ and let χRλn(q)be its character. The dimensions ofMλandMqλare given by

dim(Mλ)=dim Mqλ

=#(n-standard tableaux of shapeλ)= n

|λ|

fλ, (1.6)

where fλis the number of|λ|-standard tableaux of shapeλgiven by the hook formula (see [21], Theorem 3.10.2).

The Rn-moduleMλis studied in [6, 14, 19]. In [6], C. Grood determines the analog of Young’s natural basis forMλ. In [10], analogs of Young’s seminormal bases of bothMqλ andMλare constructed, and the action of the generators ofRn(q) andRnon this basis are described explicitly.

1.5. Standard elements Defineγ1 =Tγ1=1 and γt =s1s2· · ·st1,

for 2≤tn. (1.7)

Tγt =T1T2· · ·Tt1,

(6)

For a compositionµ=(µ1, µ2, . . . , µ) with|µ| =kand 0≤kn, define γµ =γµ1γµ2⊗ · · · ⊗γµ,

Tγµ =Tγµ1Tγµ2⊗ · · · ⊗Tγµ, (1.8) and

dµ =πn−kγµ,

Tµ =PnkTγµ, (1.9)

where we viewTµ=PkTγµ1⊗ · · · ⊗TγµRk(q)⊗Rµ1(q)⊗ · · · ⊗Rµ(q)⊆Rn(q).

For example, ifn =15 andµ=(5,3,2,2), then Tµ=P3(T4T5T6T7)(T9T10)(T12)(T14).

In [15] it is shown that Hn(q)-characters are completely determined by their value on Tγµ. In Section 5 we show that characters of Rn(q) andC[Rn] are completely determined by their values on Tµ anddµ. Since both the irreducible representations and the standard elements are indexed byn, we see that the character table is square with these labels.

Whenq→1, we haveRn(q)→C[Rn] withTµdµ. Furthermore, in [10], we construct Mqλso that M1λ = Mλ, and the action of Tµ specializes at q = 1 to the action ofdµ. It follows that the characters also specialize upon settingq=1,

χλRn(q)(Tµ)|q=1=χλRn(dµ). (1.10)

2. A Frobenius formula for theq-rook monoid

In this section, we use the Schur-Weyl duality between Rn(q) and the quantum general linear groupUqgl(r) to derive a Frobenius formula for the irreducible characters ofRn(q).

We defineUqgl(r) as in Jimbo [11], except with his parameterq replaced byq1/2. Let Uqgl(r) be theC(q1/4)-algebra given by generators

ei, fi(1≤i <r) and q±εi/2(1≤in), with relations

qεi/2qεj/2=qεj/2qεi/2, qεi/2q−εi/2 =q−εi/2qεi/2=1, qεi/2ejq−εi/2=





q12ej, if j =i−1, q12ej, if j =i, ej, otherwise,

qεi/2fjq−εi/2=





q12fj, if j=i−1, q12 fj, if j=i,

fj, otherwise, eifjfjei =δi j

q12i−εi+1)q12i−εi+1) q12q12 ,

(7)

ei±1ei2

q12 +q12

eiei±1ei+e2iei±1=0, fi±1fi2

q12 +q12

fifi±1fi+ fi2fi±1=0, eiej =ejei, fifj = fjfi, if|i− j|>1. Define

ti =qεi4 (1≤ir) ki =titi−1+1 (1≤ir−1).

There is a Hopf algebra structure (see [11], p. 248) onUqgl(r) with comultiplicationand counitugiven by

(ei)=eiki−1+kiei, u(ei)=0,

(fi)= fiki1+kifi, u(fi)=0, (2.1) (ti)=titi, u(ti)=1.

2.1. Representations and characters of Uqgl(r)

Lethbe a Cartan subalgebra of the Lie algebragl(r), and letε1, . . . , εr be an orthonormal basis forhwith respect to an inner product ( , ). The weight lattice isL =r

i=1i, and the dominant integral weights are of the form

λ=m1ε1+ · · · +mrεr, mi ∈Z, m1m2≥ · · · ≥mr.

We identify the dominant weightλwith the sequence (λ1, . . . , λr), and we letVq(λ) denote the irreducibleUqgl(r)-module with dominant weightλ(see [2], Section 10.1, for example).

Any finite dimensionalUqgl(r)-moduleV has a basis B consisting of weight vectors, where, for eachbB, there exists wt(b)Lsuch that

tib=q14(εi,wt(b))b, 1≤ir.

Letx1, . . . ,xr be indeterminates, and define the character ofV to be ch(V)=

b∈B

xwt(b), (2.2)

where if wt(b)=a1ε1 + · · · + arεr, then xwt(b) =xa11· · ·xrar. It is known (see [2], Proposition 10.1.5) that ch(Vq(λ)) is the same as the corresponding character ofgl(r), and so it is given by the Weyl denominator formula. Thus, whenλis a partition, the character ofVq(λ) is given by the Schur function,

ch(Vq(λ))=sλ(x1, . . . ,xr)=det

xiλj+rj det

xirj . (2.3)

(8)

2.2. The bitrace

IfVis a finite-dimensionalUqgl(r)-module andZ =EndUqgl(r)(V) is its centralizer algebra, then define, for eachφZ,

btr(φ)=

bB

xwt(b)(φb|b), (2.4)

where B is a weight basis of V (a basis consisting of weight vectors) and φb|b is the coefficient ofbinφb. ForµL, letVµdenote theµ-weight space ofV. Then, sinceZ commutes withUqgl(r), we know thatZpreserves weight spaces, and so by summing over weight spaces we get

btr(φ)=

µ∈L

dim(Vµ)xµtrVµ(φ).

wheretrVµ(φ) is the trace ofφonVµ. In particularbtr(φ) is a weighted sum of usual traces, and it satisfies the trace property,btr(φ1φ2)=btr(φ2φ1) for allφ1, φ2Z.

Now, by double centralizer theory (see for example [3], Section 3D), we have a decom- position of the form

V ∼=

λ

Vq(λ)⊗Zλ

whereZλis an irreducibleZ-module and the sum is over the highest weightsλfor which Vq(λ) is a constituent ofV. For each moduleVq(λ)⊗Zλwe choose a basis{bλizλj}, where Bλ= {bi}is a weight basis ofVq(λ) and{zλj}is a basis ofZλ. The bitrace becomes

btr(φ)=

λ

bBλ

xwt(b)

j

φzλj|zλj =

λ

ch(Vq(λ))χZλ(φ). (2.5)

Hereφzλj|zλj is the coefficient ofzλj inφzλj, andχZλ(φ)=

jφzλj|zλj is the character ofZλ evaluated atφ. We thank Arun Ram for suggesting this derivation of (2.5).

2.3. Schur-Weyl duality

The “fundamental”r-dimensionalUqgl(r)-moduleV = Vq((1)) = Vq1) is the vector space

V =C(q1/4)-span{v1, . . . , vr}

(so that the symbols vi form a basis of V) with Uqgl(r)-action given by (see [11], Proposition 1)

eivj =

vj+1, if j=i,

0, if j =i, fivj =

vj1, if j =i+1, 0, if j =i+1,

(9)

and

tivj =

q1/4vj, if j =i, vj, if j =i.

The “trivial” 1-dimensionalUqgl(r)-moduleW =Vq(∅) is the vector space W =C(q1/4)-span{v0}

(so that the symbolv0is a basis ofW) withUqgl(r)-action given by the counitu eiv0= fiv0 =0 and tiv0 =v0.

LetU =VWso thatUhas basisv0, v1, . . . , vr. The coproduct onUqgl(r) is coasso- ciative, so we can form then-fold tensor product representationUn. The simple tensors vi1⊗ · · · ⊗vinform a basis forUn,i.e.,

Un=C(q)-span

vi1⊗ · · · ⊗vin0≤ijn .

Define an action ofRn(q) onUnas follows. The action of a generatorTk,1≤kn−1, andPj,1≤ jn, on a simple tensorv=vi1⊗ · · · ⊗vin inUnis given by

Tkv=





qv, ifik=ik+1, (q−1)v+q1/2skv, ifik<ik+1, q1/2skv, ifik>ik+1.

(2.6) Pjv=

v, ifi1=i2= · · · =ij =0, 0, otherwise.

whereskacts onvby place permutation, sk

vi1⊗ · · · ⊗vikvik+1⊗ · · · ⊗vin

=vi1⊗ · · · ⊗vik+1vik⊗ · · · ⊗vin.

Solomon [20] first proved that (2.6) extends to an action ofRn(q) on tensor space, although he used a different generatorN in place of thePi, and he proved that the action is faithful whenrn.

Halverson [10] proved that Rn(q) commutes withUqgl(r) on Un, and so ifrn, we have Rn(q) ∼= EndUqgl(r)(Un). Furthermore, [10] shows that Un decomposes into irreducibles as

Un∼= n

k=0

λk

Vq(λ)⊗Mqλ (2.7)

as a bimodule forUqgl(r)⊗Rn(q). Here,Vq(λ) is the irreducibleUqgl(r)-module of highest weightλ, andMqλis the irreducibleRn(q)-module corresponding toλ.

(10)

2.4. A Frobenius formula

Putting together (2.3), (2.5) and (2.7), proves Proposition 2.1 For all hRn(q),we have

btr(h)= n k=0

·

λk

sλ(x1, . . . ,xrRλn(q)(h),

whereχλRn(q)is the irreducible Rn(q)character labeled byλ.

Letn=n1+n2,d1Rn1(q), andd2Rn2(q). Then the bitrace ofd1d2Rn(q) on U⊗nsatisfiesbtr(d1d2)=btr(d1)btr(d2), wherebtr(di) is the bitrace ofdi onU⊗ni (the proof is identitical to that in [7] Section 5, sinced1acts on the firstn1tensor slots andd2acts on the lastn2tensor slots). Thus ifµ=(µ1, . . . , µ) is a composition with 0≤ |µ| ≤n, andTµis defined as in (1.9), then

btr(Tµ)=btr(Pnk)btr Tµ1

· · ·btr Tµ

. (2.8)

As in [15], letq0(x0,x1, . . . ,xr;q)=1, and for a positive integerkdefine qk(x0,x1, . . . ,xr;q)=

I=(i1,...,ik)

qe(I)(q−1)(I)xi1· · ·xik, (2.9) where the sum is over all weakly increasing sequencesI =(0≤i1≤ · · · ≤ikr),e(I) is the number ofijI such thatij =ij+1, and(I) is the number ofijI such that ij<ij+1. For a compositionµ=(µ1, µ2, . . . , µ), define

qµ=qµ1qµ2· · ·qµ. (2.10)

Proposition 2.2

(a) The bitrace of Tγk on Ukis btr(Tγk)=qk(x0,x1, . . . ,xr;q).

(b) The bitrace of Pkon Ukis btr(Pk)=1.

(c) For a compositionµwith0≤ |µ| ≤n,the bitrace of Tµon Un is btr(Tµ)=qµ(x0, . . . ,xr;q).

Proof: Recall from Section 2.3, thattiv0 = v0, and for 1 ≤ jr,tjvj = q14vj and tivj =vjifi = j. Letx0=1. Then

xwt(v0)=1=x0 and xwt(vj)=xεj =xj, 1≤ jr, so the simple tensorsvi1⊗ · · · ⊗vinform a weight basis ofUnsatisfying

xwt(vi1⊗···⊗vin)=xi1· · ·xin.

(11)

Now, the proof of (a) is exactly as the proof of [15], Theorem 4.1. For (b), we have Pk(vi1· · ·vik) = 0 unless i1 = · · · = in = 0, and Pk(v0· · ·v0) = v0· · ·v0. Part (c) follows from (a), (b), and (2.8).

Combining Propositions 2.1 and 2.2(c), we have the following Frobenius formula for Rn(q).

Theorem 2.3 Letµbe a composition with0≤ |µ| ≤n. Then qµ(1,x1, . . . ,xr;q)=

n k=0

λk

χλRn(q)(Tµ)sλ(x1, . . . ,xr)

where Tµis defined in(1.9)andχRλn(q)is the irreducible Rn(q)-character labeled byλ.

We saw in (1.10) that upon settingq =1 we haveχRλn(q)(Tµ)|q=1=χRλn(dµ). Furthermore, it is easy to see thatqµ(x0,x1, . . . ,xr; 1)= pµ(x0,x1, . . . ,xr), since whenq =1 in (2.9) we must havei1=i2= · · · =ik. Thus, settingq =1 in Theorem 2.3, gives

Theorem 2.4 Letµbe a composition with0≤ |µ| ≤n. Then pµ(1,x1, . . . ,xr)=

n k=0

λk

χRλn(dµ)sλ(x1, . . . ,xr),

where dµis defined in(1.9)andχλRnis the irreducible Rn-character indexed byλ.

The next corollary (of Theorem 2.3) tells us that the character table ofRn(q) has the form shown in (0.3).

Corollary 2.5 Letλnand letµbe a composition with0≤ |µ| ≤n,then (a) if|λ|>|µ|,thenχRλn(q)(Tµ)=0.

(b) if|λ| ≤ |µ|,thenχRλn(q)(Tµ)=χRλ|µ|(q)(Tγµ).

Proof: From Theorem 2.3, we see that n

k=0

λk

χRλn(q)(Tµ)sλ(x1, . . . ,xr)=|µ|

k=0

λk

χRλ|µ|(q) Tγµ

sλ(x1, . . . ,xr),

since each side of this equation equalsqµ(x0,x1, . . . ,xr;q). This is an identity in the ring of symmetric functions, and the Schur functions are linearly independent, so the corollary follows from equating the coefficient ofsλon both sides. In particular, when|λ|>|µ|the coefficient ofsλon the right side is 0, proving part (a).

(12)

3. Murnaghan-Nakayama rules

Ifλandµare partitions, we say thatµλifµiλi for eachi. The skew shapeλ/ν consists of the boxes that are inλand not inµ. Two boxes inλ/µare adjacent if they share a common edge, andλ/νis connected if you can travel from any box to any other via a path of adjacent boxes. A skew shapeλ/νis abroken border strip(bbs) if it does not contain any 2×2 blocks of boxes, and a broken border strip is aborder stripif it is a single connected component. Each broken border stripλ/νcontainscc(λ/ν) connected components (border strips).

The width and height of a border stripbare defined, respectively, by w(b)=(the number of columns thatboccupies)−1,

(3.1) h(b)=(the number of rows thatboccupies)−1.

For a skew shapeλ/ν, we define wtλ/ν(q)=

(q−1)cc(λ/ν)−1

b

qw(b)(−1)h(b), ifλ/ν is a bbs,

0, otherwise;

(3.2)

where the product is over the connected components (border strips)binλ/ν. For example

(7,5,5,3,2)/(4,4,3,1)=

is a broken border strip consisting of two connected componentsb1andb2withw(b1)= 2,h(b1) = 1 andw(b2) = 3,h(b2) = 2. Thus its weight is (q −1)q2(−1)q3(−1)2 =

−(q−1)q5.

A key step in proving the Murnaghan-Nakayama rule for Hn(q) is the following propo- sition [15] (see also [7]), which is aq-analog of [12], Section 3, Example 11(2),

Proposition 3.1(Ram [15]) Ifν(n−k),then qk(x1, . . . ,xr;q)sν(x1, . . . ,xr)=

λn

wtλ/ν(q)sλ(x1, . . . ,xr),

where qkis defined in(2.9),sν is the Schur function,and the sum is over all partitionsλ such thatλ/νis a broken border strip of size k.

To extend this result to our setting, we first expandqt(1,x1,x2, . . . ,xr;q) in terms of qk(x1,x2, . . . ,xr;q).

(13)

Lemma 3.2 For t≥0,we have qt(1,x1, . . . ,xr;q)=

t k=0

fk,t(q)qk(x1, . . . ,xr;q),

where

fk,t(q)=





qt1, if k=0, (q−1)qtk1, if 0<k<t,

1, if k=t.

(3.3)

Proof: By definitionqt(1,x1, . . . ,xr;q)=

Iqe(I)(q−1)(I)xi1, . . . ,xik, where the sum is over all sequences I =(i1, . . . ,it) of the form 0 ≤i1i2 ≤ · · · ≤itr. We letK represent the subsequence ofIcontaining all the strictly positive terms inI, and letk= |K|.

Now we sum the terms inqt(1,x1, . . . ,xr;q) according tok. The terms with k = t contribute

K=(i1,...,it)

qe(K)(q−1)(K)xi1, . . . ,xit =qt(x1, . . . ,xr;q),

since 1≤i1i2≤ · · · ≤itr. The terms with 0<k<teach havetk−1 equalities between 0s and one jump from a 0 subscript to a nonzero subscript. Thus, they contribute

(q−1)

t1

k=1

qtk1

K=(it−k+1,...,it)

qe(K)(q−1)(K)xitk+1, . . . ,xit

=(q−1)

t−1

k=1

qtk−1qk(x1, . . . ,xr;q).

Finally, there is one term withk=0. It has the form qt1x0, . . . ,x0=qt1q0(x1, . . . ,xr;q).

Summing these three cases gives the desired result.

Proposition 3.3 Ifνnt,then

qt(1,x1, . . . ,xr;q)sν(x1, . . . ,xr)=

λ∈n

f|λ/ν|,t(q)wtλ/ν(q)sλ(x1, . . . ,xr),

where the nonzero terms in this sum are over the partitionsλnsuch thatλ/νis a broken border strip with0≤ |λ/ν| ≤t.

(14)

Proof: By Proposition 3.1 and Lemma 3.2, ifνnt, we have qt(1,x1, . . . ,xr;q)sν(x1, . . . ,xr)=

t k=0

fk,t(q)qk(x1, . . . ,xr;q)sν(x1, . . . ,xr)

= n

k=0

fk,t(q)

λ(|ν|+k)

wtλ/ν(q)sλ(x1, . . . ,xr).

We now are ready to derive a Murnaghan-Nakayama rule for computing the irreducible characters ofRn(q).

Theorem 3.4 Letλnand letµ=(µ1, . . . , µ)be a composition with0≤ |µ| ≤n.

Letµ=t andµ¯ =(µ1, . . . , µ1). Then χλRn(q)(Tµ)=

ν∈nt

f|λ/ν|,t(q)wtλ/ν(q)χνRnt(q)(Tµ¯),

where wtλ/ν(q)is defined in (3.2) and fk,t(q)is defined in (3.3). The nonzero terms in this sum correspond to partitionsνn−t such that λ/ν is a broken border strip with 0≤ |λ/µ| ≤t.

Proof: From Theorem 2.3 and Proposition 3.3, we have

λ∈n

χλRn(q)(Tµ)sλ(x1, . . . ,xr)

=qµ(1,x1, . . . ,xr;q)

=qµ¯(1,x1, . . . ,xr;q)qt(1,x1, . . . ,xr;q)

=

ν∈n−t

χRνnt(q)(Tµ¯)sν(x1, . . . ,xr)qt(1,x1, . . . ,xr;q)

=

ν∈n−t

χRνn−t(q)(Tµ¯)

λ∈n

f|λ/ν|,t(q)wtλ/ν(q)sλ(x1, . . . ,xr)

=

λ∈n

ν∈nt

χνRn−t(q)(Tµ¯)f|λ/ν|,t(q)wtλ/ν(q)

sλ(x1, . . . ,xr).

Now compare coefficients of the sλ, which are a basis in the ring of symmetric fun- ctions.

Whenq=1, definitions (3.3) and (3.2) become fk,t(1)=

1, ifk=0 ork=t,

0, otherwise, (3.4)

(15)

wtλ/ν(1)=

(−1)h(λ/ν), ifλ/νis a border strip,

0, otherwise. (3.5)

It follows that the Murnaghan-Nakayama rule for the rook monoid is

Theorem 3.5 Letλnand letµ=(µ1, . . . , µ)be a composition with0≤ |µ| ≤n.

Letµ=t andµ¯ =(µ1, . . . , µ−1). Then χλRn(dµ)=

ν∈n−t

(−1)h(λ/ν)χνRn−t(dµ¯),

where the sum is over partitionsνn−tsuch that eitherν=λorλ/νis a border strip of size t.

4. Robinson-Schensted-Knuth insertion and Roichman weights

Fixrn. For a partitionµ=(µ1, . . . , µ)∈ndefineB(µ) to be the set of partial sums ofµso that

B(µ)= {µ1, µ1+µ2, . . . , µ1+ · · · +µ}. (4.1)

Forµk, define theµ-weight ofxi1, . . . ,xik, with 0≤ijr, to be wtµ

xi1, . . . ,xik

= k

j=1 j∈B(µ)/

φµ

j,xi1, . . . ,xin

, (4.2)

where

φµ

j,xi1, . . . ,xik

=





−1 ifij <ij+1,

0, ifijij+1andij+1<ij+2andij+1/ B(µ), q, otherwise.

Proposition 4.1([16]) We have q=1,and forµk with1≤kn,we have qµ(x0,x1, . . . ,xr;q)=

xi1,...,xik

wtµ

xi1, . . . ,xik

xi1, . . . ,xik,

where the sum is over all words xi1, . . . ,xik with0≤ijr .

Letλnand recall our definition, in Section 1.3, of ann-standard tableauQλof shape λ. In this section we will place the numbers that are missing fromQλin a standard tableau

参照

関連したドキュメント

In section 3 all mathematical notations are stated and global in time existence results are established in the two following cases: the confined case with sharp-diffuse

Since the boundary integral equation is Fredholm, the solvability theorem follows from the uniqueness theorem, which is ensured for the Neumann problem in the case of the

“Breuil-M´ezard conjecture and modularity lifting for potentially semistable deformations after

Then it follows immediately from a suitable version of “Hensel’s Lemma” [cf., e.g., the argument of [4], Lemma 2.1] that S may be obtained, as the notation suggests, as the m A

standard Young tableau (SYT) : Obtained by filling in the boxes of the Young diagram with distinct entries 1 to n such that the entries in each row and each column are increasing.. f

This paper gives a decomposition of the characteristic polynomial of the adjacency matrix of the tree T (d, k, r) , obtained by attaching copies of B(d, k) to the vertices of

[Mag3] , Painlev´ e-type differential equations for the recurrence coefficients of semi- classical orthogonal polynomials, J. Zaslavsky , Asymptotic expansions of ratios of

Recently, Zhou and Fan in [8] proved a regularity criterion for another system of partial differential equations modelling nematic liquid crystal flows, which is considered by Sun