Type-II Matrices and Combinatorial Structures

arXiv:0707.1836v1[math.CO]12Jul2007Type-IIMatricesandCombinatorialStructuresAdaChanandChrisGodsilFebruary5,2008AbstractType-IImatricesareaclassofmatricesusedbyJonesinhisworkonspinmodels.Inthispaperweshowthattype-IImatricesarisenaturallyinconnectionwithsomeinterestingcombinatorialandgeo-metricstructures.1IntroductionIfMandNarematricesofthesameorder,theirSchurproductisthematrixM◦N,definedbythecondition(M◦N)i,j=Mi,jNi,j.TheSchurproductiscommutativeandassociative,withanidentityelementJ,theall-onesmatrix.IfM◦N=JwesaythatNistheSchurinverseofM,anddenoteitM(−).Atype-IImatrixisaSchurinvertiblen×nmatrixWoverCsuchthatWW(−)T=nI.ThisconditionimpliesthatW−1existsandW(−)T=nW−1.In[6]Jonesshowedthatcertainspecialtype-IImatricescouldbeusedtoconstructso-calledspinmodels,whichcouldinturnbeusedtoconstruct1interestinginvariantsofknotsandlinks(includingtheJonespolynomial).Themaingoalofthispaperistoshowthattype-IImatricesaremuchmorecommonthanmightbeexpected:inparticulartheyariseinconnectionwitharangeofcombinatorialandgeometricstructures:symmetricdesigns,setsofequiangularlinesandstronglyregulargraphs.2TheBasicsWeoffersomeexamplesoftype-IImatrices.First111−1isasymmetrictype-IImatrix.Ifωisaprimitivecuberootofunitythen11ωω111ω1isalsotype-II.Foranynon-zerocomplexnumbert,thematrixW=111111−1−11−1t−t1−1−ttistype-II.NextwehavethePottsmodels:ifWisn×nandW=(t−1)I+J,thenWW(−)T=((t−1)I+J)((t−1−1)I+J)=((2−t−t−1)I+(n−2+t+t−1)J,whenceitfollowsthatWistype-IIwhenever2−t−t−1=n,i.e.,whenevertisarootofthequadratict2+(n−2)t+1.2Asthefirstexamplesuggests,anyHadamardmatrixisatype-IImatrix,anditisnotunreasonabletoviewtype-IImatricesasageneralisationofHadamardmatrices.TheKroneckerproductoftwotype-IImatricesisatype-IImatrix;thisprovidesanothereasywaytoincreasethesupplyofexamples.Recallthatamonomialmatrixistheproductofapermutationmatrixandadiagonalmatrix.ItisstraighforwardtoverifythatifWistype-IIandMandNareinvertiblemonomialmatrices,thenMWNistype-II.WesayW′isequivalenttoWifW′=MWN,whereMandNareinvertiblemonomialmatrices.ThetransposeWTisalsotype-II,asisW(−),butthesematricesmaynotbeequivalenttoW.Itwouldbeausefulexercisetoprovethatany2×2type-IImatrixisequivalenttothefirstexampleabove,any3×3type-IImatrixisequivalenttothesecond,andany4×4type-IImatrixisequivalenttoamatrixinthethirdfamily.LetWbeaSchur-invertiblematrix,withrowsandcolumnsindexedbythesetΩ,where|Ω|=n.Letthevectorsea,a∈ΩdenotethestandardbasisforCΩ.Wedefineasetofn2vectorsinCnasfollows.Ya,b:=Wea◦W(−)eb.WecanviewYa,bastheSchurratioofthea-andb-columnsofW.TheNomuraalgebraNWofWconsistsofthesetofn×ncomplexmatricesMsuchthateachofthen2vectorsYa,bisaneigenvectorforM.TheNomuraalgebraisnon-empty,becauseitalwayscontainsI.2.1Lemma.LetWbeaSchurinvertibleandinvertiblematrix.ThenWisatype-IImatrixifandonlyifJ∈NW.Proof.LetDabethen×ndiagonalmatrixsuchthat(Da)i,i:=Wi,a.SinceWisinvertible,itscolumnsWeb,b∈Ωarelinearlyindependent.SinceDaisinvertibleandYa,b=D−1aWeb,3weseethatthevectorsYa,b,b∈ΩarelinearlyindependentandconsequentlytheyformabasisforCn.NowYa,a=1,soJ∈NWifandonlyifJYa,b=nδabYa,b,equivalentlyXrWr,aWr,b=(W(−)TW)b,a=nδb,aforalla,b∈Ω.ItfollowsthatifWisatype-IImatrixofordern×n,thenNWcontainsIandJanddimNW≥2whenn≥2.WesaythatNWistrivialifdimNW=2.Alltheworkinthispaperismotivatedbythedesiretofindtype-IImatriceswithnon-trivialNomuraalgebras.OnereasonisthatifWisatype-IImatrixandW∈NW,thenwemayuseWtoconstructalinkinvariant.ThePottsmodel,whichwementionedabove,hasthispropertyandthecorrespondinglinkinvariantsareevaluationsoftheJonespolynomial.Formoreonthisconnection,see[5]and[4].Atype-IImatrixWsuchthatW∈NWisknownasaspinmodel.ThePottsmodelaside,veryfewinterestingspinmodelsareknown.IfWisaspinmodelotherthanthePottsmodel,thenNWcontainsI,JandW,andthereforedimNW≥3.Spinmodelshaveprovedverydifficulttofind.Henceweareleadtosearchfortype-IImatriceswhoseNomuraalgebrasarenon-trivial.Forreasonsthatarenotatallclear,eventheseseemtobescarce.Thepreviousdiscussionglossesoveronepoint.IfW1andW2aretype-IImatrices,thentheNomuraalgebraofW1⊗W2isthetensorproductoftheNomuraalgebrasofW1andW2.Sincedim(NW1⊗W2)=dim(NW1)dim(NW2),theNomuraalgebraofW1⊗W2isalwaysnon-trivial.Howeverthecorre-spondinglinkinvariantsareofnointerest,sincetheyarebuiltinanobviouswayfromtheinvariantsbelongingtothefactors.Thereforeoursearchisac-tuallyfortype-IImatriceswhichhavenon-trivialNomuraalgebraandwhicharenotequivalenttoKroneckerproductsoftype-IImatrices.43NomuraAlgebrasWehaveintroducedtype-IImatricesandtheirNomuraalgebras.Nowwedescribetheconnectionbetweentype-IImatricesandcombinatorics;thecon-nectionismediatedbyassociationschemes.LetWbeatype-IImatrixorordern×n.WesawintheprevioussectionthatYa,b,b∈ΩformabasisforCn.IfM∈NW,thenthematrixrepresentingMrelativetothisbasisisdiagonal,fromwhichweconcludethatifM,N∈NWthenMN=NM.Inotherwords,theNomuraalgebraofatype-IImatrixiscommutative.WewillalsoseethatitisclosedundertheSchurproduct.LetWbeatype-IImatrix,withrowsandcolumnsindexedbythesetΩ,where|Ω|=n.IfM∈NW,thereisann×nmatrixΘW(M)suchthatMYa,b=(ΘW(M))a,bYa,b.WecallΘW(M)thematrixofeigenvaluesofM.(Whenn