Lecture 17 Perron-Frobenius Theory

1 EE363 Winter 2008-09 Lecture 17 Perron-Frobenius Theory Positive and nonnegative matrices and vectors Perron-Frobenius theorems Markov chains Economic growth Population dynamics Max-min and min-max characterization Power control Linear Lyapunov functions Metzler matrices17 1 Positive and nonnegative vectors and matriceswe say a matrix or vector is positive(orelementwise positive) if all its entries are positive nonnegative(orelementwise nonnegative) if all its entries arenonnegativewe use the notationx > y(x y) to meanx yis elementwise positive(nonnegative)warning:ifAandBare square and symmetric,A Bcan mean: A Bis PSD ( ,zTAz zTBzfor allz), or A Belementwise positive ( ,Aij Bijfor alli, j)in this Lecture ,>and mean elementwisePerron- frobenius Theory17 2 Application areasnonnegative matrices arise in many fields, , economics population models graph Theory Markov chains power control in communications Lyapunov analysis of large scale systemsPerron- frobenius Theory17 3 Basic factsifA 0andz 0, then we haveAz 0conversely: if for allz 0, we haveAz 0, then we can concludeA 0in other words, matrix multiplication preserves nonnegativity if and only ifthe matrix is nonnegativeifA >0andz 0,z6= 0, thenAz >0conversely, if wheneverz 0,z6= 0, we haveAz >0, then we canconcludeA >0ifx 0andx6= 0, we refer tod= (1/1Tx)xas itsdistributionornormalized formdi=xi/(Pjxj)gives the fraction of the total ofx, given byxiPerron- frobenius Theory17 4 Regular nonnegative matricessupposeA Rn n, withA 0 Ais calledregularif for somek 1,Ak>0meaning.

2 Form directed graph on nodes1, .. , n, with an arc fromjtoiwheneverAij>0then(Ak)ij>0if and only if there is a path of lengthkfromjtoiAis regular if for somekthere is a path of lengthkfrom every node toevery other nodePerron- frobenius Theory17 5examples: any positive matrix is regular 1 10 1 and 0 11 0 are not regular 1 1 00 0 11 0 0 is regularPerron- frobenius Theory17 6 Perron-Frobenius theorem for regular matricessupposeA Rn nis nonnegative and regular, ,Ak>0for somekthen there is an eigenvalue pfofAthat is real and positive, with positiveleft and right eigenvectors for any other eigenvalue , we have| |< pf the eigenvalue pfis simple, , has multiplicity one, and correspondsto a1 1 Jordan blockthe eigenvalue pfis called thePerron- frobenius (PF) eigenvalue ofAthe associated positive (left and right) eigenvectors are calledthe (left andright) PF eigenvectors (and are unique, up to positive scaling) Perron-Frobenius Theory17 7 Perron-Frobenius theorem for nonnegative matricessupposeA Rn nandA 0then there is an eigenvalue pfofAthat is real and nonnegative, withassociated nonnegative left and right eigenvectors for any other eigenvalue ofA, we have| | pf pfis called thePerron- frobenius (PF) eigenvalue ofAthe associated nonnegative (left and right) eigenvectors are called (left andright) PF eigenvectorsin this case, they need not be unique, or positivePerron- frobenius Theory17 8 Markov chainswe consider stochastic processX0, X1.

