Головна
Journal of Combinatorial Theory, Series A A schenstedtype correspondence for the symplectic group
A schenstedtype correspondence for the symplectic group
Allan BereleНаскільки Вам сподобалась ця книга?
Яка якість завантаженого файлу?
Скачайте книгу, щоб оцінити її якість
Яка якість скачаних файлів?
Том:
43
Рік:
1986
Мова:
english
Сторінки:
9
DOI:
10.1016/00973165(86)900701
Файл:
PDF, 363 KB
Ваші теги:
 Будьласка, спочатку увійдіть в свій аккаунт

Необхідна допомога? Будьласка, ознайомтесь з інструкцією як надіслати книгу на Kindle
Напротязі 15 хвилин файл буде доставлено на ваш email.
Напротязі 15 хвилин файл буде доставлено на ваш kindle.
Примітка: Вам необхідно верифікувати кожну книгу, яку Ви відпрвляєте на Kindle. Перевірте поштову скриньку на наявність листа з підтвердженням від Amazon Kindle Support.
Примітка: Вам необхідно верифікувати кожну книгу, яку Ви відпрвляєте на Kindle. Перевірте поштову скриньку на наявність листа з підтвердженням від Amazon Kindle Support.
Пов’язані Буклисти
0 comments
Ви можете залишити відгук про книгу и поділитись своїм досвідом. Іншим читачам буде цікаво дізнатись вашу думку про прочитані книги. Незалежно чи вам сподобалась книга чи ні, якщо ви відверто і детально розповісте про це, люди зможуть знайти для себя нові книги, які їх зацікавлять.
1


2


