» 7 , 7 w ‘ ‘ «ENS lHIIIIHI’lllll‘I‘llllll'lllllllIll’llllllll’llllIIHIIIHI 31293 00904 5786 This is to certify that the dissertation entitled Lattice Path Proof of Some Jacobi-Trudi Type Formulae presented by Jose H. Giraldo has been accepted towards fulfillment of the requirements for Ph.D. degree in Mathematics Bowgém Major prdlessoU LUZ? M; MSU is an Affirmative Action/Equal Opportunity Institution 0-12771 LIIRARY Michigan State University PLACE IN RETURN BOX to remove this checkout from your record. TO AVOID FINES return on or before date due. ll DATE DUE DATE DUE DATE DUE IWST—ll ”__JL_|L_Jl ji— L} lfilH—l MSU Is An Affirmative Action/Equal Opportunity Institution cMma-pd LATTICE PATH PROOF OF SOME J ACOBI—TRUDI TYPE FORMULAE By José H. “Giraldo A DISSERTATION Submitted to Michigan State University in partial fulfillment of the requirements for the Degree of DOCTOR OF PHILOSOPHY Department of Mathematics 1993 ABSTRACT LATTICE PATH PROOF OF SOME JACOBI-TRUDI TYPE FORMULAE BY José H. Giraldo Ira Gessel gave a combinatorial proof of the Jacobi-Trudi identities using lattice paths. We use this lattice path technique to prove some Jacobi-Trudi type identities. These identities relate determinants, where each entry is the sum or difference of certain complete homogeneous symmetric functions, to sums of certain skew Schur functions. Similar determinantal identities are obtained when the entries of the de— terminant are elementary symmetric functions. Contents Introduction 1 Preliminaries 1.1 Partitions and Tableaur 1.2 Symmetric Functions . 1.3 Lattice Paths ..... 2 Main Results 2.1 Jacobi- Trudi Identities 2.2 Some Jacobi-Trudi Type Identities .................... 2.3 Symplectic and Orthogonal Analogs ................... 3 Open Problem 3.1 Circulants ....... Bibliography OOOOOOOOOOOOOOOOOOOOOOOOOO iii 14 22 22 30 46 49 49 58 Introduction In the theory of group representations it is well-known that the irreducible poly- nomial representations of the general linear group GL(n) of all n by n non-singular complex matrices are indexed by partitions A of length at most n. The character of the irreducible representation indexed by A is the Schur function s,\ which belongs to the ring A of symmetric functions. A nice combinatorial proof of the fact that s; is symmetric was given by Knuth [Knu 70]. Even more, the 3), form a basis for the ring of symmetric functions. There are two other interesting bases for A, formed by the elementary and com- plete homogeneous symmetric functions, denoted by e; and h A, respectively. Formulae expressing s,\ as the determinant of certain elementary or complete homogeneous sym- metric function were found by Jacobi [Jac 41]. The proof of such formulae was later simplified by his student Trudi. These Jacobi-Trudi identities are stated as follows. Let A = (A1, A2, . . . , A") be a partition. Then 3A = I’m-ml and 8» = lend-HI where the determinants are n by n, and A’ is the conjugate of A. Ira Gessel [Ges um] gave a beautiful combinatorial proof of these results using lattice paths and tableaux. The same technique has been used by Gessel and Gerald 1 Viennot, [G-V 85,G-V ip], to prove other determinantal identities. Bressoud and Wei [B-W um] in an attempt to find a lattice path proof of the Jacobi-Trudi analogs for symplectic and orthogonal groups, discovered a way to ex- tend this method to prove the following result. For t Z —1 an integer 2(t-ltlll2 Z (_1)a (h,.__,+,(,, + (—1)(‘+"')/2hi,-.-_a(.)+1_t) n 063'; t l = Z (_1)[IuI+u..(ItI-u1/23W pgk “GP: where up is the length of the main diagonal of p and P; is the set of all p = (#1, . . . , pn) such that p.- = p:- + t, for 1 S i S V”. However their method lacked the elegance of the Gessel-Viennot proof. In the present work we give a lattice path proof of some more general determinantal identities which imply the Bressoud-Wei result. These identities are stated as follows. Theorem Let A = (A1, A2, . . . , An) be a partition. Fort Z —1, a fixed integer, lhAt-Hj + hA.—£—j+1—¢| = Z(_1)(Iul-(t+1)uu)/23Vu MEX ”6"} and “MM“. _ hA.-i—j+i—t| = Z (_1)(l#l-(t—1)Vu)/23A/u 549* FEP¢ In particular fort = —1 we have Ll Illa-m + hA.-i-j+2| = 2 Z (-1) t; 3w [€1ch I’M-m - hA.-i-j+2| = 0- Similar formulae are obtained for elementary symmetric functions. Theorem Let A :: (A1,A2, . . . , A") be a partition. Fort Z —1, a fixed integer, let-4+,- + €A.—i-j+1—:| = Z (-1)(""—(t+1)"“)/ 23min ug" HEP: and ICA.—i+j _ €A,—i—j+1—t| = Z (—1)(I"|_(t—1)W)/2SA'/w #91 “5": In particular fort = —1 we have I l RIM-4+]. + eAi-i—j-i-Zl = 2 Z (—1).%_3AI/ul "25:, 6A.—i+j - 6.\.—i—j+2| = 0- Chapter 1 Preliminaries 1.1 Partitions and Tableaux A partition is any sequence (finite or infinite) (1.1.1) A=(A1,A2,...,Ak,...) of non-negative integers in decreasing order, A1 2 Ag 2 - -- 2 Ah 2 -- -, with only a finite number of non-zero terms. The partitions A, u are said to be equal if they have the same non-zero terms. The parts of A are the non-zero A.-’s in (1.1.1). The number of parts is the length of A, which is denoted by ((A). The weight of A, denoted by IAI, is the sum of the parts of A, (1.1.2) |A|=A1+A2+A3+---. If n = |A| we say that A is a partition of n. If the last non-zero entry of A is Ak, we will simply write A = (A1,A2,...,Ak). If A is a partition of n, an alternate way of writing it is 4 A=(1’"‘,2’"’,...,n"‘") where mk indicates the number of times the summand 1: appears in the partition. So 22;, m,- = l(A) and 22‘zlim; = n. For instance, A = (3,3,1,l,1) and A = (13,32) represent the same partition. The diagram of a partition A = (A1, Ag, . . . , A1,) is an array of k left-aligned rows. The i“ row consists of A.- dots (nodes) or boxes. The rows are numbered starting with the first row at the top and columns are numbered starting with the first column at the left. We use (i, j) to refer to a box located in the it" row and j’h column. We write (i,j) E A, if the box in that position is in the diagram of A. For example if A = (4,3,2,1), its diagram is given in Figure 1.1.1. In this case (2,3) 6 A but (3,3) ¢ A. — Fig. 1.1.1 The main diagonal of a diagram is the diagonal starting at the upper left corner of the diagram and moving southeast. The conjugate of the partition A is the partition A’ = (A’l, A’z, Ag, . . .) whose diagram is the transpose of the diagram for A. That is, the diagram obtained by reflecting the diagram of A through the main diagonal. As an illustration, if A = (4,3,2), then A’ = (3,3, 2, 1). The diagrams for A and A’ are given in Figure 1.1.2, where the main diagonal of A is indicated. A semi-standard A- tableau is a filling of the diagram for A with the elements from a totally ordered set (A, _<_) where the rows are weakly increasing from left to right Fig. 1.1.2 and the columns are strictly increasing from top to bottom. As an example, if A = (4, 3, 2, 1), Figure 1.1.3 shows a semi-standard A-tableau where A is the set of positive integers with the usual order. 258] .4:- O) [OD-«liked co Fig. 1.1.3 Unless stated specifically, we fill the tableaux with positive integers. The entry in box (i, j) of a semi-standard A-tableau T is denoted by T(i.j)° To To.» we assign a variable denoted by an , ,). The weight :rT of a semi-standard A-tableau T is defined by T _ (1.1.3) at — II 31.0.1). (Mlle) If A = (3,2,2) some A-tableaux are shown in Figure 1.1.4. These tableaux have weights: 2:71 = $1$1$1$2$3$3$3 = xi’xgarg, 1:72 = :rlxlxgzgx3x4z4 = xfmgxgxi, 2:73 = A3. 0 A 0 231322313343435 = xlzgxgxixs. The degree of a monomial 23‘: 13%,} - - 3,: is defined as 23:1 A,-. Then, the weight of a semi-standard A-tableau is a monomiaJ of degree IAI- The length of the main diagonal of the diagram for A is denoted by VA. When A is clear from the context we will simply write 11. Alternatively, we can interpret 11A, as: (1..14) V,\ = l(AglA.‘ __>_ 2“. Observe that the diagram for A is completely determined by the first u rows and columns. We are interested in a particular set of partitions which is going to be denoted by P,. Definition 1.1.1 Let t be an integer. We define P, = {AIA is a partition and A,- = A:- +t for all IS i 3 VA}. For instance, P0 = {Al/A; = A1, for l_<_ i S V,\} = {AIA is self-conjugated}. Figure 1.1.5 shows an element of P0. 0 e c Fig. 1.1.5 Observe that the partition p = 0 vacuously belongs to Pt, since it has no non-zero parts. Note that if p 6 Po, and t > 0 then by adding t nodes to each of the first 12,, rows of p we obtain 1] 6 Pt. We will say 1) is obtained by t-addition to p. An example is shown in Figure 1.1.6. o e e e e e e e e 0 EP0 e e e 0 EP2 e e Clearly, we can go backwards: given an element 17 of P,, with t > 0, we can obtain an element of P0 by deleting t nodes from each of the first 11,, rows. Definition 1.1.2 For a diagram A, the hook of the (i, j ) node is Haj = {(i,j')|j' 21'} U {(i',j)|i' > i}- The cardinality of HM, denoted hm‘, is called the hooklength of Hi,j- It follows that (1.1.5) hi,- =A.-+A;-—(i+j)+l. Note that if p 6 Po then h,,,- is odd. Thus |p| — V” E 0 mod 2. Lemma 1.1.3 Let t be a positive integer and A 6 Pt, then |A| - V)‘ E tVA mod 2. Proof. Since A 6 P,, A can be obtained by t-addition to p 6 Po. Because 11,, = V,\, |A| = Ipl + tun and lul E 11,, mod 2, we have lAl - VA = (l/‘l + til“) _ ”u = (l/‘l — Vii) + tVu 5 ti!“ mOd 2' B Let p and A be partitions. The notation p C_: A indicates that p.- S A, for all i Z 1. In terms of diagrams, this means that the diagram of p is contained in the diagram of A. The boxes in A which are not in p determine a diagram, called a skew-diagram and denoted A/u. The i“ row of A/u has length A,- — p,. The definitions of a semi-standard A/p tableau and its weight are analogous to the case p = 0. 1.2 Symmetric Functions Let C [[3]] be the ring of formal power series on the variables a: = {2:1, 2:2, 1:3, . . .}. An element of C [[x]] with all the monomials of degree n, is called a homogeneous formal power series of degree n. For Ir 2 1, let 5;, be the symmetric group on k letters. For each 1:, consider the function «5 = s. x CIIxII —-» Cllxll defined by (1.2.1) (Paf(W3 . . .)) 43+ f($p(1),$p(2)a$p(3)’ - . .) where p(i) = i for i > k. The function o5 defines an action of S". on C[[:r]]. Let A = (A1,A2, . . . ,An) be a partition. The monomial symmetric function asso- ciated with A is (1.2.2) mm) = Z xt‘xt’ - - ' wt." where the sum is over all distinct monomials with exponents A1, A2, . . . , An. For each A, m; E C [[3]] is homogeneous of degree |A| and invariant under the action of St, for every 1:, as defined in (1.2.1). Definition 1.2.1 The vector space spanned by the m,\ is denoted A = A($) = C[m,\] as A varies over all partitions. This vector space is closed under product and hence is a ring. It is called the ring of symmetric functions. It should be noticed that not all the elements of C [[3]] which are invariant under the action of S]. as in (1.2.1), can be written as a finite linear combination of the m A. For example [1,210 + x.) is invariant under 45 but is not in A. That is because the product contains monomials of every degree. The space spanned by all the mi of degree n is denoted by A“. Since the set {mAIA is a partition of n} is linearly independent, it is a basis for A”. So the dimension of A” is the number of partitions of n, denoted p(n). Note that if f E A9 and g E A" then fg E M” and thus A becomes a graded ring. 10 Definition 1.2.2 For n 2 O, the 12“ elementary symmetric function e,, is the sum of all products of n distinct variables xi. That is, co = 1, and for n 2 1 (1.2.3) en = m(ln) = Z $.33.) - - - 11:5". ‘1 (i2<'"<£n As an example, for n = 4, e, = $1$2$3$4 + $1$2$3$5 + 2:12:2st + - .. . For a partition A = (A1, A2, . . . , An) define (1.2.3') e; =e,\,e,\,---e,\n. Definition 1.2.3 For n 2 O, the 71‘“ complete homogeneous symmetric function hn is the sum of all monomials of degree n in the variables 13,“. That is, kg = l and for n 2 1 (1.2.4) h,, = m,\ = 2 2:51:13, - - - xi". IAI=n eases-gin For instance, if n = 4 ’14 = mm + mm) + mm) + mm 4 4 3 3 2 2 2:1+£2+---+xl:rg+a:2:rl+---+:rla:2 + £133 + - - - + 11172513334 + 2:11:233225 + - - - Similarly, as in the case of the e’s, we define for any partition A = (A1, A2, - - - , An), (1.2.4’) ’01 = huh; ° ' ° h,\ "0 Remark: For n < 0 we assume hn = en = 0. The definitions for e,\ and hi make sense for any sequence of non-negative integers. The proofs of the following results can be found in Macdonald [Mac 79] or Sagan [Sag 91]. 11 Theorem 1.2.4 The generating functions for en and hn are respectively (1.2.5) E(t) = Zert'=H(l+:r,-t), r20 :21 (1.2.6) H(t) = 2 kn" = 1'1(1- at)“. D r20 1'21 This theorem immediately yields H(t)E(—t) = 1. Extracting the coefficient of t" on both sides, results in the following corollary. Corollary 1.2.5 For each n > 0, 71 (1.2.7) Z(—1)kekh,,_,. = o. k=0 In addition to the basis formed by the m ,\, we have two other bases for A. Theorem 1.2.6 The sets {e,\|A is a partition of n} and {MM is a partition of n} are bases for A". D Since the e A form a basis for A, the e, are algebraically independent. Thus we can define a ring homomorphism w:A——1A by w(e,-) = h, for all i Z 0. In fact no is an isomorphism because of the next result. 12 Theorem 1.2.7 w is an involution. That is a)? is the identity. Proof It suffices to show w(h,,) = en. If n = 0, co 2 ho, hence w(ho) = e0. Assume w(h,-) = e,- for all i S n -— 1. Because w is a homomorphism, and by (1.2.7) each h,- can be written as a polynomial in terms of Cj,8 for j S i, w(ekh,-) = w(ek)w(h,-). Thus w(hn) = w(Z(—1)k+lekhn_k) k=1 = genrwkwwm) = E(—1)k+1hken_k k=1 2 en, El Definition 1.2.8 Let A = (A1,A2,...,A,,) be a partition. The Schur function corresponding to A is (1.2.8) 3, = Z; T where the sum is over all semi-standard A-tableaux T, and xT is as defined in (1.1.3). In a similar way, the skew Schur function corresponding to A/p is (1.2.8’) 3),, = 2 1:7” T where the sum is over all skew semi-standard A/p-tableaux T. To illustrate this, let A = (3,2,2) and p = (3,1). Some skew semi-standard A fp-tableaux are 13 whence the skew Schur function for A / p is 2 2 . 3A/u = $1132 + $132 + 2:1:lrgxg + - - - Proposition 1.2.9 The function s,\(:r) is a symmetric function. Proof: The following is a combinatorial proof due to Knuth [Knu 70]. Since the function ”(23) is homogeneous of degree |A|, it suffices to show the function sA(:c) is invariant under 45 for all k. Since any permutation is a product of transpositions of the form (i,i + 1) we need to show ((.-,.-+1),.,,(.)) 34* so) for all i. Let 7} be the collection of all semi—standard A-tableaux. We want to find a bijection f : 73 —; T,\ such that f(T) = T’ implies ((i,i + 1),:BT) 41* :cT'. We obtain T’ from T as follows. Look at the entries of T equal to i or i+ 1. If an i and an i + 1 are in the same column the entries are called fixed. If only one of i or i+ 1 appears in a column the entry is called free. In each row of T consider the free i’s and i+1’s. If a row contains r free i’s followed by t free i+ 1’s, then we change these into t i ’s followed by r i + 1’s. Call this new tableau T’. That the rows of T’ are weakly increasing is clear. When i is free, the entry immediately below it is at least i +2, and when i+1 is free the entry immediately above it is at most i — 1. So if a free i is changed into i + 1 then the new column is strictly increasing. Similarly, if a free i + l is changed into i, the new column is strictly increasing. Thus T’ is a semi-standard A-tableau. The map defined is an involution, since exchanging the number of i’s and i + 1’s in each row twice maps T into itself. The fact that ((i, i + 1), 1:7) 4’4 $7" follows because the number of fixed i’s and i + 1’s is the same in T and T’, while the number of frees i’s 14 and i+ l’s is switched under f. Therefore under the action of (i, i + 1), the exponents of z.- and 3,-4.1 are exchanged. Thus, this involution guarantees that sA(:r) is invariant under the action of each transposition. C] For instance, for the transposition (3,4), Figure 1.2.1 shows a T and the corre- sponding T’. The fixed entries are enclosed by circles and the free entries are enclosed by squares. 1112®EEI 1112®EEI 7‘@flflfl@5 7"@flflfl@5 @ @ Fig. 1.2.1 Our final basis for A (see [Mac,70] or [Sag,91]) is as follows. Theorem 1.2.10 The set {sAIA is a partition} forms a basis for A. D 1 .3 Lattice Paths Definition 1.3.1 a) Let Z x Z be the set of integer lattice points in R x R. If u = (a, b) and v = (a+ 1, b) are in Z x Z then the line segment no is called an eastward step. If u = (a, b) and v = (a, b + 1) are in Z x Z then no is called a northward step. We say that the step uv starts at u and ends at v. We call u and v the initial and end points of the step, respectively. b) Suppose u = (a, b) and v = (c,d) are lattice points in Z x Z with a S c and b S d. A finite u — v lattice path is a sequence of northward and eastward steps 31, s2, . . . , 3;, such that the first step begins at u, the last step ends at v, and the end point of s,- is the initial point of s,“ for 1 S i < k. 15 c) We define Z = ZU{oo}. Let u = (a,b) and v = (c,oo) with a S c be in Z x Z. A u —- v path in Z x Z with initial point u and end point v, denoted (a, b) l» (c, 00), also written p : (a, b) -—i (c, 00), is obtained by extending a finite u — w path, where w = (c, d) for some d, with an infinite number of northward steps along the line a: = c. Note that in this case there are infinitely many it — v paths but each one has only c — a eastward steps. Figure 1.3.1 shows a path in Z x Z. 39 86 37 38 34 35 - 81 32 33 Fig. 1.3.1 Let p be a lattice path with steps 31,32, . . . To each eastward step we associate two labelings, the e-labeling and the h-labeling, as follows. The e-labeling of the eastward step 3,- is L(3,‘) = 2. The h-labeling of the eastward step 3,- is L(s.-) = (number of preceding northward steps) + 1. Figure 1.3.2 shows the e and h labelings for the path given in Figure 1.3.1 16 Fig. 1.3.2 Let p be a path. We assign to each of the eastward steps of p the weight mm“) or mu“) depending upon the labeling we are considering. We now define two weights for a path p, depending on the labeling assigned to the eastward steps as: (1.3.1) as” = H m...) (1.3.2) 2? = 112““, 3i where s, varies over all the eastward steps in p. The connection of these weights with elementary and complete homogeneous sym- metric functions is as follows. For a fixed a,b and n, consider all paths (a,b) —”—+ (a + n, 00). There is a one-to-one correspondence between square free monomials in n variables and the weights of these paths as determined by the e-labeling. Simi- larly, there is a one—to-one correspondence between all monomials of degree n and the weights of these paths as determined by the h-labeling. Hence, (1.3.3) 6n = Z :r” (a,b)-L(a+n,oo) and (1.3.4) 12,, = Z 2". (a,b)—L(a+n,oo) Products of elementary and complete homogeneous symmetric functions can be obtained by considering weights of n-tuples of paths. Let ’P be the collection of all 17 n-tuples of paths P = (p1,p2, . . . ,pn) with initial points u], u;, . . . , u", and end points v1, . . . , v... We insist that the initial point of p.- is u,- for all i. However the end points of p1, pg, . . . , pn can be 120(1), van), . . . , ”0(a) (respectively) for any permutation a 6 Sn. If the n-tuple P corresponds to the permutation a we will write P = P0. Each path in P, is written 19,- 2 u,- ——> 210(5). An n-tuple P = (p1,p2, . . . ,pn) is called intersecting if it contains two paths with a common node, that is p,- n 12,- ;£ 0 for some i ;E j. Otherwise, it is called non- intersecting. Count the number of steps from the initial point of a path to a node where intersection with other paths occurs. The node which corresponds to the minimum number of steps is called the first intersection of the path. Definition 1.3.2 Let P = (p1,p2,...,pn) be an n-tuple of paths. If P = P, we define its sign to be (—1)P = (—1)". Also, the weight of P corresponding to the e-labeling is (1.3.5) 2:” = pr‘, i=1 while the weight corresponding to the h-labeling is (1.3.6) 3” = H see. We define the signed weights of P to be (—1)Pa:P and (-1)P:i:P respectively. For example, Figure 1.3.3 (a) - (b) shows a triple P with the e and h-labeling respectively. In this case a = (2,3) and its sign is (—1)" = -1. The weights as defined in (1.3.5) 2 2 and (1.3.6) are 2:? 2 13111322731174 6 2 1:52:19 and :EP = 313323425. Proposition 1.3.3 Let ’P be the collection of all n-tuples of paths of the form p.- : u,- —+ v.-, with u; = (a.-,b,-) and v.- = (c,~,oo). That is, for all n-tuples of paths in ’P, the initial and end point of the path p,- are fired. Let A,- = c, — a,- then, for L. 18 A = (A1,...,A,,) we have (1.3.7) e; = Zap P and (1.3.8) hA = 22” P where P varies over all n-tuples of paths in ’P. v2 '03 01 ‘02 v3 v1 | 1 I 1 i -63 l .5.9 . .. : 1 : . u -‘Li 9 1 -4. o . 3 I g | b ...3_l i _.3-l 1 ' i ' i 1 l 2 3 1 4 5 6 1 l 1 1 1 l 1 1 U1 : i “1 : i . l t l t U3 112 113 112 (a) (b) Fig. 1.3.3 Proof: From (1.2.3’) e) = ehey, - - - e,\,,. By (1.3.3) e), = 201' b_)_.:._,+(c_ 00) .31". Hence, 6A = H ( 2 mp.) i=1 (a.,b.')—flo(c.',oo) = 2.1-” P where P varies over all n-tuples in 'P. Similarly, from (1.2.4’) h,\ = h,\,h,\,-~h),n. By (1.3.4) h), = 2(3 b~)—’—’L(c Mi“. Thus by = :II( 2 ftp") (Cabal-514% .00) = 21-” P 19 P varying over all n-tuples in 15. D We define the x-coordinate function on Z x Z by a:((a, b)) = a. For u = (a, b) and v = (c,d) in Z x Z we write 11 < v if :c(u) < x(v) and say that u is to the left of v (or v is to the right of 11). When we refer to a partial order between lattice points we assume it is the order induced by the function 2:, unless otherwise stated. Given an n-tuple P of paths we will always write the initial points as (u1,...,un_1,u,,) where uk > uh“. We also write an n-tuple of paths as P = (p1,. . .,p,._1,p,,), where p1 is the path with rightmost initial point, p; is the path with second rightmost initial point and so on. Definition 1.3.4 We define a function i : 'P —+ ’P the following way: a) If P is a non-intersecting n-tuple of paths, then i(P) = P. b) If P 2 (p1, . . . ,pn) is an intersecting n-tuple of paths, choose the path with the smallest index, say pk, such that p)‘ 0 pi gé G for some j > lc. Let v0 be the lattice point in pk where the first intersection occurs. Select the path with smallest index intersecting pk at v0, call it p,. Define i(P) = P’ with P’ = (p’l, . . . ,p’n) where i) p’,=p, ifs¢k,qand ii) p), : ugh —p-"—* vo 33-) vauq), p" . 1’1. .35., . q . u", v0 vam‘). Note that the permutations determined by P and P’ differ by a transposition. The next result follows immediately from the definition of i. 20 Lemma 1.3.5 The function i as in definition 1.3.4 is an involution. Also, ifP is an intersecting n-tuple with i(P) = P’ then (-—1)P = —(—1)P'. Cl Lemma 1.3.6 Let P be an intersecting n-tuple with i(P) = P’ as in definition 1.3.4. a) If the paths have the h-labeling and the initial points are on the line y = c, then £2"qu = Wire‘s”; and hence (—1)P§:P + (—1)P'§:P' = 0. b) If the paths have the e-labeling and the initial points are on the a: + y = c then 2:"qu = xpirpi and hence (-—1)P.rP + (-—1)P’:I:P' = 0. Proof: a) To reach v0 we have to move the same number of northward steps from the initial points, since they are on the line y = c. Thus, after switching paths to obtain p6, and pf, the h-labeling remains the same and so a?” 5:"? = 2:" 5%. Since all the other paths are unchanged, we have 5:” = 2’”. But the permutations corresponding to P and P’ differ by a transposition, so it follows that (—1)P:i:P + (—1)P':i:P' = 0. b) Say the point v0 is on a line a: + y = a, for some a > c. The number of steps on any lattice path between the lines a: + y = c and :1: + y = a is c — a. So, after the first intersection on pk the e-labeling for p5, and pf, is the same as the one for p, and pk, respectively. Therefore as?“ :13”? = spirit”; and because all the other paths in the n-tuple remain unchanged, 15” = .13” '. Since the signs of the permutations corresponding to P and P’ differ by a transposition, it follows that (—1)P:L'P + (-1)P'2:P' = 0. Figures 1.3.4 (a)-(b) illustrates cases (a) and (b) of Lemma 1.3.6, respectively. 21 01 02 03 w. 2 0 vs .“ 4. ink}... _ . 4. 3 3. p 2 illu 2r 3 u P. in... 4. 4. 3. 3. . :5... 2F 3 u P. 1 u v i 5 A. O 4 2 l v 4 3 ll Ill. U _ 3 2. hill 1 o 2 u P. 111 Fig. 1.3.4 Chapter 2 Main Results 2.1 Jacobi- Trudi Identities By Theorems 1.2.6 and 1.2.10 the sets {eAIA is a partition of n} {hAIA is a partition of n} {s,\]A is a partition of n} are bases for A". Equation (1.2.7) can be used to express each h A as a linear combination of ep and vice versa. Jacobi [Jae 41] expressed each s; as the determinant of an array of certain sym- metric functions. Later, his student Trudi [Tru 64] simplified the demonstration of these identities. In each determinant, all the entries are either complete homogeneous or elementary symmetric functions. Thus, these, determinantal identities provide a way to write 3) as a linear combination of h,, or ep with lpl = IA]. They can be proved combinatorially using a method of Gessel [Ges um] involving lattice paths. For completeness we present this proof here. 22 23 Theorem 2.1.1 (Jacobi-Trudi determinants) Let A = (A1, A2, . . . , An) be a partition. Then (2.1.1) 3A = lhA.—e+j| and (2.1.2) 3.. = le.,_.,,-|. Proof: To prove identity (2.1.1), we consider n-tuples of paths P = (p1, . . . , pn_1, pn) with initial points 11; = (1—i,0) and end points v,- = (AJ- —-j + 1,00) for 1 S i, j S n. L :1 We regard the weight determined by the h-labeling as in (1.3.6). Note that u1>u2>--->un and v1>v2>--->vn. Due to the ordering of the initial and end points of the paths, the non-intersecting n-tuples correspond to the identity permutation id. Therefore the sign of non- intersecting n-tuples is (—1)"’ = 1. For an intersecting n-tuple P, take pk and p, as in Definition 1.3.4. Since the initial points are on the line y: 0, 2:“qu = $932”; and so by Lemma 1.3.6 (a) (—1)P:1:P+ (—1)P’x”' = 0. Hence, the signed weights of intersecting n-tuples of paths cancel in pairs. Using the definition of determinant, identity (1.3.4), the definition in (1.3.6), Lemma 1.3.6 (a) and the previous discussion, we obtain lhA,—i+jl = Z(—1"Hh1,(,_a(.)+. 068'; 3 1 fl 2 (*1)’H Z 33”" aesn i=1 (,_,-,o):1.(,\,(,.,_a(.-)+1,oo) 24 = Z Z(_1)Pajpc 065'; Pa = Z 5" P where P varies over all non-intersecting n-tuples. To complete the proof we establish a weight preserving bijection between non- intersecting n-tuples of paths and semi—standard A-tableaux. For this part of the proof, weight preserving means that if the n-tuple P corresponds to the tableau T under a bijection, then a?” = 237. Let P = (p1,. . .,p,,-1,p,.) be a non-intersecting n-tuple. Since the path p,- has A,- eastward steps, we can fill the diagram of A = (A1, A2, . . . , An) as follows. Fill the i’h row of A, from left to right, with the h-labeling of pg, also read left to right, and call this tableau T. By the definition of the h-labeling of a path, the rows of T are weakly increasing. Because the paths do not intersect and the initial points are on the line y = 0, the lc’h eastward step of p.- lies on a horizontal line with y coordinate at least one less than the y coordinate of the horizontal line containing the k“ eastward step of p51,]. Therefore, T(i.k) < T91”), and hence, the columns of T are strictly increasing. Thus, T is a semi-standard A-tableau. From the definitions of 5:” in (1.3.2) and :1:T in (1.1.3), it follows 3:” = :rT. Now given a semi-standard A-tableau T, we map it to an n-tuple of paths as follows. Take the entries of the i”‘ row, weakly increasing, as the h-labeling of an infinite path p,- with initial point 11.- = (1 — i,0). Note that the h-labeling uniquely determines p,- and that its end point must be v,- = (A, — 1+1, 0). Because the columns of T are strictly increasing, that is T(i.k) < Th1”), and the initial points are on the line y = 0, we have that the It“ eastward step of p, lies on a horizontal line which is below the horizontal line containing the k’h step of [35+]. So, the k’h eastward steps do not intersect. Due to the choice of initial points, the k’h eastward step of pi“ is one unit to the left of the Ic’h eastward step of p,- for 1 S k S Ag“. Thus, the northward 25 steps between the In“ and (k + 1)” eastward steps of the two paths do not intersect. Hence, the paths pm and p,- are non-intersecting. From what we have shown and the relative placement of p,- and [25+], it follows that the semi-standard A-tableau is mapped to an n-tuple of non-intersecting paths. Since this construction is a step by step reversal of the one given in the previous paragraph, we have a bi jection. Because the bijection is weight preserving (2.1.3) 22? = 237' P r where P varies over all non-intersecting n-tuples of paths with initial points u,- and end points v,-, and T varies over all semi-standard A-tableaux. But the right hand side of (2.1.3) is the definition of s; as in (1.2.8). Hence the identity (2.1.1) holds. An example indicating the correspondence between non-intersecting n-tuples of paths and semi-standard A-tableaux is given in Figure 2.1.1. v4 v3 02 v1 . 'l‘ 5] - 0 ( 4 4 °' 122 3 3‘3 T233 P’ ‘ 34 , 2, 2,2 45 l 1 1) U4 U3 U2 U1 Fig. 2.1.1 To prove identity (2.1.2) we consider n-tuples of paths with weight corresponding to the e-labeling as defined in (1.3.5). We choose as initial points of the n-tuple 26 u; = (1 —i,i- 1) and end points v,- = (A,- —j+ 1,00) for 1 S i, j Sn. Note that u1>u2>--->un and v1>v2>--->v,,. Due to the ordering of the initial and end points of the paths, the non-intersecting n-tuples correspond to the identity permutation id. Therefore the sign of non- ‘ 1 intersecting n-tuples is (—1)“’ = 1. For an intersecting n-tuple of paths we take pk and p, as in Definition 1.3.4. Since the initial points are on the line y + a: = 0 and we are considering the e-labeling, the weights of intersecting n-tuples of paths cancel in pairs by Lemma 1.3.6 (b). The previous discussion together with the definition of determinant, the identity (1.3.3), the definition in (1.3.5) and Lemma 1.3.6 (b), yield (6A,(,)-a(i)+i) lexa-iw'l = ZED”. n 065" 1: _ n = 2(_1)0H Z 2:" 06571 {:1 (1_i'i_1).flo(AU(i)-U(i)+19°°) ___ Z: Z(_1)PaxPa 0637; Pa = Z :5” P where P varies over all n-tuples of non-intersecting paths. We obtain a weight preserving bijection between non-intersecting n-tuples of paths and semi-standard A’otableaux as follows. Consider a non-intersecting n-tuple P = (p1, . . . , pn). Since the path p; has A,- eastward steps we fill the i’h column of A’ from top to bottom with the e-labeling of p;, read from left to right. Call this tableau T. 27 Columns are strictly increasing by definition of the e-labeling. Due to the choice of initial points, and since the paths pg and pg.” are non-intersecting, the lc’h eastward step of the path pg.” lies one unit to the left and at least one unit up from the k’h eastward step of the path pg, for 1 S lc S Ag“. Since the difference in the e-labeling of these two steps is one less than the difference in their y coordinates, the rows of T are weakly increasing making it a semi-standard A’-tableau. From definitions in (1.3.1) and (1.1.3) it follows .23” = (J. Conversely, given a semi-standard A’-tableau T, let pg be the infinite path with initial point ug = (1 —- i,i — l) and eastward steps with the e-labeling determined by the entries of the i’h column of A’, from top to bottom. The path pg is uniquely determined by the e-labeling and it must have end point vg = (Ag - i + 1, 0). Since the rows of T are weakly increasing and the initial point of pg“ is one unit to the left and one unit up from the initial point of pg, the k’h eastward step of pg“ is one unit to the left and at least one unit up from the k’h eastward step of pg, for 1 S k S Ag“. Thus the paths pg+1 and pg do not intersect. Therefore the unique n-tuple P = (P1, . . . , p") so obtained is non-intersecting and IT = 2’”. Since the bijection is weight preserving (2.1.3’) 22” = :xT P T where P varies over all non—intersecting n-tuples of paths with initial points ug and end points vg and T varies over all semi-standard A'-tableaux. The right hand side of (2.1.3’) is the definition of s), as given in (1.2.8), hence the identity (2.1.2) follows. C] There are Jacobi-Trudi identities corresponding to skew Schur functions. Theorem 2.1.2 Let p and A be partitions with ,u Q A. Then (2.1.4) 8.1,. = lhAg—Hj-ml 28 and (2.1.4,) SAI/ul 1: ICA'._,'+J'_“J . Proof: To prove (2.1.4) we consider n-tuples of paths with the h-labeling. We take as initial points ug = (1 —i+pg,0) and end points v,- = (Ag —j + 1, 00) for l S i, j S n. Since pg 2 pg“, we have 11,- > ug+1. Because the initial points are on the line y = 0, for two intersecting paths the first intersection occurs after an equal number of northward steps. Hence, by Lemma 1.3.6 (a) the signed weights of intersecting n-tuples of paths cancel in pairs. The non-intersecting n-tuples correspond to the identity permutation and so they have sign (-1)"’ = 1. From these observations, it follows in the usual manner that lhAg—i+j-#Jl = )0 412.1: (h/‘anrOl‘lH-I‘i) 06:5n( 3:1 11 = Z (—1)" 1'1 )3 see UESn ’=1 “4+“,,o)—’1L(A,(g)—a(i)+l.00) = 22(— 06311 Pa = 25” P where the summation is over all non-intersecting n-tuples of paths P. A weight preserving bijection between non-intersecting n-tuples of paths with the h-labeling and semi-standard A/p-tableaux T is obtained as follows. Let P = (p1, . . . , pn) be a non-intersecting n-tuple. Since the path pg has eastward steps, fill the i’h row of T, from left to right, with the h labeling of the path pg. Rows are weakly increasing by the definition of h-labeling. Let’s consider the paths pg and pg“. Since [1; — pi.“ = a Z 0, the (a + It)“ eastward step of pg“, 1 S k S Ag.“ — a, must be on a horizontal line with y coordinate at least one greater than the y coordinate of the 29 horizontal line containing the lc’h eastward step of pg. Since the initial points are on the line y = 0, the h-labeling of the (a + k)“ eastward step of pg.” is greater than the h-labeling of the lc’h eastward step of pg. Thus columns are strictly increasing and hence, T is a semi-standard A/p-tableau. Therefore, to each n-tuple of non- intersecting paths corresponds a unique semi-standard A / p-tableau T, with 5:” = :rT. Conversely, given a semi-standard A / p-tableau T, a unique n-tuple of non- intersecting paths is obtained as follows. Construct the path pg with initial point (1 - i + pg, 0) and take the entries of the i’h row of T as the h-labeling for its eastward steps. The paths are uniquely determined by the h-labeling and the end point of the path pg is vg = (Ag — i + 1, 0). Due to the choice of initial points and the fact that the difference in the h-labeling of the (a + k)”‘ eastward step of pg.” and the k‘h eastward step of pg is positive, the paths pg.“ and pg are non-intersecting. Hence (2.1.4) follows from (1.2.8’). To prove (2.1.4’), we consider n-tuples of paths with the e-labeling. We choose as initial points ug = (1 — i + pg,i — 1 — pg) and end points v,- = (Ag — j + 1,00) for 1 S i, j S 11. Since pg 2 flg+1, we have ug > ug+1. Two intersecting paths have equal number of steps up to the first intersection (see Lemma 1.3.6.(b)). Thus, the weights of intersecting n-tuples of paths cancel in pairs by Lemma 1.3.6 (b). So, 73 lexa-Hj-ujl = Z (’lla H (8*a(d1-0(‘)+‘-"i) = Z (4)0. 068" 3 Z Z(_1)P01.Pa 0651; Pa = D" P where P varies over all non-intersecting n-tuples of paths. 2 3m 73 = (1-i+pg,0)fl*(/\a(g)-0(t)+l,00) 1 30 A weight preserving bijection between n-tuples of non-intersecting paths with the e-labeling and semi—standard A’ / p’ tableaux T is obtained as follows. Since the path pg has Ag — pg eastward steps, fill the i”‘ column, from top to bottom, with the e- labeling of the path pg, read from left to right. Columns are strictly increasing, by the definition of e-labeling. Let pg -— [15.1.1 = a, thus the (a + k)”l eastward step of pg+1 must be at least one unit to the left and one unit up from the k’h eastward step of pg. Also, due to the choice of initial points the difference in the e-labeling of these two steps is one less than the difference in the y coordinates of the horizontal lines containing them. Hence, the rows are weakly increasing and if the semi-standard P T=$ . tableau T corresponds to P then 1: Conversely, given a semi-standard A’ / p’-tableau T, choose a path pg with initial point 11g = (1 -— i + pg,i — 1 — pg) and eastward steps with e-labeling determined by the i”‘ column of A’ / p’ . The path pg is uniquely determined by the e-labeling and its end point is vg = (Ag — i + l, 00). Since the rows are weakly increasing, the e-labeling of the lc’h eastward step of the path pg is less than or equal to the e-labeling of the (a + lc)”' eastward step of the path pg+1, where pg — pg.” = a and 1 S k S Ag.” — a. Because of the choice of initial points, the (a + k)“ eastward step of pg.” is one unit to the left and at least one unit up from the Ir“ eastward step of the path pg. Hence, pg and pg“ are non-intersecting and :rT = 2:”. Thus we have a weight preserving bijection and (2.1.4’) follows from (1.2.8’). D 2.2 Some Jacobi- Trudi Type Identities The identities we are about to prove relate certain determinants, where each entry is the sum or difference of certain complete homogeneous symmetric functions, to sums of certain skew Schur functions. 31 Theorem 2.2.1 Let A = (A1, A2, . . . , An) be a partition. Fort 2 0, a fixed integer, (2.2.1) I’m-1H + hAg—i—j+1—tl = Z (‘1)(lpl_(t+l)u")/25A/u 149‘ “GP: (22-?) lhA.-a+j - hA.-£-j+1-t| = Z: (-1)("‘"("1)"“)’281/,.. ugA #61:} We first prove some lemmas. For A = (A1,A2, . . . ,An) a partition and t Z 0 an integer we consider n-tuples of paths with initial points of the form (2.2.3) ug=(1—i,0) or wg=(j+t,0) for 1 S i, j S n, and end points (2.2.3’) 11;, = (Agc — k +1,00) for 1 S lc S n. We write the initial points of an n-tuple of paths in decreasing order of their :1: coordinates as (2.2.4) (w,-,,w,-,,...,wgm,u,-m+,,...,ujn) wheren2j1>j2>--->jm,jm+1 m, we have $(uji) — 111113.“) 2 (”(115) _ $(Ug+1). 33 So the.) - $011) 2 $(Uj.+1)- $(Ui+1) which is pg _>_ #5.“, for m < i < n. Finally, mm...) — m-..) 2 mm) — an...) Hence, new...) — mm) 2 up...) — mm“). which is the same as pm 2 pm“. All the cases together give pg 2 [15+], for 1 S i S n, so p is a partition. Now, let P = (p1, . . . ,pg.) be a non-intersecting n-tuple of paths with the given initial points. Thus, for each i the path pg has end point vg, that is pg : (1 —i+pg, 0) —-> (Ag —i + 1, 00). So, the difference between the first coordinates of end and initial points of each path is greater than zero. It follows that pg S Ag, for all i, and so p Q A. D We now relate the length of the main diagonal of p with the number of wg and u,- occuring as initial points of the n-tuple of paths. Lemma 2.2.3 Let P be an n-tuple of paths with initial points as in (2.2.4). Up is the partition determined by the initial points, then 1),‘ = m. Proof: According to (1.1.4) it has to be shown that pg 2 i for i S m and pg < i for i> m. Sincet 2 0, :r(w,-g) >0. That isl—i+p.' > Oand so pg >iforiS m. Similarly 2(ugg) S 0, that is 1 — i + pg S 0 for m < i S 12. Hence, pg < i for i > m. C] The next result explains the appearance of the partition from Pg in our main theorems. 34 Lemma 2.2.4 Lett 2 0 be a fixed integer. There is a bijection between n-tuples of initial points as in (2.2.4) and partitions in Pg. Proof: Note that ifj, > j] then uj, = u,. Thus, p, = 0 for r > j]. On the other hand, if jr 0 for 1 S i S 11. Since p: Z pf“ we have that 1 — i + pf>1—(1+i)+ pf“. That is jg > jg+1 for 1 S i < m. Also, pk _>_ pk.“ and so k — pk < (1 + k) — pk“. Thus, jk j2>~~>jm andjm+1 <--- 61,-. Lemma 2.2.6 Port 2 0 a fixed integer, let P = P, be a non-intersecting n-tuple of paths with initial points as in (2.2.4) and p the partition determined by the initial 38 points of P. Then, a fill—0+1)” (-1)P = ('4) = (-1) 5 - Note that since p 6 P, by Lemma 1.1.3, |p| — (t + 1)1/,, is even. Proof: It suffices to show that the number of inversions of a“ is lul -(t+1)V 2 . Since P, = (wj,,w,-,,...,w,-m,u,-m+,,...,ugn) is non-intersecting, using one row notation for permutations we have a“ = j] - - ~jmjm+1 - - -j,, with jg > > jm and jm+1 < - - - < jn. For 1 S i S m, all the numbers to the left of jg are greater than it. So the numbers 1,2, . . . , jg — 1 are all to the right of jg and causing inversions with it. For m < i S n, all the numbers to the right of jg are greater than it. So they do not generate any inversions. Thus, the number of inversions is inva‘1 =(j1—1)+(2'2—1)+---+(jm-1). Now consider the diagram of p 6 Pg. After we delete a strip with (t + 1)1/,g boxes from the diagram of p, as shown in Figure 2.2.3, we obtain an array with |p| —(t+1)1/,, boxes represented by the two unshaded regions. By the definition of Pg, the two unshaded parts have the same number of boxes. The size of the upper unshaded part is (#1—(t+1))+(u2-(t+2))+-~+(#m-(t+m))- Sincet“: =j.+t-(1-k), for 1 S k S m, we can write this as (j1—1)+(j2 — 1) + - -- + (jm — 1). Therefore lfll-(t'i'lll’: 2 (jl—1)+(.l2_1)+"°+(jm—'1) and the result follows. Cl 39 XXXXX XXXXX XXXXX XXXXX W—J (t+1)u Fig.2.2.3 Remark: If a 75 id is a permutation, there may be non-intersecting n-tuples of paths which correspond to a. In Figure 2.2.1 we exhibited a non-intersecting triple of paths corresponding to a = (1,2, 3). Now, we put together these results to prove Theorem 2.2.1, which we restate here for easy reference Theorem 2.2.1 Let A = (A1, A2, . . . ,An) be a partition. Fort _>_ 0, a fixed integer, (2.2.1) lhAg—i+j + hAg—i—j+l-tl = Z: (‘1)(lul—(t+1)u”)/23A/m uSA PEP: (2.2.2) lhAg-i+j _ hA‘_.._j+l_t| = Z (‘1)(lul-(t-1)V”)/2Sx/u- uQA HEP: Proof: We first prove identity (2.2.1). Consider initial points of the form (2.2.4). Combining the definition of determinant and the identity (1.3.4) we have n lhAg-i+j + hAg-i—j-H-tl = Z (-1)0 H(h1,(g,_a(r)+.' + h1,(,,_a(i)—i+1—1) 063" i=1 =Z(—1rfi( z 221+ z .] oesn i=1 (1-1,o)-!-o(»\.(.-)-a(i)+1.oo) (t+i.0)-3~(Aam-0(‘)+1’°°) = : Z(—1)”°i”‘ ”€511 Pa id 40 where P, varies over all n-tuples of paths corresponding to 0. Since the initial points are along the line y = O and we are considering the h-labeling, by Lemma 1.3.6 (a) the signed weights of intersecting n—tuples cancel in pairs. Thus, |h1._.-+g + hxg—e-m—tl = Z Z(-1)P°~’5P° 063,, P, where now P, varies over all non-intersecting n-tuples of paths corresponding to a. Group the signed weights of non-intersecting paths that have the same initial points. By Lemma 2.2.4, identity (2.2.5) and Lemma 2.2.6 it follows that lul-(H'llu lhA.—i+j+hA.-i-J‘+1—t|=2(4) 1‘ SA/w 119* "GP; To prove the identity (2.2.2) we proceed as follows Vin-1+1 — hAg—i—j-H—tl = Z (-1)" H(h1.(.)-a(i)+1 — hxag.)—a(i)—i+1-t) n = X (-1)" ll )3 53" - Z 5‘" 053" i=1 (1-1.0)_E—.(1,(g,_a(1)+1.oo) (i+t,0)—L(,\,(g,—a(i)+1,oo) In each factor, the second summation is over paths with w’s as initial points. When we multiply out the product indicated for each 0' 6 3,, we obtain a sum of signed weights of n-tuples. Each n-tuple has as many factors with negative sign as paths with initial points wg. Let u be the number of w which are initial points of the Pa n-tuple P,. By Lemma 2.2.3 11,, = Vpa, where p is the partition determined by the initial points of P,. Thus, P x lhAi-i'i'j — hAg—i-j-{J—t] = E : E (_1) 0+VPU (LPG. 0651; Pa By Lemma 1.3.6 (a), signed weights of intersecting n-tuples cancel in pairs. So, we can consider the last identity as summed over all non-intersecting n-tuples P,. 41 Group all the monomials for n-tuples with the same initial points. Then, by identity (2.2.5) and Lemma 2.2.6, we have lPl-('+1)”E+”g Z (—1) SA/u 149A P6P; I’m-1+1 - hA.-i-j+1-t| = = z(—1>'-“'ir"—’”*=st.. s 149* ”6”: Theorem 2.2.7 Let A = (A1, A2, . . . , An) be a partition. Fort = —1 we have lu (2.2.6) Hug—1n + hA.-i—j+2l = 2 Z (“ll-713M“ .2st (22-7) Illa-m - h.\.--:°-j+2| = 0- Proof: To prove (2.2.6) we consider initial points as in (2.2.3) and satisfying the condition established in (2.2.4). Since t = —l, we have u1 = 1121. So we will always let 111 be present as an initial point in the n-tuple; that is, we always have jm+1 = 1. Define p as for the case t Z 0. The proof of Lemma 2.2.2 is the same as before, so p is a partition. Since each w that appears in the n-tuple still satisfies :r(w) > 0, the demonstration of Lemma 2.2.3 holds for t = —1. The proofs of Lemmas 2.2.4 and 2.2.5 can be mimicked without change for t = —1. Thus, identity (2.2.5) is still valid. Finally, the proof of Lemma 2.2.6 proceeds similarly, except that since t + 1 = 0 we do not have to delete any strip. In this case the number of boxes to the right of the diagonal and including it is [pl/2. So we have lp] = 2(number of inversions of 0). Thus, 42 Therefore, we can apply all the results as for t 2 0 to yield n lhA.-i+j + hA.-i-j+2| = Z (-1)” H(hx.(.-)-a(i)+i + hA.(.-)—a(i)-i+2) 063,. i=1 n = Z (—1)"H Z i"+ Z 56‘” 065" i=1 (l-i,0)L(Adi)—0(i)+1.°0) (i“lv0)"’,—'(Aa’(i)"a(i)+l'°°) = z (—1)" 2 z: aeSn (o,o)_’_.((,\,(,,—a(1)+1.oo)) n 11 z 5.». z i=2 (1_§,0)—L(Aa(,)—a(i)+l,oo) (i—1.0)L(Aa(i)-”(‘)+1'°°) = 2 Z z(—1)Pai-Pa 068,. Pa = 2Z(—1)P°;2Pa Pa where, by Lemma 1.3.6 (a), P0 varies over all non-intersecting n-tuples of paths with u; as one of the initial points. Group the signed weights of n-tuples of paths with the same initial points. Now, we use the bijection of Lemma 2.2.6, the identity (2.2.5) and the observation made at the beginning of the proof to obtain lul I’M—m + hA.—i-j+2| = 2 2, (-1)73A/u- pCA pet; To prove (2.2.7), note that for a 6 Sn the first factor of each of the summands participating in the determinant is hAc(1)—U(l)+l — hAa(1)-a(1)+l = 0. Thus, the result follows. [3 The next result was proved by Bressoud and Wei [B-W 92]. Here, we give a proof of it using Theorem 2.2.1. 43 Corollary 2.2.8 Lett 2 —1 be an integer. Then 2(t- MHz Z( (—1)0 H( (I‘M-Hm“) "l' ('-1)(t+ltI)/2hAg-i—a(i)+1—t) 063,. i=1 = Z (_1)[lul+vu(ltI-1)]/2sA/w #93 “GP: Proof: We rewrite the statement of the corollary as: (a) Ift = — I’m-m + h.\.—i—j+2| = 2 Z: ("UM/23m- pCA per; 1 (b) Ift is even, lhA.-i+j + hA.—£—j+1—tl = Z (_1)[lul+uu(t—1)]/23/Vu. Mg“ O‘GP: (c) Ift is a positive odd integer, IhA.-e+j - hA.-i—j+1—t| = (-1)[""+"“(H)]/23A/w uCA ”6?; Now we proceed to prove these three. (a) This is the content of the identity (2.2.6) already proved in Theorem 2.2.7. (b) We have that wig—“115 — tu = W. Since t is even (_1)(lul+(t-l)v)2 = (_1)(lu|—(t+1)u)/2. Hence, the identity in (b) is (2.2.1) for t even. (c) We have that Milt—11‘: — (t — l)V = W. Since t — 1 is even (__1)(lul+(t-1)V)2 z (_1)(lu|-(t-1)V)/2. 44 Hence, the identity in (c) is (2.2.2) for t odd. Cl Using the ring homomorphism w in Theorem 1.2.7, we have w(hA) = e,\ and w(s;) :2 8y. When we apply (.0 to the identities (2.2.1), (2.2.2), (2.2.6) and (2.2.7) we obtain, for t Z —l, IeAfl-H + eA,_,-_j+1_,| 2 Z (_..1)(lul‘(t+l)Vu)/2SA,/u' MC} “GP; and €A.—i+j _ 8A.—i-j+1—tl = Z (_1)|#l—(t-1)Vu/23A'/#" HEX HEP; We can also give a combinatorial proof of these identities. Theorem 2.2.9 Let A = (A1, A2, . . . , An) be a partition. Fort Z —1, a fixed integer, (2.2.8) ICA.—i+j + 6A,—i—j+1_tl = Z ('1)(lul—(t+1)”“)/23y/ur 55A and (2-2-9) 6A.-:‘+j - €A.-i—j+1-t| = (-1)“"Ht-l)y“)/23A'/u'- :3. In particular for t = —1 we have ltl (22-10) ICA,—i+j + 6A.—i—j+2| = 2 Z (—1) 2 3A’/u'a p253, (2'2'11) leAi-H'j _ eAr-i-i-Hl : 0' First we make some remarks. For A = (A1, A2, . . . ,An) a partition and t Z —1 an integer we consider n-tuples of paths with initial points of the form (2.2.12) u'—=(1—i,i—1) or w;=(j+t,—j—t) 45 for l S i, j S n, and end points (2.2.12’) 22;, =(Ak—k+l,oo) for 1 S k S n. Observe that for t = —1, u1 = wl. In this case we always write the initial points of an n-tuple of paths as in (2.2.4) with jm+1 = 1 and ul in it. The proofs of Lemmas 2.2.2, 2.2.3, 2.2.4 and 2.2.6 go through unchanged, since :c(u(-) = a:(u,-) and 23(w3) = $(wj) for 1 S i, j S n. Note that for Lemma 2.2.6 the strip of size (1 + t)v is removed from under the diagonal instead of from the right hand side. For Lemma 2.2.5 we have the following analogue. Lemma 2.2.10 There is a bijection between n-tuples of non-intersecting paths as in (2.2.1.?) with fixed initial and end points, and semi-standard X/p’ tableaux, where a is determined by the initial points and the end points are determined by A. Proof: Consider non-intersecting n-tuples of paths with initial points as in (2.2.12) and satisfying the condition in (2.2.4). Assign the e-labeling to each path. Now the proof goes as for the skew case of the J acobi-Trudi determinants involving elementary symmetric functions in Theorem 2.1.2. D By Lemma 2.2.10 2 3T = Z xP T P where T varies over all semi-standard X/p’ tableaux and P varies over all non— inter- secting n-tuples of paths with initial points as in (2.2.12) which determine [1 and end points as in (2.2.12’). From these remarks and (128’) we obtain (2.2.13) SW, = 2 :cp. P 46 Proof of Theorem 2.2.9: The proof of (2.2.8) goes exactly parallel to that of (2.2.1) in Theorem 2.2.1, using the corresponding lemmas about elementary symmetric func- tions and partitions determined by initial points as in (2.2.12). Since we are using the e-labeling, the cancellation of signed weights of intersecting paths is due to Lemma 1.3.6 (b). Similarly, identity (2.2.9) is obtained by following the proof of (2.2.2) and using the elementary symmetric functions lemmas together with the ones about the partition determined by the initial points. The identities (2.2.10) and (2.2.11) are obtained similarly as (2.2.6) and (2.2.7) using the parallel results for elementary symmetric functions. D 2.3 Symplectic and Orthogonal Analogs Definition 2.3.1 Let A = (A1, . . . , A") be a partition and A = {1,1,2,2, . . . ,n,fi., . . .} a totally ordered set with 1 < I < 2 < 2 < < n < n < A semi-standard A-tableau T with entries from A is called a sp—tableau if all the entries in the row i are greater than or equal to i. In Figure 2.3.1 T1 is a sp—tableau (3, 2, 1)-tableau while T2 is not. 112j 12?] 22 1'3 _3. 5!. T1 T2 Figure 2.3.1 We assign weights to the entries of a sp—A-tableau T as follows. If i appears as an entry then we give it weight w(i) = 23;, and if i is an entry then we give weight 47 w(i) = 13,71. The weight of T is defined as T x = H w(T(i.1))° (i.j)eT For the s tableau T1 in Fi ure 2.3.1 3T1 2 xlxlxgx’lx’lxg, = 3223-1233. I" 2 2 1 2 For the rest of the section we consider 1"“ = ($1,314,172, 3?, . . .). Definition 2.3.2. Let A be a partition. The sp Schur function corresponding to A is 8pA(.’E*1) = ExT T where T varies over all sp—A-tableaux. The sp Schur functions are symmetric functions in the variables :5”. Definition 2.3.3. Let A = (A1, A2, . . . , An) be a partition and A = {1,1,2,2,...,n,n,...,oo} a totally ordered set with 1 < l < 2 < 2 < . - ' < n < n < .. - < 00. A semi-standard A-tableau T with entries from A is called an so—tableau if a) all entries in row i are larger than or equal to i; b) on any row, the symbol 00 appears at most once. The weight of an so-tableau T is defined as the weight of the sp—tableau obtained from T by deleting the symbol 00 if it appears. In Figure 2.3.2 T is a so—(4,2,2)-tableau with weight 37 = xflxgsra 2 210°] carom—H M Figure 2.3.2 48 Definition 2.3.4. Let A be a partition. The so—Schur function corresponding to A is soA(;i:i1) = Z :cT T where T varies over all so—A-tableaux and in” = mil U {1}. The Jacobi-Trudi identities are polynomial expressions for the character s,\ of the polynomial representation of the general linear group GL(n). There are similar identities for the characters 3p; and so; of the polynomial representations of the symplectic group sp(2n) and orthogonal group so(2n + 1), respectively, which are due to Weyl [We 46]. These formulae are 1 (23.1) 8PA($i1) = 5 det(h,\.-i-j+2(93i1) + hA,_,-+,-(x*1)) and (232) 30A(itil) = det(h,\..-,-_j(.i:il) + hAi_.°+j(iIil)) where both are l(A) by l(A) determinants and hk(:r*1) is the complete homogeneous symmetric function on 2:”. Note the resemblance between the identity (2.2.6) in Theorem 2.2.7 and (2.3.1). We are attempting to prove (2.3.1) using the lattice path approach as in Theorem 2.2.1. In our attempt we have discovered that there may be a relationship between the Gessel-Viennot technique and Schiitzenberger’s jeu de taquin (or “teasing game”) [Scii 76]. An account of Schiitzenberger’s jeu de taquin can also be found in Sagan [Sa 90,Sa 91]. Okada [0k um] recently gave a combinatorial proof of these formulae using lattice paths, but introducing some dummy variables. In his proof the relationship between lattice paths and tableaux is not as clear as it could be following our approach. Chapter 3 Open Problem 3. 1 Circulants Definition 3.1.1 A circulant determinant, C, is an n by n determinant where the (i + 1)“ row is obtained by rotating the i‘h row one place to the right. Thus (lo 01 ' ’ ° art—2 an—l an—l (10 ° ' ’ an-3 ail-2 02 a3 ' ' ° do a; 01 a2 ‘ ° ' art—1 ao Let p(x) = a0 + ala: + + a,,_.1:1:"‘l be a polynomial having as coefficients the values from the entries of the first row of C and let r be a generator for the group of the n“ roots of unity. It is well known [Led 87] that C = P(1)P(") - °-P(""'1)~ That is (3.1.1) C = (a0 + a1 + - -- + an_1)(ao + alr + - - - + an_1r"‘l) - ~- (00 + 01(7‘n_1)+---+ an—1(7‘n—1)n-1) Consider the right hand side of (3.1.1). We call p(rk’l) the kth factor. From left to right, label the n summands in the let" factor, 1 S k S n, with the numbers 49 50 k, k + 1, . . . , n, l, . . . , k — 1. With this labeling the coefficient of the term labeled j in the k‘h factor is the entry of C in the k” row and jth column. Let f be a function from {1,2,. . . ,n} to itself. If f(q) = s, then from the qth factor we choose the summand labeled with 3. Thus, the product in (3.1.1) can be regarded as a sum of weights of functions f from a set with n elements to itself where the weight of a function f is the product of the summands picked by the function from each of the factors. We will visualize functions and their weights using graphs as explained next. Definition 3.1.2 Let V be a set and let A be a set of ordered pairs of elements from V. The set V will be called the set of vertices (or nodes) and A the set of arcs or directed edges, where loops are allowed. The pair (V, A) is called a digraph or directed graph. Usually we represent a digraph by a diagram where the vertices are indicated by nodes and the directed edge (u,v) is represented by an arrow heading from u to v. We say that u is the starting point and v the ending point of the directed edge (u,v). For the digraph shown in Figure 3.1.1 we have that V = {l,2,3,4} and A = {(1, 4))(2a4)9(31 3)7(4i1)} & '6) Figure 3.1.1 A digraph is of outdegree one if each node is the starting point of only one directed 51 edge. We are interested in digraphs of this type since they represent functions from a set with n elements to itself. Given a digraph G with n vertices we label them 1,. . . ,n in a clockwise manner after we select the vertex with the label zero. The graph in Figure 3.1.1 shows this type of labeling. With this assignment of labels we think of the i“ node of G as being associated with the root ri'l. Definition 3.1.3 Let G be an outdegree one digraph and denote the edge with starting point i and ending point j by e;,-. We define the weight of e5,- as where j — i is taken modulo n. The weight of G is defined as w(G) = H we.) i=1 which we also write as 10(G) = H aj_.'T(i-l)(j—i) (M) where (i, j) indicates a directed edge. As an example, Figure 3.1.1 shows a digraph G where w(eu) = a3, w(e24) = a2r2, w(e33) = a0 and w(e41) = a1r3. So, w(G) = (a3)(a2r2)(ao)(a1r3) = 000102037‘. Let G be an outdegree one digraph. With the edge egj E G we associate the number t,-, where t.- E j -i mod n and 0 S t,- < n. Hence, with digraph G is associated a unique n-tuple (t1, . . . , tn) where t.- is the number associated with 65,- 6 G. Conversely, each n-tuple (t1, . . . ,tn) with O S t.- < n uniquely determines a digraph G. To see this we take as e:,- 6 G the edge with starting point i and ending point j, where t,- +i E j mod n with 1 S j S n. This allows us to identify outdegree one digraphs 52 on n vertices with n-tuples of non-negative integers less than n. Note that if tk is in the n-tuple of non—negative integers associated with the digraph G, then the weight of the edge ck,- has at, as a factor on its weight. Thus, two edges with the same value tk associated with them, contain the same factor of (1;. So, we have proved the next lemma. Lemma 3.1.4 Let G be a digraph associated with the n-tuple (t1,.. . ,tn). If G’ is another digraph associated with an n-tuple which is a rearrangement of (t1, . . .,t,,) then the a ’s participating in the weights ofG and G’ are the same. E] For instance, the digraph associated with (1,0,0,2) has 01000002 as the a’s and (r°)1(r1)°(r2)°(r3)2 = r2 as the r’s in its weight. The digraph associated with (0,1,2,0) has 00010200 as the a’s and has (r°)°(r1)‘(r2)2(r3)° = r as the r’s in its weight. Observe that the powers of r associated with two n-tuples which have the same set of values may be distinct. Definition 3.1.5 Let (t1, . . . ,tn) be the n-tuple associated with the digraph G. We define the ratio of G or ratio of the n-tuple by RC = Ztg. i=1 Let (t1,. . .,t,.) be the n-tuple associated with G and consider a = (1,2,. . . ,n) E S... We define an action of the cyclic group generated by a on digraphs the following way (3.1.2) 0'"(G) = G’ O S k < n where G’ is the digraph associated with the n-tuple (tn_k+1, tn_k+2, . . . , t1, . . . , tn-k). Note that the lc‘h position in the n-tuple is occupied by t1. We say that G’ is a k“ rotation of G. 53 The next lemma relates the weights of digraphs wich are in the orbit of G under the action defined in (3.1.2). Lemma 3.1.6 IfG’ is the k’h rotation ofG then w(G') = w(G)("R)'c where R = RC is as in Definition 3.1.5. Proof: Let (t1, . . . , tn) be the n-tuple associated with G. Since the ag’s in the weights of G and G’ are the same, it suffices to concentrate on the powers of r. The power of r in the weight of G is (r0)"(r2)t1 ---(r"’1)‘". Its exponent is XXL-1U — 1)t;. On the other hand, the power of r in the weight of G’ is (r0)t,,_k+1 (r1)t""‘+2 . . . (rk—1)tn(rk)t1(rk+l)t2 . . . (Tn)t""". Its exponent is ELI“: + (i — l))t.~, where k + (i — l) is taken modulo n. The relation between the exponents of r is 20: +(i—1))t.- = kR + Z(i-1)t.- i=1 i=1 and the lemma follows. C] Given an n-tuple (t1, . . . , tn) associated with a digraph G we interpret the entry t.- as the number of nodes we have to move clockwise from the i"‘ node to reach the end point of the directed edge with initial point at that node. If the digraph G represents a bijection, then it is composed of cycles. Also, the sum of the t,’s corresponding to the edges in a cycle is a multiple of n. So we have proved the following result. Lemma 3.1.7 If (t1,.. .,t,.) is the n-tuple associated with a digraph G representing a permutation then n|2?=1 t,- = R. C] 54 By Lemma 3.1.7, if R is not a multiple of n then the digraph does not represent a bijection. However, if R is a multiple of n it does not imply that G represents a bijection. For instance, the graph corresponding to (1,4,3,],1), as shown in Figure 3.1.2, has ratio R = 10 and does not represent a permutation. In the graph, the numbers next to the edges are the entries of the n-tuple associated with the digraph. l ,.:.2 / R 5 3 X 4 Figure 3.1.2 The next theorem allows us to reduce the right hand side of (3.1.1) to a sum associated with n-tuples whose ratio is a multiple of n. We consider the n-tuple (t1, . . . , tn) as a circular word. The degree I of the n-tuple is the number of elements in the orbit of that n-tuple under circular permutation. In terms of graphs, the degree I represents the number of digraphs in the orbit of G under the action defined in (3.1.2). Theorem 3.1.8 Let G be an outdegree one digraph associated with the n-tuple (t1,...,t,,) of degree I. Ifn‘f R0 then 2 w(G’) = 0 G! where G’ varies over all digraphs in the orbit ofG under the action defined in (3.1.2). Proof: Note that (t1, . . . ,tn) has % identical blocks each of length I. If the sum of the entries in one of the blocks is t then RC; = %t. Thus (r3)’ = r"t = 1 and so 55 1 — (rRG)’ = 0. Also, since 12‘ R0 we have that r30 7‘. 1. By Lemma 3.1.6, and the fact that the orbit of G has I digraphs we have that wa’) = w(G)(1+(r’*°‘)+(r’*0)2 + ' - - + (rRGY‘l) GI 1 — (rRG')l l — r3 w(G) =O.D Lemma 3.1.9 Let G be an outdegree one digraph associated with the n-tuple (t1,...,t,,) ofdegree I. IntRG then 2 w(G’) = [w(G) G, where G’ varies over all digraphs in the orbit ofG under the action defined in (3.1.2). Proof: Since r30 = l, the result follows from gwm’) = w(G)(1+(r“")+(r“")2 + - - - + (”26)“). D Conjecture: We know each digraph corresponding to a permutation a contributes (—1)"a,(1)-1a,(2)_2 - - - a,(,,)_,, to the determinant. Since on the product side the terms corresponding to digraphs with weight not a multiple of n cancel, we can partition the terms corresponding to digraphs with weight a multiple of n in a natural manner such that a) Each subset of the partition has the weight of a digraph corresponding to a unique permutation a. b) The sum of the weights on the subset is (—1)"aa(1)_1a,(2)_2 - - - a,(,,)_,,. 56 Note that the term in the determinant C corresponding to a E 15'n is aa(1)—laa(2)—2 ' ' ' aa(n)—n9 where 0‘(i) — i is taken modulo n and 0 S 0(i) —i < n. Now we will show that the conjecture is true for the case of transpositions. Let a = (i, j), i < j, be a transposition on Sn, and let G be the outdegree one digraph representing a. The n-tuple associated with G is (0, . . . ,j — i,0, . . . ,i — j,0, . . . ,0), where j — i and i - j are in the ith and j“ entries, respectively. We fix the it" entry and make i — j occupy each of the remaining n — 1 positions, to obtain n — l n-tuples which are associated with digraphs in different orbits. All these digraphs have the same factors of a.- in their weights, namely aoao - - -a,-_.- - - -a.-_,- - . - a0 which can be written as a,(1)_1aa(2)_2-- .a,(,,)_,,. If we call G}. the digraph associated with the n-tuple having j —i in the ith entry and i— j in the let" entry, 1 S k S n, k 7t i, then the power of r in its weight is (r"‘)j“(r"'1)"j. With this setup we prove the next result. Lemma 3.1.10 Ifa is a transposition in Sn and G is the outdegree one digraph representing it then 2 w(Gk) : _aa(1)—laa(2)-2 ° ' ° aa(n)-n 7.31 where the G, is as defined previously. Proof: Note that r‘j“l+("j) = 1 and 22:1(rk'1)"j = 0. Hence, it 2““le = aa(1)_1aa(2)_2---a,(,,)_,, 2(r5-1)i-i(rk—1)i-j ks] has] us kg“ = “0(1)-iaa(2)-2 - - - (1...)-.. (2(r‘-‘)j-‘(r*-1)‘-J‘ - (r‘-‘)“-"+<‘-“) k=1 = -Ga(1)—10a(2)—2'"aa(n)—n- U 57 We expect to carry on this construction for all the subsets of digraphs where two of them are in different orbit and exactly one represents a permutation. Bibliography [B-W 92] D.M. Bressoud and Shi-Yuan Wei, “Determinantal Formulae for Com- plete Symmetric Functions,” J. of Combin. Theory Series A 60 (1992), 277-286. [Ges um] I. Gessel, “Determinants and plane partitions,” unpublished manuscript. [G-V 85] I. Gessel and G. Viennot, “Binomial determinants, paths, and hook- length formulae,” Adv. in Math. 58 (1985), 300-321. [G-V ip] I. Gessel and G. Viennot, “Determinants, paths, and plane partitions,” in preparation. [Jac 41] C. Jacobi, “De functionibus alternantibus earumque divisione per pro- ductum e differentiis elementorum conflatum,” J. Reine Angew. Math. (Crelle) 22 (1841), 360—371. Also in Mathematische Werke, Vol. 3, Chelsea, New York, NY, 1969, 439-452. [Knu 70] DE. Knuth, “Permutations, matrices and generalized Young tableaux,” Pacific J. Math. 34 (1970), 709-727. [Led 77] W. Ledermann, Introduction to Group Characters, Cambridge University Press, Cambridge, 1977. [Mac 79] LG. Macdonald, Symmetric Functions and Hall polynomials, Oxford University Press, Oxford, 1979. 58 59 [Ok um] S. Okada, “Lattice Path Method and Characters of Classical Groups,” [Sa 90] [Sa 91] [Scii 76] [Tru 64] [We 46] unpublished manuscript. B.E. Sagan, “The Ubiquitious Young Tableau,” The IMA Vol. in Math. and Its App. 19 (1990), 262-298. B.E. Sagan, The Symmetric Group, Brooks/ Cole Publishing Company, Pacific Grove, California, 1991. MP. Schfitzenberger, “La correspondence de Robinson,” in Combina- toire et Representation du Groupe Syme’trique, D. Foata ed., Lecture Notes in Math., Vol. 579, Springer-Verlag, New York, NY, 1977, 59-135. N. Trudi, “Intorno un determinante piu generale di quello che suol dirsi determinante delle radici di una equazione, ed alle funzioni simmetriche complete di queste radici,” Rend. Acad. Sci. F is. Mat. Napoli 3 (1864), 121-134. Also in Giornale di Mat. 2 (1864), 152-158 and 180-186. H. Weyl, The Classical Groups, Their Invariants and Representations, 2”“ ed., Princeton Univ. Press, Princeton, NJ, 1946. HICHIGQN STATE UNIV. LIBRRRIES [IHI[Ill[ll[IlHllllllllllllllllllllllllllll[[INHlllHI 31293009045786