3 With values in{1, .. , n}Prob(Xt+1=i|Xt=j) =PijPis called thetransition matrix; clearlyPij 0letpt Rnbe the distribution ofXt, ,(pt)i=Prob(Xt=i)then we havept+1=P ptnote:standard notation uses transpose ofP, and row vectors forprobability distributionsPis astochastic matrix, ,P 0and1TP=1 Tso1is a left eigenvector with eigenvalue1, which is in fact the PFeigenvalue ofPPerron- frobenius Theory17 9 Equilibrium distributionlet denote a PF (right) eigenvector ofP, with 0and1T = 1sinceP = , corresponds to aninvariant distributionorequilibriumdistributionof the Markov chainnow supposePis regular, which means for somek,Pk>0since(Pk)ijisProb(Xt+k=i|Xt=j) , this means there is positiveprobability of transitioning from any state to any other inkstepssincePis regular, there is a unique invariant distribution , which satisfies >0the eigenvalue1is simple and dominant, so we havept , no matterwhat the initial distributionp0in other words: the distribution of a regular Markov chain alwaysconvergesto the unique invariant distributionPerron- frobenius Theory17 10 Rate of convergence to equilibrium distributionrate of convergence to equilibrium distribution depends on second largesteigenvalue magnitude, , = max{| 2|.}

4 ,| n|}where iare the eigenvalues ofP, and 1= pf= 1( is sometimes called the SLEM of the Markov chain)themixing timeof the Markov chain is given byT=1log(1/ )(roughly, number of steps over which deviation from equilibriumdistribution decreases by factore) Perron-Frobenius Theory17 11 Dynamic interpretationconsiderxt+1=Axt, withA 0and regularthen by PF theorem, pfis the unique dominant eigenvalueletv, w >0be the right and left PF eigenvectors ofA, with1Tv= 1,wTv= 1then ast ,( 1pfA)t vwTfor anyx0 0,x06= 0, we have11 Txtxt vast , , the distribution ofxtconverges tovwe also have(xt+1)i/(xt)i pf, , the one-period growth factor ineach component always converges to pfPerron- frobenius Theory17 12 Economic growthwe consider an economy, with activity levelxi 0in sectori,i= 1, .. , ngiven activity levelxin periodt, in periodt+ 1we havext+1=Axt, withA 0 Aij 0means activity in sectorjdoes not decrease activity in sectori, , the activities are mutually noninhibitorywe ll assume thatAis regular, with PF eigenvalue pf, and left and rightPF eigenvectorsw, v, with1Tv= 1,wTv= 1PF theorem tells us: (xt+1)i/(xt)i, the growth factor in sectoriover the period fromttot+ 1, each converge to pfast the distribution of economic activity ( ,xnormalized) converges tovPerron- frobenius Theory17 13 asymptotically the economy exhibits (almost) balanced growth, bythefactor pf, in each sectorthese hold independent of the original economic activity, provided it isnonnegative and nonzerowhat does left PF eigenvectorwmean?

5 For largetwe havext tpfwTx0vwhere means we have dropped terms small compared to dominant termso asymptotic economic activity is scaled bywTx0in particular,wigives the relativevalueof activityiin terms of long termeconomic activityPerron- frobenius Theory17 14 Population model(xt)idenotes number of individuals in groupiat periodtgroups could be by age, location, health, marital status, dynamics is given byxt+1=Axt, withA 0 Aijgives the fraction of members of groupjthat move to groupi, or thenumber of members in groupicreated by members of groupj( , inbirths)Aij 0means the more we have in groupjin a period, the more we havein groupiin the next period ifPiAij= 1, population is preserved in transitions out of groupj we can havePiAij>1, if there are births (say) from members ofgroupj we can havePiAij<1, if there are deaths or attrition in groupjPerron- frobenius Theory17 15now supposeAis regular PF eigenvectorvgives asymptotic population distribution PF eigenvalue pfgives asymptotic growth rate (if>1) or decay rate(if<1) wTx0scales asymptotic population, sowigives relative value of initialgroupito long term populationPerron- frobenius Theory17 16 Path count in directed graphwe have directed graph onnnodes, with adjacency matrixA Rn nAij= 1there is an edge from nodejto nodei0otherwise Ak ijis number of paths fromjtoiof lengthknow supposeAis regularthen for largek,Ak kpfvwT= kpf(1Tw)v(w/1Tw)T( means: keep only dominant term)v, ware right, left PF eigenvectors, normalized as1Tv= 1,wTv= 1 Perron-Frobenius Theory17 17total number of paths of lengthk:1 TAk1 kpf(1Tw)forklarge, we have (approximately) pfis factor of increase in number of paths when length increases byone vi.

