Further-results-for-Perron-Frobenius-theorem-for-n

SIAMJ.MATRIXANAL.APPL.c2010SocietyforIndustrialandAppliedMathematicsVol.31,No.5,pp.2517–2530FURTHERRESULTSFORPERRON–FROBENIUSTHEOREMFORNONNEGATIVETENSORS∗YUNINGYANG†ANDQINGZHIYANG‡Abstract.WegivefurtherresultsonthePerron–Frobeniustheoremfortensors,generalizeothertheoremsfrommatricestotensors,andgiveanequivalentconditionfornonnegativeirreducibletensors.Keywords.nonnegativetensor,Perron–Frobeniustheorem,KyFantheorem,maxminproblemAMSsubjectclassifications.74B99,15A18,15A69DOI.10.1137/0907787661.Introduction.ThePerron–Frobeniustheoremisafundamentalresultfornonnegativematrices.Ithasbeenwidelyusednotonlyinmathematicsbutalsoinvariousfieldsofscienceandtechnology,suchaseconomics,operationalresearch,andpagerankintheinternet;formoreinformation,see[2,4,9,10].Chang,Pearson,andZhanggeneralizedthistheoremtotheclassofnonnegativetensorsrecently[1].ThePerron–Frobeniustheoremfornonnegativetensorsisrelatedtomeasuringhigherorderconnectivityinlinkedobjects[5]andhypergraphs[6].Ng,Qi,andZhougaveamethodtofindthelargesteigenvalueofanonnegativetensor[11]basedonsomeresultsof[1].Inthispaper,wewillgivefurtherresultsforthePerron–Frobeniustheoremfornonnegativetensorsandsomeotherresultsgeneralizedfromnonnegativematrices.Thispaperisorganizedasfollows.Insection2,werecallsomedefinitionsandthePerron–Frobeniustheoremgivenin[1]andproposeourmainresults.Wegivetheproofofmainresultsinsection3.Insection4,wegeneralizetheKyFantheoremfrommatricestotensors.Insection5,wediscussthemaxminproblemsfornonnegativetensors.Weproposeanequivalentconditionofnonnegativeirreducibletensorsinsection6.Wefirstaddacommentonthenotationthatisused.Vectorsarewrittenasitaliclowercaseletters(x,y,...),matricescorrespondtoitaliccapitals(A,B,...),andtensorsarewrittenascalligraphiccapitals(A,B,...).TheentrywithrowindexiandcolumnindexjinamatrixA,i.e.,(A)ij,issymbolizedbyaij(also(A)i1···im=ai1···im).Thesymbol|·|usedonamatrixA(ortensorA)meansthat(|A|)ij=|aij|(or(|A|)i1···im=|ai1···im|),andwhenitisusedonasetI,itdenotesthenumberofelementsinI.Rn+(Rn++)denotesthecone{x∈Rn|xi≥()0,i=1,...,n}.Cndenotesthendimensioncomplexfield.Wecallanordermdimensionntensortheunittensorifitsentriesareδi1···imfori1,...,im=1,whereδi1···im=1ifand∗ReceivedbytheeditorsNovember28,2009;acceptedforpublication(inrevisedform)byL.DeLathauwerJune1,2010;publishedelectronicallyAugust31,2010.ThisworkwassupportedbytheNationalNaturalScienceFoundationofChinagrant10871105,theKeygrantProjectofChineseMinistryofEducation(309009),andtheScientificResearchFoundationfortheReturnedOverseasChineseScholars,StateEducationMinistry.†SchoolofMathematicalSciencesandLPMC,NankaiUniversity,Tianjin300071,People’sRepublicofChina([e-mail]).‡Correspondingauthor.SchoolofMathematicalSciencesandLPMC,NankaiUniversity,Tianjin300071,People’sRepublicofChina([e-mail]).25172518YUNINGYANGANDQINGZHIYANGonlyifi1=···=im,anddenoteitbyI.ThesymbolA≥(,≤,)Bmeansthataij≥(,≤,)bijforeveryi,j,anditisthesamefortensors.2.Preliminaries.Firstwerecallthedefinitionoftensor:atensorisamul-tidimensionalarray,andarealordermdimensionntensorAconsistsofnmrealentries:Ai1···im∈R,whereij=1,...,nforj=1,...,m.IfthereareanumberλandanonzerovectorxthataresolutionsofthefollowinghomogeneouspolynomialequationsAxm−1=λx[m−1],thenλiscalledtheeigenvalueofAandxiscalledtheeigenvectorofAassociatedwithλ,whereAxm−1andx[m−1]arevectorswhoseithcomponentsare(Axm−1)i=ni2,...,im=1aii2···imxi2···xim(x[m−1])i=xm−1i,respectively.ThisdefinitionwasintroducedbyQiin[4]wherehesupposedthatAisanordermdimensionnsymmetrictensorandmiseven.Independently,Lim[2]gavesuchadefinitionbutrestrictedxtobearealvectorandλtobearealnumber.Hereweusethedefinitiongivenin[1].LetusrecallthePerron–Frobeniustheoremfornonnegativetensorsgivenin[1].Theorem2.1(seeTheorem1.3of[1]).IfAisanonnegativetensorofordermdimensionn,thenthereexistsλ0≥0andanonnegativevectorx0=0suchthat(2.1)Axm−10=λ0x[m−1]0.Theorem2.2(seeTheorem1.4of[1]).IfAisanirreduciblenonnegativetensorofordermdimensionn,thenthepair(λ0,x0)in(2.1)satisfiesthefollowing:(1)λ00isaneigenvalue.(2)x00;i.e.,allcomponentsofx0arepositive.(3)Ifλisaneigenvaluewithnonnegativeeigenvector,thenλ=λ0.Moreover,thenonnegativeeigenvectorisuniqueuptoamultiplicativeconstant.(4)IfλisaneigenvalueofA,then|λ|≤λ0.Andthereducibilityoftensorisdefinedasfollows.Definition2.1(reducibility;seeDefinition2.1of[1]).AtensorC=(ci1···im)ofordermdimensionniscalledreducibleifthereexistsanonemptyproperindexsubsetI⊂{1,...,n}suchthatci1···im=0foralli1∈I,foralli2,...,im∈I.IfCisnotreducible,thenwecallCirreducible.NotethatinTheorem2.1,theauthorsin[1]provedthatthereexistsapair(λ0,x0)∈Rn+1+whichistheeigenpairofanon-negativetensor.Inthispaper,wewillprovethatthespectralradiusistheeigenvalueofanonnegativetensor.FirstthespectralradiusoftensorAisdefinedasfollows.Definition2.2.ThespectralradiusoftensorAisdefinedasρ(A)=max{|λ|:λisaneigenvalueofA}.FURTHERRESULTSFORPERRON–FROBENIUSTHEOREM2519Thisdefinitionisthesameastheclassofmatrices.NotethatTheorem2.2impliesthatρ(A)=λ0isaneigenva