chapter9

Chapter 9 Hermitian and Symmetric Matrices Example 9.0.1. Letf:D→R,D⊂Rn.T h e Hessian is defined by H(x)=hij(x)≡∂f ∂xi∂xj∈Mn. Since for functions f∈C2it is known that ∂2f ∂xi∂xj=∂2f ∂xj∂xi it follows that H(x)i ss y m m e t r i c . Definition 9.0.1. A function f:R→Risconvex if f(λx+( 1−λ)y)≤λf(x)+( 1−λ)f(y) forx, y∈D(domain) and 0 ≤λ≤1. Proposition 9.0.1. Iff∈C2(D)andf00(x)≥0onDthenf(x)is convex. Proof. Because f00≥0, this implies that f0(x) is increasing. Therefore if x<x m<ywe must have f(xm)≤f(x)+f0(xm)(xm−x) and f(xm)≤f(y)+f0(xm)(xm−y) 237 238 CHAPTER 9. HERMITIAN AND SYMMETRIC MATRICES by the Mean Value Theorem. Therefore, y−xm y−xf(xm)+xm−x y−xf(xm)≤y−xm y−xf(x)+xm−x y−xf(y) or f(xm)≤y−xm y−xf(x)+(xm−x) y−xf(y). It is easy to see that xm=y−xm y−xx+xm−x y−xy. Definingλ=y−xm y−x, it follows that 1 −λ=xm−x y−x. Definition 9.0.2. We say that f:D→R,w h e r e D⊂Rnis convex, is a convex function if fis a convex function on every line in D. Theorem 9.0.1. Suppose f∈C2(D)andH(x)is positive de finite. Then fis convex on D. Proof. Letx∈Dandηbe some direction. Then x+ληis a line in D.W e computed2 dλ2f(x+λn) d dλf=∇f·n= ∂f ∂x1... ∂f ∂xn ·[n1...n n]. Now d dλµ∂f ∂x1¶ =∇∂f ∂x1·η= ∂2f ∂x1∂x1 ∂2f ∂xn∂x1 ·[η1,... ,ηn]. Hence we see that d2 dλ2f(x+λη)=ηTH(x)η≥0 by assumption. 239 Example 9.0.2. LetA=[aij]∈Mn. Consider the quadratic form on Cn orRndefined by Q(x)=xTAx=Σaijxjxi =1 2Σ(aij+aji)xjxi =xT1 2(A+AT)x. Since the matrix A+ATis symmetric the study of quadratic forms is reduced to the symmetric case. Example 9.0.3. LetLf=nP i,j=1aij∂2f ∂xi∂xj.Lis called a partial di fferential operator. By the combination of devices above (assuming f∈C2for exam- ple) we can study the symmetric and equivalent partial di fferential operator Lf=nX i,j=11 2(aij+aji)∂2f ∂xi∂xj. In particular, if A+ATis positive de finite the operator is called elliptic. Other cases are (1) hyperbolic,(2) degenerate/parabolic. Characterizations of Her mitian matrices. Recall (1)A∈M nis Hermitian if A∗=A. (2)A∈Mnis called skew-Hermitian if A=−A∗. Here are some facts (a) If Ais Hermitian the diagonal is real. (b) If Ais skew-Hermitian the diagonal is imaginary. (c)A+A∗,A A∗andA∗Aare all Hermitian if A∈Mn. (d) If Ais Hermitian than Ak,k=0,1,... , are Hermitian. A−1is Her- mitian if Ais invertible. 240 CHAPTER 9. HERMITIAN AND SYMMETRIC MATRICES (e)A−A∗is skew-Hermitian. (f)A∈Mnyields the decomposition A=1 2(A+A∗)+1 2(A−A∗) Hermitian Skew Hermitian (g) If Ais Hermitian iAis skew-Hermitian. If Ais skew-Hermitian then iAis Hermitian. Theorem 9.0.2. LetA∈Mn.T h e n A=S+iTwhere SandTare Hermitian. Moreover this is unique. Proof. A=1 2(A+A∗)+1 2(A−A∗) =S+iT where S=1 2(A+A∗)a n d iT=1 2(A−A∗) ⇒T=−i 2(A−A∗). Theorem 9.0.3. LetA∈Mnbe Hermitian. Then (a)x∗Axis real for all x∈Cn; (b) All the eigenvalues of Aare real; (c)S∗ASis Hermitian for all S∈Mn. Proof. For (a) we have x∗Ax=Σaijxjxi. The conjugate is x∗Ax=Σ¯aij¯xjxi=Σaji¯xjxi =Σaijxj¯xi+x∗Ax Theorem 9.0.4. LetA∈Mn.T h e n Ais Hermitian if and only if at least one of the following holds: 9.1. VARIATIONAL CHARACTERIZATIONS OF EIGENVALUES 241 (a)hAx, x i=x∗Axis real∀x∈Cn. (b)Ais normal with real eigenvalues. (c)S∗ASis Hermitian for all S∈Mn. Proof. Hermitian ⇒(a), (b), or (c) are obvious. (a) ⇒Hermitian. Prove using ejandek.W eh a v e hAej+ek,ej+eki=ajj+akk+ajk+akj ⇒ajk+akjis real⇒Imajk=−Imakj. Similarly hAiej+ek,i ej+eki−ajj+akk+iakj−iajk ⇒i(akj−ajk)i sr e a l⇒Reakj=R e ajk. All this gives A∗=A. (c)⇒Hermitian S∗ASis Hermitian ⇒S∗ASis similar to a real diagonal matrix. Therefore Ais similar to a real diagonal matrix. Just let S=Ito getAis Hermitian. Theorem 9.0.5 (Spectral Theorem). LetA∈Mnbe Hermitian. Then Ais unitarily (similar) equivalent to a real diagonal matrix. If Ais real Hermitian, then Ais orthogonally similar to a real diagonal matrix. 9.1 Variational Characterizations of Eigenvalues LetA∈Mnbe Hermitian. Assume λmin≤λ1≤λ2≤···≤λn−1≤λn=λmax. Theorem 9.1.1 (Rayleigh—Ritz). LetA∈Mn, and let the eigenvalues ofAbe ordered as above. Then λmax=λn=m a x x6=0hAx, x i hx, xi λmin=λ1=m i n x6=0hAx, x i hx, xi. 242 CHAPTER 9. HERMITIAN AND SYMMETRIC MATRICES Proof. Letx1...x nbe the linearly independent and orthogonal eigenvectors ofA. Any vector x∈Cnhas the representation xΣαjxj. Then hAx, x i=Σα2 jλjand hx, xi=Σα2 j.H e n c e hAx, x i hx, xi=X jα2 jP iα2iλj. Since½ α2 j Σα2 i¾ is nonnegative and sums to 1, it follows that hAx, x i hx, xi is a convex combination of the eigenvalues, whence the theorem follows. In particular take x=xn(x1) to achieve the maximum (minimum). Remark 9.1.1. This result gives just the largest and smallest eigenvalues. How can we achieve the intermediate eigenvalues? We have already consid- ered this problem somewhat in conjunction with the power method. In thatconsideration we employed the bi-orthogonal eigenvectors. For a Hermitianmatrix, the families are the same. So we could characterize the eigenvaluesin a manner similar to that discussed previously. However, the following characterization is simpler. Theorem 9.1.2. LetA∈M nbe Hermitian with eigenvalues as above and corresponding eigenvectors x1...x n.T h e n (∗) λn−k=m a x x⊥{xn,... ,x n−k+1} x 6=0hAx, x i hx, xi. The following result is even more general (∗) λn−k=m i n {wn,wn−1...wn−k+1}max x⊥{wn,wn−1...wn−k+1} x 6=0hAx, x i hx, xi. Proof. The Rayleigh—Ritz argument above gives ( ∗) directly. 9.2. MATRIX INEQUALITIES 243 9.2 Matrix inequalities When the underlying matrix is symmetric or positive de finite, certain pow- erful inequalities can be established. The first inequality is a consequence of the cofactor result Proposition 2.5.1. Theorem 9.2.1. LetA∈Mn(C)be positive de finite. Then detA≤a11a22···ann Proof. Expanding in minors, the determinant of A detA=a11¯¯¯¯¯¯¯a 22···a2n ......... an2 ann¯¯¯¯¯¯¯+d e t¯¯¯¯¯¯¯¯¯0a 12···a1n a21a22···a2n ............ an1an2 ann¯¯¯¯¯¯¯¯¯ Since Ais positive de finite, it follows that each of it principal submatrices is also. Therefore, the first term in the right side of the equality above is postive, while the second term is negative by the cofactor result Proposition2.5.1. To clarify , it is important to note that if Ais Hermitian and invert- ible, so also is its inverse. In particular, it Ais positive de finite, we know its determinant is positive and so when we write det¯¯¯¯¯¯¯¯¯0a 12···a1n a21a22···a2n ............ an1an2 ann¯¯¯¯¯¯¯¯¯=−X a 1ja1kaik it is clear this term is negative. Therefore, detA≤a11¯¯¯¯¯¯¯a 22···a2n ......... an2 ann¯¯¯¯¯¯¯ whence the result follows inductively. Corollary 9.2.1. LetS1,S2,..., S rbe any partition of the integers {1,...,n }, and let A1,A2,...,A r., be the principal submatrices of Apertaining to the indices of each subdivision. Then detA=d e t A1detA2···detAr An important consequence of Theorem 9.2.1 is one of the most famous determinantal inequalities. It is due to Hadamard. 244 CHAPTER 9. HERMITIAN AND SYMMETRIC MATRICES Theorem 9.2.1. Let B be an arbitrary nonsingular real square matrix. Then (detB)2≤nY i=1nX j=1|bij|2 Proof. DefineA=BTB.Then diagA= nX j=1|b1j|2,. . . ,nX j=1|bnj|2  whence the result follows from Theorem 9.2.1 since det A=( d e t B)2. 9.3 Exercises 1. Prove Corollary 9.2.1. 2. Establish Theorem 9.2.1 in the case the matrix is complex. 3. Establish a result similar to Theorem 9.2.1 for rectangular matrices. Chapter 10 Nonnegative Matrices 10.1 De finitions Nonnegative matrices are simply those with all nonnegative entries. We will eventually distinguish various types of such matrices substantially onhow they are nonnegative or conversely where they are zero. A particular type of nonnegative matrix, the type that has no o ff-diagonal block to be zero, will turn out to have the greatest value to us. If nonnegative matricesdistinguished themselves in only minor ways from general matrices, theywould not occupy the high position of importance they enjoy in the modernliterature. Indeed, many remarkable properties of nonnegative matriceshave been uncovered. Owing substantially to the many applications to economics, probability, and engineering, the subject has now for more than a century been one of the hottest areas of research within the subject. Definition 10.1.1. A∈M n(R)i sc a l l e d nonnegative ifaij≥0f o r1≤ i, j≤n. We use the notation A≥0 for nonnegative matrices. If aij>0 for all i, jwe say Aisfully (orstrictly )positive . (Notation. AÀ0.) In this section we need some special notation. Let x∈Cn,x=(x1,... ,x n)T. Then |x|=(|x1|,... , |xn|)T. We say that x∈Rnispositive ifxi≥0, 1≤i≤n.W es a yt h a t x∈Rnis fully (orstrictly )positive ifxi>0, 1≤i≤n. We use the notation x≥0 andxÀ0 for positive and strictly positive vectors, respectively. Note that if A≥0w eh a v e kAk∞=kAek∞where e=( 1,1,... , 1)T. 245 246 CHAPTER 10. NONNEGATIVE MATRICES To give an idea of the direction we are heading, let us suppose that A∈Mn(R) is a nonnegative matrix. Let λ6= 0 be an eigenvector of A with pertaining eigenvector x≥0. Thus Ax=λx. (We will prove that this comes to pass for every nonnegative square matrix.) Suppose furtherthat the vector Axis zero on the index set S.That is ( Ax) i=0i f i∈S. Sinceλ6=0i tf o l l o w st h a t xi=0i∈S.L e t SCbe the complement of Sin the integers {1,...,n },a n dl e t PandP⊥be the projections to Sand SC, respectively. So, Px=0a n d P⊥x=x. Also, it is easy to see that In=P+P⊥,and hence PAP⊥x=λPx=0 Therefore PAP⊥=0.When we write A=³ P+P⊥´ A³ P+P⊥´ in block form A=³ P+P⊥´ A³ P+P⊥´ =·PAP PAP⊥ P⊥AP P⊥AP⊥¸ we see that Ahas the special form A=·PAP 0 P⊥AP P⊥AP⊥¸ This particular calculation reveals in a simple way the consequences of zero components to eigenvectors of nonnegative matrices. Zero components ofeigenvectors implies zero blocks of A. I tw o u l db ec o r r e c tt oo b s e r v et h a t this argument requires a nonnegative eig envector. Nonetheless, there are still some very special properties of the remaining eigenvalues of A,p a r t i c u l a r l y those with the modulus equal to the spectral radius. It will be convenient tohave a name for the index set where a nonnegative vector x∈R nis strictly positive. Definition 10.1.2. Letx∈Rnbe nonnegative, x≥0. Let Sbe the index set such that xi6=0i f i∈S.W ec a l l Sthesupport of the vector x. 10.2 General Theory Definition 10.2.1. ForA∈Mn(R)a n dλ/∈σ(A)w ed e fine the resolvent ofAby R(λ)=(λI−A)−1. 10.2. GENERAL THEORY 247 This function behaves much like a rational function in complex variable t h e o r y .I th a sp o l e sa te a c h λ∈σ(A). The order of the pole is the same as t h eo r d e ro ft h ez e r oo f λin the minimal polynomial of A. Theorem 10.2.1. Suppose A∈Mn(R)is nonnegative and λ>ρ(A),t h e n R(λ)=(λI−A)−1≥0. Proof. Apply the Neumann series (?)( λI−A)−1=∞X k=0λ−(k+1)Ak. Sinceλ>0a n d A≥0, it is apparent that R(λ)≥0. Remark 10.2.1. It is apparent that ( ?) holds upon noting that (λI−A)−1à 1−µA λ¶n+1! =nX 0λ−(k+1)Ak and that |λ|>ρ(A) yields convergence. Theorem 10.2.2. Suppose A∈Mn(R)is nonnegative. Then the spectral radiusρ(A)ofAis an eigenvalue of Awith at least one eigenvector, x≥0. Proof. Suppose for each y≥0,R(λ)yremains bounded as λ↓ρ.I fx∈Cn is arbitrary |R(λ)x|=¯¯¯¯¯∞X n=0λ−(n+1)Anx¯¯¯¯¯ ≤∞X n=0|λ|−(n+1)An|x| =R(|λ|)|x| for allλ,|λ|>ρ. It follows that R(λ)xis uniformly bounded in the region |λ|>ρ, and this is impossible. Now let y0≥0 be a vector for which R(λ)y0is unbounded as λ↓p,a n d letkkdenote a vector norm. For λ>r,s e t z(λ)=R(λ)y0/kR(λ)y0k, where kR(λ)y0k↑∞.N o w z(λ)⊂{x|kxk=1}, and the latter is compact. Therefore {z(λ)}λ>ρhas a cluster point x0with x0≥0a n d kx0k=1 . S i n c e (ρI−A)z(λ)=(ρ−λ)z(λ)+y0/kR(λ)y0k 248 CHAPTER 10. NONNEGATIVE MATRICES and since λ→ρand kR(λ)y0k↑∞ we have lim λ→ρ(ρI−A)z(λ)=l i m λ→ρ(ρI−A)x0=0. Corollary 10.2.1. Suppose A∈Mn(R)is nonnegative and Az=λzfor some zÀ0,t h e nλ=ρ(A). Proof. Sinceρ(A)⊂σ(AT) there is a vector y≥0f o rw h i c h ATy=ρy.I f λ6=ρ,w em u s th a v e hz,yi=0 . B u t zÀ0 and this is impossible. Corollary 10.2.2. Suppose A∈Mn(R)is strictly positive and z≥0such thatAz=ρz,t h e n zÀ0. Proof. Ifzi=0 ,t h e nnP j=1aijzj= 0, and thus zj=0f o ra l l jsince aij>0, for all j. Hence z= 0, a contradiction. This result will be strengthened in the next section by another result that has the same conclusion but a much weaker hypotheses. Theorem 10.2.3. Suppose A∈Mn(R)is nonnegative with spectral radius ρ(A)and de fine rm=m i n iX jaij rM=m a x iP jaij cm=m i n jX iaij cM=m a x jP iaij then both inequalities below hold. rm≤ρ(A)≤rM cm≤ρ(A)≤cM Moreover, if A, B∈Mn(R)thenρ(A+B)≥max(ρ(A),ρ(B)). Proof. We prove the second set of inequalities. Let x∈Rnbe the eigenvec- tor pertaining to ρ(A).Since x≥0 we can normalize xso thatPxi=1. Then nX j=1aijxj=ρ(A)xi,i =1,...,n 10.2. GENERAL THEORY 249 Sum both side in ito obtain nX i=1nX j=1aijxj=nX i=1ρ(A)xi nX j=1ÃnX i=1aij! xj=ρ(A) ReplacingPn i=1aijbycMmakes the sum on the left larger, that is ρ(A)≤nX j=1ÃnX i=1aij! xj≤cMnX i=1xi=cM Similarly replacingPn i=1aijbycmmakes the sum on the left smaller, and therefore ρ(A)≥cm.Thus, cm≤ρ(A)≤cM.The other inequality, rm≤ρ(A)≤rM,can be easily established by applying what has just been proved to the matrix ATnoting of course that ρ(A)=ρ(AT). The proof that ρ(A+B)≥max(ρ(A),ρ(B)) is an easy consequence of a Neumann series argument. We could just as well prove the first inequality and apply it to the transpose to obtain the second. This proof is given below. Alternative Proof. Letxbe the eigenvector pertaining to ρ(A)a n d xk= max ixi.T h e n ρxk=nX j=1aijxj≤ nX j=1aij maxxj. Hence ρ≤nX j=1aij≤max knX j=1akj=t. To obtain s≤ρ,l e ty≥0s a t i s f y ATy=ρy and suppose kyk1=1 .T h e nw eh a v eo nt h eo n eh a n d he, ATyi=ρhe, yi=ρ 250 CHAPTER 10. NONNEGATIVE MATRICES and on the other hand applying convexity he, ATyi=X iX jaT ijyj =X jyjÃX iaji! ≥min jX iaji=s Corollary 10.2.1. (i) Ifρ(A)is equal to one of the quantities cmorcM, then all of the sumsP iaijare equal for jin the support of the eigenvector xpertaining to ρ. (ii) Ifρ(A)is equal to one of the quantities rmorrM, then all of the sumsP jaijare equal for iin the support of the eigenvector yofATpertaining toρ. (iii) If all the row sums (resp. column sums) are equal, the spectral radius is equal to this value. Proof. Assume that ρ(A)=cM.L e t Sdenote the support (recall De finition 10.1.2) of the eigenvector x. Assume also that the eigenvector xis normal- ized so thatPn j=1xj=P j∈Sxj= 1. Following the proof of Theorem 10.2.3 we have nX j=1ÃnX i=1aij! xj=X j∈SÃnX i=1aij! xj=cM Since1 cM(Pn i=1aij)≤1f o re a c h j=1,...,n it follows that X j∈S1 cMÃnX i=1aij! xj≤X j∈Sxj Clearly if for some j∈Swe have1 cM(Pn i=1aij)<1 the inequality above will become a strict inequality, and the result is proved. The result is proved similarly for cm (ii) Apply the proof of (i) to AT. 10.3 Mean Ergodic Theorem LetA∈Mn(R). We have seen that understanding the nature of powers Ak, k=1,2,... leads to interesting conclusions. For example if lim k→∞Ak=P, 10.3. MEAN ERGODIC THEOREM 251 it is easy to see that Pis idempotent ( P2=P)a n d AP=PA=P.I t i s therefore a projection to the fixed space ofA. A less restrictive property is mean convergence : Mk=k−1(I+A+A2+···+Ak) lim k→∞Mk=P. Note that if ρ(A)<1w eh a v e Ak→0. Hence Mk→0. On the other hand ifρ(A)>1t h e Mkbecome unbounded. Hence mean convergence has value only when ρ(A)=1 . Theorem 10.3.1 (Mean Ergodic Theorem for matrices). LetA∈Mn(R) withρ(A)=1 .I f{Ak}∞ k=1is bounded then lim k→∞Mk=P,w h e r e Pis a pro- jection, commuting with A,o n t ot h e fixed space of A. Proof. We need a norm k·k, vector and matrix. We have kAkk<C for k=1,2,... . It is easy to see that (?) AM k−Mk=1 kÃkX 0Aj+1! −1 kÃkX 0Aj! =1 k(I+Ak+1) ≤1 k(1 +C). Since the matrices Mkare bounded they have a cluster point P. This means there is a subsequence Mkjthat converges to P. If there is another cluster point Q(i.e. there is a subsequence M`j→Q), then we compare PandQ. First we know kMkj−Pk<ε 2(1 + C) kM`j−Qk<ε 2(1 + C). From ( ?)w eh a v e AP=PandAQ=Q, whence MkjP=PandMljQ=Q for all k=1,2,... . Hence P−Q=M`j(Mkj−P)−Mkj(M`j−Q) or kP−Qk≤ε. 252 CHAPTER 10. NONNEGATIVE MATRICES Thus P=QandMkconverges to some matrix P.W eh a v e AP=PA=P hence MkP=Pfor all kand therefore P2=P. Clearly the range of P consists of all fixed vectors under A. Corollary 10.3.1. LetA∈Mn(R)and suppose that lim k→∞Ak=P,t h e n lim k→∞Mkexists and equals P. Definition 10.3.1. LetA∈Mn(R)h a v eρ(A)=1 . T h e n Ais said to be mean ergodic if limk−1(I+A+···+Ak) exists. Clearly, if A∈Mn(R)s a t i s fiesρ(A)=1a n d Akis bounded, then Ais mean ergodic. (Previous theorem.) Conversely, if Ais mean ergodic then the sequence Akis bounded. This can be proved by resorting to the Jordan canonical form and showing Akis bounded if and only if Ak jis bounded, where AJis the Jordan canonical form of A. Lemma 10.3.1. LetA∈Mn(R)withρ(A)=1 .S u p p o s e λ=1 is a simple pole of the resolvent, and the only eigenvalue of modulus 1. ThenA=P+Bwhere P=l i m λ→1(λ−1)R(λ)is a projection onto the fixed space ofA,PB=BP=0 andρ(B)<1. Proof. We know that Pexists and using the Neumann series it is clear that AP=PA=P Alim λ→1(λ−1)(λI−A)−1=A(λ−1)∞X 0λ−(k+1)Ak =l i m λ→1(λ−1)∞X 0λ−(k+1)Ak+1 =l i m λ→1(λ−1)λ"X 0λ−(k+1)Ak−λ−1# =l i m λ→1(λ−1)R(λ)=P. That is, AP=P. The other assertions follow similarly. Also, it follows that P2=l i m λ→1PR(λ)=P 10.4. IRREDUCIBLE MATRICES 253 which is to say that Pis a projection. We have, as well, that Ax=x⇒ Px=x, again using the Neumann series. Now de fineB=A−P.T h e n BP=PB= 0. Suppose Bx=ax,w h e r e |α|≥1. Then Px=0 ,f o r αPx=PBx =0. Therefore Ax=αx.H e r eα6=1i m p l i e s x= 0 by hypothesis and α=1 implies Px=x,o r x= 0, also. This contradicts the assumption that |α|≥1. Theorem 10.3.2. LetA∈Mn(R)satisfy A≥0andρ(A)=1 .T h e following are equivalent: (a)λ=1 is a simple pole of R(λ). (b){Ak}∞ 1is bounded. (c)Ais mean ergodic. Moreover lim λ→1(λ−1)R(λ)= l i m k→∞1 k(I+A+···+Ak) if either limit exists. 10.4 Irreducible Matrices Irreducible matrices form one of the cornerstones of positive matrix theory. Because the condition of irreducibility is both natural and often satis fied, their applications are far and wide. Definition 10.4.1. LetA∈Mn(C).Thezero pattern ofAis the set of ordered pairs S={(i, j)|aij=0}. Example 10.4.1. For example with A= 012 100230  S={(1,1),(2,2),(2,3),(3,3)}. 254 CHAPTER 10. NONNEGATIVE MATRICES Definition 10.4.2. A generalized permutation matrix Bis any matrix hav- i n gt h es a m ez e r op a t t e ra sap e r m u t a t i o nm a t r i x . This means of course that a generalized permutation matrix has ex- actly one nonzero entry in each row and one nonzero entry in each column.Generalized permutation matrices ar e those nonnegative matrices with non- negative inverses. Theorem 10.4.1. LetA∈M n(R)be invertible and A≥0.Then Ais invertible with nonnegati ve inverse if and only if Ais a generalized permu- tation matrix. Proof. First, if Ais a generalized permutation matrix, de fine the matrix B by bij=  0i f aij=0 1 aijifaij6=0 Then A−1=BT≥0. On the other hand suppose A−1≥0a n d Ahas on some row two non zero entries, say ai,j1andai,j2.S i n c e A−1≥0i s invertible there is a nonzero entry in the ithcolumn, say a−1 ki>0. Now compute multiply A−1A. It is easy to see that ¡ A−1A¢ k,j1>0a n d¡ A−1A¢ k,j2>0 which contradicts that A−1A=I. Example 10.4.1. The analysis for 2 ×2 matrices can be carried out directly. Suppose that A=·ab cd¸ and A−1=1 detA·d−b −ca¸ There are two cases: (1) det A> 0. In this case we conclude that b=c=0. Thus Ais a generalized permutation matrix. (2) det A< 0. In this case we conclude that a=d=0.Again Ais a generalized permutation matrix. As these are the only two cases, the result is veri fied. Definition 10.4.3. LetA, B∈Mn(R). We say that Aiscogredient to Bif there is a permutation matrix Psuch that B=PTAP 10.4. IRREDUCIBLE MATRICES 255 Note that two cogredient matrices are similar, indeed they are unitarily similar for the very special class of unitary matrices given by permutations.It is important to note that since APmerely interchanges the columns of AandP TAPthen interchanges the rows of AP.From this we observe that both AandB=PTAPhave exactly the same elements, though permuted. Definition 10.4.4. LetA∈Mn(R). We say that Aisirreducible if it is notcogredient to a matrix of the form ·A10 A3A4¸ where the block matrices A1andA4are square matrices. Otherwise the matrix is called reducible. Example 10.4.2. All diagonal matrices are reducible. There is another way to describe irreducible (and reducible) matrices in terms of projections. Let S={j1,...,j k}⊂{1,2,...,n }and de finePSto be the projection to the coordinate directions by PSei=½1if i∈S 0if i /∈S Furthermore de fine P⊥ S=I−PS Then PSandP⊥ Sare orthogonal projections. That is, the product PSP⊥ S= 0 and by de finition PS+P⊥ S=I.I f SCdenotes the complement of Sin {1,2,...,n },it is easy to see that P⊥ S=PSC Proposition 10.4.1. LetA∈Mn(R).T h e n Ais irreducible if and only if there is no set of indices S={j1,...,j k}⊂{1,2,...,n }for which PSAP⊥ S=0. Proof. Suppose there is a set of indices S={j1,...,j k}⊂{1,2,...,n }for which PSAP⊥ S=0.Define the permutation matrix as from the permutation that takes the firstkintegers 1 ,..., k to the integers j1,...,j kand the integers k+1,...,n to the complement SC.Then PTAP=·A1A2 A3A4¸ 256 CHAPTER 10. NONNEGATIVE MATRICES T h ee n t r i e si nt h eb l o c k A2are those with rows given from the rows cor- responding to the indices in Sand columns corresponding to the indices inSC.T h u s Ais reducible. Conversely, suppose that Ais reducible and that Pis a permutation matrix such that PTAP=·A10 A3A4¸ For de finiteness, let us assume that A1isk×kandA4is (n−k)×(n−k). DefineS={ji|pji,i=1,i=1,...,k }.a n d T={ji|pji,i=1,i= k+1,...,n }Because Pis a permutation, it follows that T=SCand PSAP⊥ S= 0, which proves the converse. As we know for a nonnegative matrix A∈Mn(R) the spectral radius is an eigenvalue of Awith pertaining eigenvector x≥0.When the additional assumption of irreducibility of Ais added the conclusion can be strengthened toxÀ0.To prove this result we establish a simple result from which the xÀ0 follows almost directly. Theorem 10.4.2. LetA∈Mn(R)be nonnegative and irreducible. Sup- pose that y∈Rnis nonnegative with exactly 1≤k≤n−1nonzero entries. Then (I+A)yhas strictly more nonzero entries. Proof. Suppose the nonzero entries of yareS={j1,...,j k}.S i n c e ( I+A)y= y+Ay, it follows immediately that (( I+A)y)ji6=0f o r ji∈S,a n dt h e r e - fore there are at least as many nonzero entries in ( I+A)yas there are in y.In order that the number of nonzero entries not increase, we must have for each index i/∈Sthat ( Ay)i=0.With PSdefined as the projection to the standard coordinates with indices from Swe conclude therefore that P⊥ SAP=0,which means that Ais reducible, a contradiction. Corollary 10.4.1. LetA∈Mn(R)be nonnegative. Then Ais irreducible if and only if (I+A)n−1>0. Proof. Suppose that Ais irreducible and y≥0i sa n yv e c t o ri n Rn.T h e n (I+A)yhas strictly more nonzero coordinates and thus ( I+A)2yhas even more nonzero coordinates. We see that the number of nonzero coordinatesof (I+A) kymust increase by at least one until the maximum of nnonzero coordinates is reached. This must occur by the ( n−1)thpower. Now apply this to the vectors of the standard basis e1,...,e n. For example, (I+A)n−1ekÀ0.This means that the kthcolumn of ( I+A)n−1is strictly positive. The result follows. 10.4. IRREDUCIBLE MATRICES 257 Suppose conversely that ( I+A)n−1>0 but that Ais reducible. Then there is a permutation matrix Psuch that PTAP has the form PTAP=·A10 A3A4¸ It is easy to see that all the powers of Ahave the same form – with respect to the same blocks. Also, ( I+A)n−1=I+Pn−1 i=1¡n−1 i¢ Ai.So PT(I+A)n−1P=PTà I+n−1X i=1µn−1 i¶ Ai! P =I+n−1X i=1µn−1 i¶ PTAiPT has the same form PT(I+A)n−1P=·˜A10 ˜A3˜A4¸ a n dt h i sp r o v e st h er e s u l t . Corollary 10.4.2. LetA∈Mn(R)be nonnegative. Then Ais irreducible if and only if for each pair of indices (i, j)there a positive power 1≤k≤n such that¡ Ak¢ ij>0. Proof. Suppose that Ais irreducible. Since ( I+A)n−1=I+Pn−1 i=1¡n−1 i¢ Ai> 0, it follows that A(I+A)n−1=A+Pn−1 i=1¡n−1 i¢ Ai+1>0.Thus for each pair of indices ( i, j),¡ Ak¢ ij>0f o r s o m e k. On the other hand suppose that Ais reducible. Then there is a permu- tation matrix Pfor which PTAP=·A10 A3A4¸ Follow the same argument as above to establish that A(I+A)n−1must h a v et h es a m ef o r ma s PTAPwith the same zero pattern. Thus there is no positive power 1 ≤k≤nsuch that¡ Ak¢ ij>0 for any of the pairs of indices corresponding to the (upper right) zero block above. Another characterization of irreducibility arises when we have Ax≤axfor some nonzero vector x≥0. This type of domination-type condition appears to be quite weak. Nonetheless, it is equivalent to the others. 258 CHAPTER 10. NONNEGATIVE MATRICES Corollary 10.4.3. LetA∈Mn(R)be nonnegative. Then Ais irreducible if and only if Ax≤axfor some nonzero vector x≥0,t h e n xÀ0. Proof. Ifxi=0,then aij= 0 whenever xj6=0.DefineS={1≤j≤ n|xj6=0}.Then with PSas the orthogonal projection to the standard vectors ei,i∈S,it must follow that PSAP⊥ S=0 . S i n c e Sis strictly contained in {1,2,...,n }, it follows that Ais reducible. Now suppose that Ais reducible, which means we can assume it has the form A=·A10 A3A4¸ For de finiteness, let us assume that A1isk×kandA4is (n−k)×(n−k) and of course k≥1. Let v∈Rn−kbe the nonzero nonnegative vector which satisfiesA4v=ρ(A4)v.Letu=0∈Rk.D efine the vector x=u⊕v.T h e n (Ax)i=½(A1u)i=0=ρ(A4)uiif 1≤i≤k (A1v)i=ρ(A4)vi if k +1≤i≤n The conditions of that the hypothesis are met without xÀ0. Corollary 10.4.4 (Subinvariance). LetA∈Mn(R)be nonnegative and irreducible with spectral radius ρ. Suppose that there is a positive number s and nonnegative vector z≥0for which (Az)i≤szi, for i=1,2,...,n Then (i) zÀ0, and (ii) ρ≤s. If in addition ρ=s,t h e n Az=ρz. Proof. Clearly, the same inequality holds for powers of A.F o r A(Az)≤ Az≤sz. Now apply induction. Next suppose that zi=0.By Corollary 10.4.2 we must have for each index pair i, jthat¡ Ak¢ ij>0 for some positive integer kmaking¡ Akz¢ i≤sziimpossible for some k.T h u s zÀ0.To prove the second assertion, let xbe the eigenvector of ATpertaining ρ.T h e n hAz, x i=­ z,ATx® =ρhz,xi≤shz,xi (1) Since xÀ0,the innerproduct hz,xi>0. Hence ρ≤s. Finally, if ρ=sand ( Az)i<ρzifor some index ithen we conclude from (1) that ρ<ρ, a contradiction. 10.4. IRREDUCIBLE MATRICES 259 Theorem 10.4.3. LetA∈Mn(R)be nonnegative and irreducible. If x≥ 0is the eigenvector pertaining to ρ(A), i.e. Ax=ρ(A)x,t h e n xÀ0. Proof. We have that ( I+A) is also nonnegative and irreducible, with spec- tral radius 1 + ρ(A) and pertaining eigenvector x.S i n c e (I+A)n−1x>(1 +ρ(A))n−1xÀ0 it follows that xÀ0. Corollary 10.4.5. (i) Ifρ(A)is equal to one of the quantities cmorcM from Theorem 10.2.3, then all of the sumsP iaijare equal for j=1,...,n . (ii) Ifρ(A)is equal to one of the quantities rmorrMfrom Theorem 10.2.3, then all of the sumsP jaijare equal for i=1,...,n . (iii) Conversely, if all the row sums (resp. column sums) are equal, the spectral radius is equal to this value. Proof. Both are direct consequences of Corollary 10.2.1 and Theorem 10.4.3 which imply that the eigenvectors (of AandAT, resp.) pertaining to ρare strictly positive. 10.4.1 Sharper estimates of the maximal eigenvalue Sharper estimates for the maximal eigenvalue (spectral radius) are possible.The following results assembles much of what we have considered above. Webegin with a basic inequality that has an interesting geometric interpreta- tion. Lemma 10.4.1. Leta i,bi,i=1,...n be two positive sequences. Then min jbj aj≤Pn j=1bjPn j=1aj≤max jbj aj Proof. We proceed by induction. The result is trivial for n=1 . F o r n=2 the result is a simple consequence of vector addition as follows. Considerthe ordered pairs ( a i,bi),i=1,2. Their sum is ( a1+a2,b1+b2). It is a simple matter to see that the slope of this vector must lie between the slopesof the summands, which is to say min jbj aj≤P2 j=1bjP2 j=1aj≤max jbj aj 260 CHAPTER 10. NONNEGATIVE MATRICES as is shown below. Now assume by induction the result holds up to n−1.Then we must have that Pn j=1bjPn j=1aj=Pn−1 j=1bj+bnPn−1 j=1aj+an≤max"Pn−1 j=1bjPn−1 j=1aj,bn an# ≤max· max 1≤j≤n−1bj aj,bn an¸ =m a x 1≤j≤nbj aj A similar argument serves to establish the other inequality. Theorem 10.4.4. LetA∈Mn(R)be nonnegative with row sums rkand spectral radius ρ.T h e n min k 1 rknX j=1akjrj ≤ρ≤max k 1 rknX j=1akjrj  (2) Proof. First assume that Ais irreducible. Let x∈Rnbe the principal nonnegative eigenvector of AT,s o ATx=ρxandxÀ0. Assume also that xhas been normalized so thatPxi= 1. By summing both sides of ATx=ρx,w es e et h a tPrkxk=ρ.S i n c eρ2is the spectral radius of A2,w e also have that¡ AT¢2x=¡ A2¢Tx=ρ2x. Summing both sides, it follows thatPn k=1Pn j=1rjaT jkxk=ρ2.N o w ρ=ρ2 ρ=Pn k=1Pn j=1rjaT jkxk rkxk=m a x kPn j=1akjrj rk by Lemma 10.4.1. The reverse inequality is proved similarly. In the case that Ais not irreducible, we take the limit Ak↓Awhere the Akare irreducible matrices. The result holds for each Ak, and the quantities in the inequality are continuous in the limiting process. Some small care must be t a k e ni nt h ec a s et h a t Ahas a zero row. 10.4. IRREDUCIBLE MATRICES 261 Of course, we have not yet established that the estimates (2) are sharper that the basic inequality min krk≤ρ≤max krk. That is the content of following result, whose proof is left as an exercise. Corollary 10.4.6. Let A∈Mn(R)be nonnegative with row sums rk. Then min krk≤min k 1 rknX j=1akjrj ≤ρ≤max k 1 rknX j=1akjrj ≤max krk We can continue this kind of argument even further. Let A∈Mn(R) be nonnegative with row sums riand let xbe the nonnegative eigenvector pertaining to ρ.T h e n¡ AT¢3x=ρ3xor expanded X m,k,jaT ijaT jkaTkmxm=ρ3xi Summing both sides yields X m,k,jrjaT jkaTkmxm=ρ3 Therefore, ρ=ρ3 ρ2=P mP kP jrjaT jkaTkmxmP mP jrjaT jmxm ≤max mP kP jrjaT jkaTkm P jrjaT jm=m a x mP kamkP jakjrjP jamjrj by Lemma 10.4.1, thus yielding another estimate for the spectral radius. The estimate is two-sided as those above. This is summarized in the fol-lowing result. Theorem 10.4.5. LetA∈M n(R)be nonnegative with row sums ri.T h e n min mP kamkP jakjrjP jamjrj≤ρ≤max mP kamkP jakjrjP jamjrj(3) Remember the complete proof as developed above does require the assump- tion irreducibility and the passage of the limit. Let’s consider an example and see what these estimates provide. 262 CHAPTER 10. NONNEGATIVE MATRICES Example 10.4.3. Let A= 133 535 114  The eigenvalues of Aare−2,2, and 8. Thus ρ= 8. The row sums are r1=7,r2=1 3 ,r3= 6, which yields the estimates 6 ≤ρ≤13. The estimates from (2) are64 7,8,and22 3giving the estimates 7.333333333 ≤ρ≤9.142857143 Finally, from (3) the estimates for ρare 7.818181818 ≤ρ≤8.192307692 It remains to show that the estimates in (3) furnish an improvement to the estimates in (2). This is furnished by the following corollary, which is left as an exercise. Corollary 10.4.7. LetA∈Mn(R)be nonnegative with row sums ri.T h e n for each m=1,...,n min k 1 rknX j=1akjrj ≤P kamkP jakjrjP jamjrj≤max k 1 rknX j=1akjrj  (4) These results are by no means the end of the story on the important subject of eigenvalue estimation. 10.5 Stochastic Matrices Definition 10.5.1. Am a t r i x A∈Mn(R),A≥0, is called (row) stochastic if each row sum of Ais 1 or equivalently Ae=e.( R e c a l l , e=( 1,1,... , 1)T.) Similarly, a matrix A∈Mn(R),A≥0, is called column stochastic if ATis stochastic. A direct consequence of Corollary 10.2. 1(iii) is that the spectral radius of stochastic matrices must be one. Theorem 10.5.1. LetA∈Mn(R)row or column stochastic . Then the spectral radius of Aisρ(A)=1 . 10.5. STOCHASTIC MATRICES 263 Lemma 10.5.1. Let A, B∈Mn(R)be nonnegative row stochastic ma- trices. Then for any number 0≤c≤1,t h em a t r i c e s cA+( 1−c)Band AB are also row stochastic. The same result holds for column stochastic matrices. Theorem 10.5.2. Every stochastic matrix is mean ergodic, and the periph- eral spectrum is fully cyclic. Proof. IfA≥0 is stochastic, so also is Ak,k=1,2,... .T h e r e f o r e Akis bounded. Also ρ(A)≤max iP kaij= 1. Hence the conditions of the previous theorems are met. This proves Ais mean ergodic. Stochastic matrices–as a set–have some interesting properties. Let Sn⊂ Mn(R) of stochastic matrices. Then Snis a convex set, it is also closed. Whenever a closed convex set is determined, the characterization of its ex- treme points is desired. Recall, the (matrix) point A∈Snis called an extreme point if whenever A=ΣλjAj Σλj=1 ,λj≥0a n d Aj∈Snit follows that one of the Aj’s equals Aand allλjbut one are 0. Examples. We can also view Sn⊂Rn2. It is a convex subset of Rn2 and is moreover the intersection of the positive orthant of Rn2with the n hyperplanes de fined byP jaij=1 , i=1,... ,n . [Note that we are viewing a vector x∈Rn2as x=(α11,... ,α1n,α21,... ,α2n,... ,αn1,... ,αnn)T] Snis therefore a convex polyhedron inRn2. The dimension of Snisn2−n. Theorem 10.5.3. A∈Snis an extreme point of Snif and only if Ahas exactly one 1 in each row, and all other entries are zero. Proof. LetC=cijbe a (0,1)-matrix. (That is a matrix cij=½1 0or for all 1≤i, j≤n.) Suppose that C∈Snthen there is a unique jfor which cij=1 . I f C=λA+( 1−λ)Bit is easy to see that a1j=b1j=1a n d moreover that a1k=b1k=0f o ra l lo t h e r k6=j. It follows that Cis an 264 CHAPTER 10. NONNEGATIVE MATRICES extreme point. Conversely suppose C∈Snisnota (0,1) matrix. Fix one row. Let Aj= e j c2→ ... cn→  where e j=( 0,0,... , 1, jthposition0...0) and c2...c nare the respective rows of C. Then C=nX 1C1jAj. IfC1is not a (0,1) row we are finished, since Ccannot be an extreme point. Otherwise select any non (0,1) row and repeat this argument with respectto that row. Corollary 10.5.1. Permutation matrices are extreme points. Definition 10.5.2. Alattice homomorphism ofCnis a linear map A:Cn→ Cnsuch that |Ax|=A|x|, for all x∈Cn.Ais a lattice isomorphism if both AandA−1are lattice homomorphisms. Theorem 10.5.4. A∈Snis a lattice homomorphism if and only if Ais an extreme point of Sn.A∈Snis a lattice isomorphism if and only if Ais a permutation matrix. Theorem 10.5.5. A⊂Snis a permutation matrix if and only if σ(A)⊂Γ. Γ={λ∈C||λ|=1}.Exercise. 1. Show that any row stochastic matrix (i.e. nonnegative entries with row sums are equal 1) with at least one column having equal entries is singular. 2. Show that the only nonnegative matrices with nonnegative inverses must be diagonal matrices. 3. Adapt the argument from Section 10.1 to prove that the nonnegative eigenvector xpertaining to the spectral radius of an irreducible matrix must be strictly positive. 10.5. STOCHASTIC MATRICES 265 4. Suppose that A, B∈Mn(R) are nonnegative matrices. Prove or disprove (a) If Ais irreducible then ATis irreducible. (b) If Ais irreducible then Apis irreducible, for every positive power p≥1. (c) If A2is irreducible then Ais irreducible. (d) If A, B are irreducible, then ABis irreducible. (e) If A, B are irreducible, then aA+bBis irreducible for all non- negative constants a, b≥0. 5. Suppose that A, B∈Mn(R) are nonnegative matrices. Prove that ifAis irreducible, then aA+bBis irreducible for all nonnegative constants a, b > 0. 6. Suppose that A∈Mn(R) is nonnegative and irreducible and that the trace of Ais positive, tr A> 0.Prove that Ak>0f o rs o m es u fficiently large integer k. 7. Prove Corollary 10.2.1(ii) for ρ(A)=rm. 8. Let A∈Mn(R) be nonnegative with row sums ri(A)a n dc o l u m n sums ci(A). Show thatPn i=1ri¡ A2¢ =Pn i=1ci(A)ri(A). 9. Prove Corollary 10.4.6. 10. Prove Corollary 10.4.7. (Hint. Use Lemma 10.4.1.) 11. Let pbe any positive integer and suppose that A∈Mn(R) is nonneg- ative with row sums ri.D efiner=(r1,..., r n)T. Recall that ( Apr)m refers to the mthcoordinate of the vector Apr.Show that min m(Apr)m (Ap−1r)m≤ρ≤max m(Apr)m (Ap−1r)m (Hint. Assume first that Ais irreducible.) 12. Use the estimates (2) and (3) to estimate the maximal eigenvalue of A= 514 315 122  The maximal eigenvalue is approximately 7.640246936. 266 CHAPTER 10. NONNEGATIVE MATRICES 13. Use the estimates (2) and (3) to estimate the maximal eigenvalue of A= 2144 573250605557  The maximal eigenvalue is approximately 14.34259731. 14. Suppose that A∈M n(R) is nonnegative and irreducible with spectral radiusρ, and suppose x∈Rnis any strictly positive vector, xÀ0. Defineτ=m a x i(Ax)i xi. Show that ρ≤τ. 15. A=·10 01¸ σ(A)={1} C= 001 100 010  B=·01 10¸ σ(B)={−1,1}ρC(λ)=λ3+1=0 λ=−1,eiπ/3,e−iπ/3