6 Fraction of lengthkpaths that end ati wj/1Tw: fraction of lengthkpaths that start atj viwj/1Tw: fraction of lengthkpaths that start atj, end ati vimeasures importance/connectedness of nodeias asink wj/1 Twmeasures importance/connectedness of nodejas asourcePerron- frobenius Theory17 18(Part of) proof of PF theorem for positive matricessupposeA >0, and consider the optimization problemmaximize subject toAx xfor somex 0, x6= 0note that we can assume1Tx= 1interpretation:withyi= (Ax)i, we can interpretyi/xias the growthfactor for componentiproblem above is to find the input distribution that maximizes theminimum growth factorlet 0be the optimal value of this problem, and letvbe an optimal point, ,v 0,v6= 0, andAv 0vPerron- frobenius Theory17 19we will show that 0is the PF eigenvalue ofA, andvis a PF eigenvectorfirst let s showAv= 0v, ,vis an eigenvector associated with 0if not, suppose that(Av)k> 0vknow let s look at v=v+ ekwe ll show that for small >0, we haveA v > 0 v, which means thatA v vfor some > 0, a contradictionfori6=kwe have(A v)i= (Av)i+Aik >(Av)i 0vi= 0 viso for any >0we have(A v)i> 0 vi(A v)k 0 vk= (Av)k+Akk 0vk 0 = (Av)k 0vk ( 0 Akk) Perron-Frobenius Theory17 20since(Av)k 0vk>0, we conclude that for small >0,(A v)k 0 vk>0to show thatv >0, suppose thatvk= 0fromAv= 0v, we conclude(Av)k= 0, which contradictsAv >0(which follows fromA >0,v 0,v6= 0)

7 Now suppose 6= 0is another eigenvalue ofA, ,Az= z, wherez6= 0let|z|denote the vector with|z|i=|zi|sinceA 0we haveA|z| |Az|=| ||z|from the definition of 0we conclude| | 0(to show strict inequality is harder) Perron-Frobenius Theory17 21 Max-min ratio characterizationproof shows that PF eigenvalue is optimal value of optimization problemmaximizemini(Ax)ixisubject tox >0and that PF eigenvectorvis optimal point: PF eigenvectorvmaximizes the minimum growth factor overcomponents with optimalv, growth factors in all components are equal (to pf)in other words: by maximizing minimum growth factor, we actually achievebalanced growthPerron- frobenius Theory17 22 Min-max ratio characterizationa related problem isminimizemaxi(Ax)ixisubject tox >0here we seek to minimize the maximum growth factor in the coordinatesthe solution is surprising: the optimal value is pfand the optimalxis thePF eigenvectorv ifAis nonnegative and regular, andx >0, thengrowth factors(Ax)i/xi straddle pf: at least one is pf, and at least one is pf when we takexto be the PF eigenvectorv, all the growth factors areequal, and solve both max-min and min-max problemsPerron- frobenius Theory17 23 Power controlwe considerntransmitters with powersP1.