JOURNAL OF COMBINATORIAL THEORY, Series A 43, 32C328 (1986) A SchenstedType Correspondence for the Symplectic Group ALLAN BERELE* Department of Mathematics. University Philadelphia, Pennsylvania Communicated of Pennsylvania, 19/04 by the Managing Editors Received February 15, 1985 The Schensted correspondence is closely related to the decomposition of V”” as a GL( V)module. In this paper we obtain an analogous correspondence related to the (cl 1986 Academic Press. Inc. decomposition of V@” as an Sp( V)module. It is well known that there is a onetoone correspondence between the set of words of length n in the alphabet { 1, 2,..., k) and the set of pairs (Pi, Q) where P and Q are tableaux of shape I, [A( = n, P, is a semistandard tableau (entries strictly increasing in columns, weakly increasing in rows) in {l,..., k} and Qj, is a standard tableau (row and column strict) in { I>...>n}. There are two ways to prove this. The Schensted correspondence (see [3]) gives an explicit construction of pairs of tableaux from words. We will assume that the reader is familiar with this construction. Alternately, there is an algebraic proof. One considers VBn, where V is a vector space of dimension k. Clearly, V@* has dimension k”. Then one shows that, as a GL(k)module, V@‘” decomposes into a direct sum of irreducible modules Nn; that the number of semistandard tableaux on 2 is the dimension of N,; and that the number of standard tableau on /1 is the multiplicity of N, in Van. The result clearly follows. 1. @(T/)MODULES The following information is taken from [2]: Let V be a 2kdimensional vector space with a nondegenerate alternating bilinear form. Then V defines Sp( V) or Sp,,, the invertible linear transformations which preserve this form. The irreducible, finitedimensional * Present address: Department of Mathematical Illinois 60614. 320 OO973165/86 $3.00 Copyright All rights r6 1986 by of reproduction Academic m any Press, form Inc. reserved. Sciences, De Paul University, Chicago, SCH; ENSTED CORRESPONDENCEFOR s&J 321 representations of Spzk are parameterized by partitions, 1, with k or fewer parts and will be denoted (A). The dimension of (A) equals the number of tableaux of shape A and entries from the ordered alphabet {id<2<k ... <k <E} and subject to (S.l) (S.2) (S.3) The entries increase weakly in the rows; The entries increase strictly in the columns; No entry < i occurs in row i, for any i We will call such a tableau Spstandard. The number of Spstandard tableau of shape 1 will be denoted d,. There is also a tensor product rule for these characters [ 11: The multiplication and division on the righthand side of the equation are the ordinary multiplication and division of partitions given by the LittlewoodPRichardson rule. We point out that a symbol (v), htv > k, may occur in such a product and that “modification rules” for interpreting such a symbol are described in [ 11. One such is if v has height k + 1 then (v) = 0. Now in the case of p = (1 ), formula (1.1) becomes (n>o(l)=(n.l>+(;L/l). (1.2) This means that (A) 0 (1) is the sum of all diagrams of height <k which can be constructed from A by either adding on or removing one box. It is now simple to show by induction. LEMMA 1. The multiplicity of (2 ) in ( 1) @* is the number of sequences of Young diagrams (DO, D, ,..., D,), where (1) D, is the empty diagram and D, is A. (2) Each Di is gotten from Dip, either by adding on one box or removing one box. (3) Each Di has height <k. We denote the number of such sequences by m, or mj,(n). EXAMPLE. The reader may verify that if k = 2, n = 5, and ;1= (2, 1 ), then m, = 16 and d, = 16. The sequences and tableaux include these in Fig. 1. 322 ALLAN FIG. THEOREM ProoJ: Taking 1. Some sequences BERELE and tableaux for k = 2, n = 5, 1= (2.1), 1. (2k)” = ‘& m, d,. By Lemma 1, (l)@“=x m),(A). dimensions now gives the result. 2. THE BIJECTION In this section we reprove Theorem 1 with a bijective proof. The bijection we construct is a modification of the usual Schensted correspondence. At each step the insertion algorithm will either add a number in the usual way or will take a box away. The process of removing a box is accomplished by a step in which an i annihilates an iand the empty box is then moved to a corner by a sort ofjeu de tacquin. We will need the following definitions: DEFINITION. A punctured tableau of shape 2 is a Young diagram of shape 2 in which every box except one is filled. We will refer to it as the empty box. If the empty box is a corner box we sometimes will identify the punctured tableau with an ordinary tableau on a smaller partition. A punctured tableau is said to be Spstandard if it satisfies (S.1 ), (S.2) and (S.3). We now describe the steps which are used in our jeu de tacquin and its inverse. DEFINITION. Let T be a punctured tableau with (a, /?) entry tcr8 and with empty box in position (i, j). Then T R(T)== if (i, j) is the right most box in row i the punctured tableau gotten from T by switching the empty box and tij+ i, if not; SCHENSTED L(T)= ! 323 sp the punctured tableau gotten from T by switching the empty box and t,, _ , , if not; D(T)== U(T)= FOR if j=l T if T and CORRESPONDENCE (i, j) is the bottom box in column j the punctured tableau gotten from T by switching the empty box and 1,+ ,,j, if not; ( if T i=l the punctured tableau gotten from T by switching I the empty box and t, ,.J, if not. See Fig. 2. LEMMA 2. Let T be an Spstandard punctured telr and empty box in position (i, j). Then Either R(T) or D(T) Spstandard. (a) is Spstandard. And if R(T) = T then D( T) is (b) Either L(T) or U(T) is Spstandard. is Spstandard or tie ,,, < i. Proof: tableau with (c(, fl) entrv And if,j= 1, then either U(T) Refer to Fig. 3. (a) If R(T) = T then, by definition of R, the empty box in position (i, j) is switched with the (i, j + 1) entry, tl,i+, Since T was Spstandard R(T) must satisfy (S.2) and (S.3), since the entries of the rows and their orders remain unchanged. Moreover, by (S.2), t,,j+, > tj ,.i+, and by (S.l) T: ’ ’ w2 2 2 2 R(Tlr [m L(T): m D(T)= m U(T)= w FIG. 2. Examples of R, L, D, and U. 324 ALLAN BERELE A A +i,j+l A +i,j1 A Sii+j,jS FIG. 3. Proof of Lemma 2. and so tij+, > tj ,,i. Hence, the only way a violation of 12 tilj could occur in R(T) would be if ti,,+ I (the (i,j) entry of R(T)!) was less than or equal to li+ I,j. A parallel argument holds for D(T). D(T) must satisfy (S.1) and (S.3), and a consideration of the inequalities tj+ ,,j, > ,+ r,, , > t,,jl shows that the only way a violation of (S.2) could occur in D(T) would be if t,,, + 1 was greater than ti+ ,,j (The (i, j) entry of D(T).) So if R( T) # T, either R(T) or D(T) must be @standard. Moreover, if R(T) = T, then T has no (i, j + 1) entry and so D(T) must be Qstandard. L;f+ t. (b) The proof in this case is similar. If L(T) is not Qstandard then tip < 1. If U(T) is not Spstandard, there are two possibilities: either > or 1 =c.~i. So t,,jP, <i and tip ,,j< t,,,_, . But this implies [i1,j that ti ,,i < i, which contradicts (S.3). I,j ti,j t,,, ti.jp DEFINITION. Let A = the set of Qstandard punctured tableaux T with empty box in the first column and such that either the empty box is in the first row or such that U(T) is not Qstandard. Let B = the set of Spstandard punctured tableaux with empty box in a corner. DEFINITION. If T is a punctured @standard tableau on A, (21 = n, let if R(T) is Spstandard and R(T) # T if not. If the empty box is not in the first column let B(T)= UT) W T) if L(T) is Spstandard if not SCHENSTED CORRESPONDENCE FOR @ 325 , then FIG. 4. Example of A and 8. and if the empty box is in the first column let if U(T) is Spstandard if not. Finally, let A(T) = A”(T) and B(T) = B”(T). See Fig. 4. LEMMA 3. A is a bijection from A to B with inverse B. Proof If suffices to show that if T is an Spstandard punctured tableau with empty box in the (i, j) position (1) (2) if A(T)# T, then m(T)= T; if B(T) # T, then AB( T) = T. If A(T) # T, then (i j) is not a corner box. If A(T) = R(T), then L(A( T)) = T and so is Spstandard. Hence B(A( T)) = L(A( T)) = T. If A(T) = D( T), then R(T) must not be Spstandard. So, as in the proof of Lemma 2, t,,, + , d ti+ ,,j. In A(T) the empty box is in position (i, j + 1) and t,.,+ I is in the (i, j) position. Now the entry in position (i  1, j + 1) is is not Spstandard and tie,,+, which is ~t,,~+,. Therefore L(A(T))  2 B(A( T)) = U(A( T)) = T. The proof of (2) is similar and we omit it. We now wish to combine A with a slight modification of the usual Schensted correspondence to give a bijection which realizes Theorem 1. The Schensted correspondence is built on an algorithm for adding a given letter to a given row of a tableau resulting in a new tableau and in either the information that the process has terminated or in a letter to be added to the next row. We modify this process in one case: If row i contains i’s and if the letter to be added is an i then, instead of adding the i to the row and bumping an i to the (i + 1)” row, we instead (1) replace the first iin the row with an i, 326 ALLAN BERELE 1 2 , then Ini (T,i)= In< and In; FIG. (2) CT,1 ): (T,2)= 5. Example of Ins’. then replace the first entry in the ith row, which is necessarily an i, with an empty box. We denote by Ins’( T, a) the tableau or punctured tableau gotten from the Spstandard tableau T by inserting a by this algorithm. See Fig. 5. LEMMA 4. For any Spstandard tableau T and any letter a, Ins’(T, an Spstandard tableau or Spstandard punctured tableau in A. a) is ProoJ: There are two things to verify: that (S.3) is not violated by the bumping processes and that (S.2) is not violated in the modified step, in which an i is replaced by an i. First, assume that (S.3) is violated and that row i is the first row with a violation. By the standardness of T, the entry <i must have come from being bumped from row i 1, in which it was replaced by a smaller entry. If this entry was an (i  1) bumping an (i  l), it would not have affected the ith row because of the modification of the insertion step; if the entry was less than (i  1) it would give an earlier violation of (S.3) and so contradict the minimality of i. Hence, there is no violation. Next we verify that if Ins’ changes an i in row i that this change will not violate (S.2). Let t,,p be the (01,p) entry in the original tableau T and let (i, j) be the position of the first i in row i. So tip ,,i = i or i 1 or i  1, and if tip l.j = i then it is the first i in row i 1. If we assume that an i is bumped from row i 1 to row i, then it will be the first i in the row which is bumped. So, in Ins’( T, a) if an i is sent to the ith row, then the (i  1, j) position will be filled by an entry less than i And so (S.2) is not violated. DEFINITIONS. Let T be an Spstandard tableau and a a letter. Then we define Ins( T, a) = Ins’( T, a) A(Ins’( T, a)) if Ins’( T, a) is a tableau if Ins’( T, a) is a punctured tableau. SCHENSTED CORRESPONDENCE FOR $I Next if w=z1z2...z, is a word in { 1, i ,..., k, E} P(w) D,)) defined by: (T, CD,,..., ifSP(z,...zEP, 327 will be a pair )=(T,(D,,...,D,,I) then SP(w) = (Ins( T, z,), (0, ,..., D,)), where D, is the Young tableau of Ins( T, z,). Of course, we initiate the algorithm by declaring SP of the empty word to be the pair (the null tableau, vacuous sequence). THEOREM 2. SP is a bijection from words z1 ... zn in { 1, i,..., k, k} and pairs ( T, (D, ,..., D,)) in which T is an Spstandard tableau of shape 1 and (0, ,..., D,) is as in Lemma 1. Proof We construct a “deletion” process which will give an inverse to Ins and, hence, to SP. If Di is gotten from Dip, by adding a box, we remove the entry from this box by the ordinary Schensted deletion algorithm and so recover zi. If Di is gotten from Dip 1 by removing a box we consider the punctured tableau gotten by adding an empty box in the appropriate position. We then apply the algorithm B to obtain a punctured tableau in which the empty box is in the first column and, say, in rowj. We fill this box with aj and change the last j in the row to a j (Note that changing this j to aj will not violate (S.2) because the entry below it is at least j+ 1, by (S.3)) Finally, we use the ordinary Schensted deletion algorithm, beginning by sending a j to row j  1. This will be possible since row j must begin with a j 1 or j  1. This completes the proof. See Fig. 6 for examples. 328 ALLAN BERELE ACKNOWLEDGMENTS Thanks are due to C. Greene for a useful discussion and to R. Proctor for introducing us to the work of R. C. King. REFERENCES R. E. BLACK, R. C. KING, AND B. G. WYBOURNE, Kronecker products for compactsemisimple Liegroups, J. Phys. A. 16 (1983), 15551589. R. C. KING AND N. G. I. ELSHARKAWAY, Standard Young tableaux and weight multiplicities of the classical Lie groups, J. Phys. A 16 (1983), 31533177. M. P. SCHUTZENBERGER, La correspondence de Robinson, in “Combinatoire et representation du group symetrique (Actes Table Ronde C.N.R.G. Strasbourg 1976),” Lecture Notes in Mathematics Vol. 579, pp. 59l 13, SpringerVerlag. Berlin/New York/Heidelberg, 1977. 1. G. 2. 3.