1 A combinatorial interpretation of the inverse t-

1Acombinatorialinterpretationoftheinverset-KostkamatrixJoaquinO.CarbonaraMathematicsDepartment,BI304StateUniversityofNewYork’sCollegeatBualo1300ElmwoodAv.BualoNY14222-1095Inthispaperweusetournamentmatricestogiveacombinatorialinterpretationfortheentriesoftheinverset-Kostkamatrix,whichisthetransitionmatrixbetweentheHall-Littlewoodpolyno-mialsandtheSchurfunctions.0.1IntroductionIntherstsectionofthispaperweintroducesomebasicnotationabouttournamentmatrices,andproveatheoremthatiscrucialinthesecondsection.Inthesecondsectionweprovethattheentriesoftheinverset-Kostkamatrixcanbeinterpretedcombinatoriallyasaweightedsumoverasubsetoftournamentmatrices,whichwecallSpecialTournamentMatrices.Wereferthereaderto([Mac])foranintroductiontoSymmetricfunctionsandtheirq-analogs.TheninthethirdsectionwerelateSpecialRimHookTabloids,whichwereintroducedbyEgeciogluandRemmeltointerprettheinverseKostkamatrix(see[E-R1]),andSpecialTournamentMatrices.Inthefourthsectionweexploitthecombinatorialdenitionjustdevelopedtoobtainmoredirectwaystoobtainsomeentriesoftheinverset-Kostkamatrix.AppendixAsurveystheconnectionamongbubblediagrams(developedbyChen-Garsia-RemmeltodescribetheplethysmSn[Sm])(see[C-G-R]),SpecialRimHookTabloids,andSpecialTournamentMatrices.AppendixBlistssomeconjecturesandtablesofvaluesfortheinverset-Kostkamatrix.0.2TournamentMatricesInthissectionweshallstatesomepreliminaryresultsabouttournamentmatrices.Thereaderisreferredto([Moon])foramorecompleteintroductiontoTournamentMatrices.Denition1ATournamentMatrixisannmatrix(mij)withentriesfromthesetf0,1gsuchthattheentriesinthemaindiagonalareall0mij+mji=1fori6=j;1i;jn.2Example1TheTournamentMatricesofsize3are011001000!,011000010!,010001100!,010000110!,001101000!,001100010!,000101100!,000100110!.TournamentMatricesofsizen(we’lldenotethissetn)willbeusedtodescribethetransitionmatrixbetweenthesetofHall-LittlewoodpolynomialsfP:‘ngandthesetofSchurfunctionsfs:‘ng,twoorderedbasesfor(t)(see[Mac]).Thispointofviewgivesrisetosomeexitingcombinatorialquestions,someofwhicharestillopen.Denition2Letm=(mij)2n.Thet-weight!ofmisdenedasfollows.!(m;t)=Yij(t)mijThegeneratingfunctionfortheweightsofnisY1ijn(xitxj):(1)Notethatinexpandingtheproduct,xiandxjare\competingtobeselected,andtheonethatisselectedissaidtohavewonthegame.Aparticularsummandintheexpansionof(1)istheequivalentofatournament,i.e.asetofgameswhereeachplayerplayseachotherplayerexactlyonce.Givenasummandxi11xi22xissfrom(1),thesequenceofpowers(i1;i2;:::;is)canbeviewedasavector,whichwecallthescorevectorsincethepowerofavariablexishowsthenumberoftimesxiwasselected.Thescorevectorcorrespondstothesequenceofrowsumsintheincidencematrixm,andwedenoteitbys(m).Example2Lets=3.ThenY1ijn(xitxj)=(x1tx2)(x1tx3)(x2tx3)=x1x1x2+(t)(x1x1x3)+(t)(x1x3x2)+:::+(t)3(x2x3x3)=!(011001000!)xs(011001000!)+!(011000010!)xs(011000010!)+!(010001100!)xs(010001100!)+:::+!(000100110!)xs(000100110!)3=x(2;1;0)+(t)x(2;0;1)+(t)x(1;1;1)+:::+(t)3x(0;1;2)respectively,wherex(a;b;c)xa1xb2xc3.Lemma1Letm2n.Thescorevectorofmisapermutationof(0,1,...,n-1)imij=1andmjk=1implythatmik=1for1i;j;kn.Inthiscasewesaythatmisatransitivetournamentmatrix.Thesetoftransitivetournamentmatriceswillbedenotedtn.Proof:Supposethescorevectorofmisapermutationof(0,1,...,n-1).Selecttherowthathasrowsum(n-1)|sayitisrowk1|itmustbelledwith1’sexceptonthediagonal.Thismeansthatmk1x=1ix6=k1.Selectnowtherowthathasrowsumn2,sayitisrowk2,andobservethatitmustbelledwith1’sexceptonthediagonalandoncolumnk1,becausemk1;k2=1impliesthatmk2;k1=0.Thismeansthatmk2;x=1forallrowsxthathaverowsumsmallerthattherowsumofrowk2.Byusinganeasyinductionargument,weseethatmkr;ks=1itherowsumofrowkrtherowsumofrowks.Thereforeweobtainthetransitiveconditionmij=1&mjk=1)mik=1.Ifwenowassumethetransitiveconditionandassumemij=1,thenforeachcasewheremjx=1wemustconcludethatalsomix=1(1xn).Sinceweassumemij=1,therowsumofrowiisstriclygreaterthantherowsumofrowj.Sincefortournamentmatriceseithermij=1ormji=1,allrowswillhavedierentrowsum.Lettherowkbemaximal,i.e.mkx=1fork6=x.Thentherowsumofrowkisn1,andbyinductionweeasilyconcludethatthescorevectorofmisapermutationof(0,1,2,3,...,n-1).Corollary11)Thereisabijectionbetweenm2tnandtheSymmetricgroupSn,wheremintncorrespondstothepermutation(m1;m2;:::;mn),withmni+1=f(ithrowsumofm)+1g.2)Pm2tn!(m;1)xs(m)=Pm2n!(m;1)xs(m).Therefore,Y1ijs(xixj)=detkxnjik(2)usuallycalledtheVandermondedeterminant.Proof:1)ThisfollowsdirectlyfromtheproofofLemma1.2)ItiseasytoseethatXm2nmnontransitive!(m;1)=0:4Onewaytoprovethisisbydeningasignreversinginvolutionasfollows.Let(r;t)betheleastpair(inlexicographicorder)ofrepeatedentriesinthescorevectorofminn.ThenmcancelswiththeTournamentMatrix^m=(m(i)(j)),whereisthepermutation(rt),incyclenotation.Thisprovestherstidentityin2).TheVandermondedeterminantformulafollowsbyusingthegeneratingfunction(1)andpart1)ofthiscorollary.Lemma2Themapdenedaboveisasign-preservingbijectionbetweentnandSn,thesym-metricgroup,whereforany2Sn,sign()=(1)inv().Letm(m).Furthermo