8 , Pn>0, transmitting tonreceiverspath gain from transmitterjto receiveriisGij>0signal power at receiveriisSi=GiiPiinterference power at receiveriisIi=Pk6=iGikPksignal to interference ratio (SIR) isSi/Ii=GiiPiPk6=iGikPkhow do we set transmitter powers to maximize the minimum SIR? Perron-Frobenius Theory17 24we can just as well minimize the maximum interference to signal ratio, ,solve the problemminimizemaxi( GP)iPisubject toP >0where Gij= Gij/Giii6=j0i=jsince G2>0, Gis regular, so solution is given by PF eigenvector of GPF eigenvalue pfof Gis the optimal interference to signal ratio, ,maximum possible minimum SIR is1/ pfwith optimal power allocation, all SIRs are equalnote: Gis the matrix of ratios of interference to signal path gainsPerron- frobenius Theory17 25 Nonnegativity of resolventsupposeAis nonnegative, with PF eigenvalue pf, and Rthen( I A) 1exists and is nonnegative, if and only if > pffor any square matrixAthe power series expansion( I A) 1=1 I+1 2A+1 3A2+ converges provided| |is larger than all eigenvalues ofAif > pf, this shows that( I A) 1is nonnegativeto show converse, suppose( I A) 1exists and is nonnegative, and letv6= 0,v 0be a PF eigenvector ofAthen we have( I A) 1v=1 pfv 0and it follows that > pfPerron- frobenius Theory17 26 Equilibrium pointsconsiderxt+1=Axt+b, whereAandbare nonnegativeequilibrium point is given byxeq= (I A) 1bby resolvent result, ifAis stable, then(I A) 1is nonnegative, soequilibrium pointxeqis nonnegative for any nonnegativebmoreover, equilibrium point is monotonic function ofb.

9 For b b, we have xeq xeqconversely, if system has a nonnegative equilibrium point, foreverynonnegative choice ofb, then we can concludeAis stablePerron- frobenius Theory17 27 Iterative power allocation algorithmwe consider again the power control problemsuppose is the desired or target SIRsimple iterative algorithm: at each stept,1. first choose Piso thatGii PiPk6=iGik(Pt)k= Piis the transmit power that would make the SIR of receiveriequal to ,assuming none of the other powers change2. set(Pt+1)i= Pi+ i, where i>0is a , add a little extra power to each transmitter) Perron-Frobenius Theory17 28each receiver only needs to know its current SIR to adjust its power: ifcurrent SIR is dB below (above) , then increase (decrease) transmitterpower by dB, then add the extra power , this is adistributed algorithmquestion:does it work? (we assume thatP0>0)answer:yes, if and only if is less than the maximum achievable SIR, , <1/ pf( G)to see this, algorithm can be expressed as follows.

10 In the first step, we have P= GPt in the second step we havePt+1= P+ and so we havePt+1= GPt+ a linear system with constant inputPerron- frobenius Theory17 29PF eigenvalue of Gis pf, so linear system is stable if and only if pf<1power converges to equilibrium valuePeq= (I G) 1 (which is positive, by resolvent result)now let s show this equilibrium power allocation achieves SIR at least foreach receiverwe need to verify GPeq Peq, , G(I G) 1 (I G) 1 or, equivalently,(I G) 1 G(I G) 1 0which holds, since the lefthand side is just Perron-Frobenius Theory17 30 Linear Lyapunov functionssupposeA 0thenRn+is invariant under systemxt+1=Axtsupposec >0, and consider the linear Lyapunov functionV(z) =cTzifV(Az) V(z)for some <1and allz 0, thenVproves(nonnegative) trajectories converge to zerofact:a nonnegative regular system is stable if and only if there is a linearLyapunov function that proves itto show the only if part, supposeAis stable, , pf<1takec=w, the (positive) left PF eigenvector ofAthen we haveV(Az) =wTAz= pfwTz, ,Vproves all nonnegativetrajectories converge to zeroPerron- frobenius Theory17 31 Weighted 1-norm Lyapunov functionto make the analysis apply toalltrajectories, we can consider the weightedsum absolute value (or weighted 1-norm) Lyapunov functionV(z) =nXi=1wi|zi|=wT|z|then we haveV(Az) =nXi=1wi|(Az)i| nXi=1wi(A|z|)i=wTA|z|= pfwT|z|which shows thatVdecreases at least by the factor pfconclusion: a nonnegative regular system is stable if and only if there is aweighted sum absolute value Lyapunov function that proves itPerron- frobenius Theory17 32 SV