On some properties of contracting matrices

arXiv:math/0604457v1[math.DS]20Apr2006OnsomepropertiesofcontractingmatricesChaiWahWuIBMResearchDivision,ThomasJ.WatsonResearchCenterP.O.Box218,YorktownHeights,NY10598,U.S.A.AbstractTheconceptsofparacontracting,pseudocontractingandnonexpandingoperatorshavebeenshowntobeusefulinprovingconvergenceofasynchronousorparallelit-erationalgorithms.Thepurposeofthispaperistogivecharacterizationsoftheseop-eratorswhentheyarelinearandfinite-dimensional.Firstweshowthatpseudocon-tractivityofstochasticmatriceswithrespecttok·k∞isequivalenttothescramblingproperty,aconceptfirstintroducedinthestudyofinhomogeneousMarkovchains.Thisunifiesresultsobtainedindependentlyusingdifferentapproaches.Secondly,wegeneralizetheconceptofpseudocontractivitytoset-contractivitywhichisausefulgeneralizationwithrespecttotheEuclideannorm.Inparticular,wedemonstratenon-Hermitianmatricesthatareset-contractivefork·k2,butnotpseudocontractivefork·k2ork·k∞.Forconstantrowsummatriceswecharacterizeset-contractivityusingmatrixnormsandmatrixgraphs.Furthermore,weproveconvergenceresultsincompositionsofset-contractiveoperatorsandillustratethedifferencesbetweenset-contractivityindifferentnorms.Finally,wegiveanapplicationtotheglobalsynchronizationincoupledmaplattices.Keywords:coupledmaplattice,Markovchains,nonexpandingoperators,paracontractiveoperators,pseudocontractiveoperators,scramblingmatrices,stochasticmatrices,synchronization.1IntroductionDefinition1([1])Letk·kbeavectornorminCn.AnnbynmatrixBisnonexpansivewithrespecttok·kif∀x∈Cn,kBxk≤kxk(1)Emailaddress:[e-mail](ChaiWahWu).PreprintsubmittedtoElsevierScience2February2008Biscalledparacontractingwithrespecttok·kif∀x∈Cn,Bx6=x⇔kBxkkxk(2)Itiseasytoseethatnormalmatriceswitheigenvaluesintheunitcircleandforwhich1istheonlyeigenvalueofunitnormisparacontractivewithrespecttok·k2.Definition2Foravectorx∈CnandaclosedsetX∗,y∗iscalledaprojec-tionvectorofxontoX∗ify∗∈X∗andkx−y∗k=miny∈X∗kx−ykThedistanceofxtoX∗isdefinedasd(x,X∗)=kx−P(x)kwhereP(x)isaprojectionvectorofxontoX∗.Eventhoughtheprojectionvectorisnotnecessarilyunique,wewriteP(x)whenitisclearwhichprojectionvectorwemeanorwhenthechoiceisim-material.Letusdenotee=(1,···,1)T.TheproofofthefollowingLemmaisrelativelystraightforwardandthusomitted.Lemma1Ifx∈RnandX∗={αe:α∈R},theprojectionvectorP(x)ofxontoX∗isαewhere:•forthenormk·k2,α=1nPixiandd(x,X∗)=qPi(xi−α)2.•forthenormk·k∞,α=12(maxixi+minixi),andd(x,X∗)=12(maxixi−minixi).•forthenormk·k1,d(x,X∗)=Pni=⌈n2⌉+1ˆxi−P⌊n2⌋i=1ˆxiand·fornodd,α=ˆx⌈n2⌉.·forneven,αcanbechosentobeanynumberintheinterval[ˆxn2,ˆxn2+1].Hereˆxiarethevaluesxirearrangedinnondecreasingorderˆx1≤ˆx2≤···.Thepropertyofparacontractivityisusedtoshowconvergenceofinfiniteprod-uctsofparacontractivematricesandthisinturnisusedtoproveconvergenceinvariousparallelandasynchronousiterationmethods[2].In[3]thispropertyisgeneralizedtopseudocontractivity.Definition3([3])LetTbeanoperatoronRn.Tisnonexpansivewithre-specttok·kandaclosedsetX∗if∀x∈Rn,x∗∈X∗,kTx−x∗k≤kx−x∗k(3)Tispseudocontractivewithrespecttok·kandX∗ifitisnonexpansivewithrespecttok·kandX∗and∀x6∈X∗,d(Tx,X∗)d(x,X∗)(4)2Ref.[3]showsthattherearepseudocontractivenonnegativematriceswhicharenotparacontractivewithrespecttok·k∞andprovesaresultontheconvergenceofinfiniteproductsofpseudocontractivematrices.Furthermore,Ref.[3]studiesaclassofmatricesforwhichafiniteproductofmatricesfromthisclassoflengthatleastn−1ispseudocontractiveink·k∞.Thepurposeofthispaperismultifold.Firstweshowthatforstochasticmatri-ceswithrespecttok·k∞andX∗={αe:α∈R},pseudocontractivematricesareequivalenttoscramblingmatricesandthusaresimplycharacterized.Theconceptofscramblingmatricesisfirstintroducedinthestudyofweakergod-icityininhomogeneousMarkovchainsandthisequivalenceallowsustounifyseveralresultsobtainedindependentlyusingthesedifferentconcepts.Thesecondgoalofthispaperistogeneralizepseudocontractivitybyintro-ducingtheconceptofset-contractivity.Weproveaconvergenceresultofset-contractivematricesandshowexistenceofset-contractivematricesink·k2thatarenotpseudocontractivewithrespecttok·k2ork·k∞.Westudyset-contractionwithrespecttok·k2intermsofmatrixnormsandgraphsofmatrices.Finally,weapplytheseresultstotheglobalsynchronizationofcoupledmaplattices.WeconcentrateonthecasewhereTarematricesandX∗isthespanofthecorrespondingPerroneigenvector.IfthePerroneigenvectorisstrictlypositive,thenasin[3],ascalingoperationT→W−1TWwhereWisthediagonalmatrixwiththePerroneigenvectoronthediagonal,transformsTintoamatrixforwhichthePerroneigenvectorise.ThereforeinthesequelwewillfocusonconstantrowsummatriceswithX∗={αe:α∈R}.2PseudocontractivityandscramblingstochasticmatricesScramblingmatriceswerefirstdefinedin[4]tostudyweakergodicityofinho-mogeneousMarkovchains.Definition4AmatrixAisscramblingifforanypairofindicesi,j,thereexistsksuchthatAik6=0andAjk6=0.Definition5ForarealmatrixA,μ(A)isdefinedasμ(A)=minj,kXimin(Aji,Aki)3Fornonnegativematriceswithrowsums≤r,itisclearthat0≤μ(A)≤rwithμ(A)0ifandonlyifAisscrambling.Definition6ForarealmatrixA,defineδ(A)≥0asδ(A)=maxi,jXkmax(0,Aik−Ajk)≥maxi,j,k(Aik−Ajk)IfAhasconstantrowsums,thenδ(A)=