Estimation For The Perron Root Of Nonnegative Matrices And Its Application

In the production practice and scientific study, we often meet the problemof eigenvalue, such as, in the numerical analysis of ordinary di?erential equationsand partial di?erential equations, to determine the approximate characteristicsystem of a continuity problem is often met, which can be described the vibrationof pole, board or structure, and the wave of ?uid.Nonnegative matrices are a class of important matrices, applied extensivelyin numerical analysis, probability and statistics, combinatory analysis, dynamicprogramming, operation research, mathematical economics, sociology, etc. Forexample, when we focus on problems that naturally appear in the design ofresource allocation strategies for wireless networks, di?erent properties of thePerron root of nonnegative irreducible matrices turn out to be vital to betterunderstanding of fundamental tradeo?s between diverse optimization objectives.Providing conditions under which the Perron root can be regarded as a convexfunction of the parameter vector, and the convexity property is an importantfactor in the development of access control and resource allocation strategies forwireless networks. The nonnegative matrix decomposing method has a very im-portant applying significance in the field of intelligent information processing andpattern recognition. Simultaneously, M-matrices closely related to nonnegativematrices are extensively applied in practice. The estimation and computationfor the Perron root of nonnegative matrices will attribute to the linear systemconvergence analysis and stability analysis in practice of some practical problem. The estimation and computation for the Perron root of nonnegative matriceswill be studied, though this problem is studied and depicted systematically, it hasmany things to study and discuss. For example, how to give the more accurateestimation for the lower and upper bounds of the Perron root, especially howto compute the Perron root of a large scale matrix, and the estimation andcomputation for the minimal eigenvalue of closely related M-matrices. Althoughthere are many results obtained, we will improve some of them in essence so thatthey will be easy to use and improve the e?ciency of calculation.In the paper, the k-path coverage in matrix directed graph is defined asfollows:Definition 2.3.1 Letγ: i1,i2,···,is,is+1 = i1∈C(A), k is an integer,t = min{k+1,r}, the least common multiple of t and r is [t,r] = pt = qr. We call,those directed path setsρ1,···,ρp inγ,beginning with ij,ij+t,···, ij+(p?1)t andcontaining t ? 1 directed edges, respectively, as the k-path coverage (basedon ij)on the simple loopγ, denotes Pk(γ).Definition 2.3.2 Let k is an integer, for everyγ∈C(A) in G(A) , take ak-path coverage Pk(γ) , and we call Pk(A) =γ∈C(A)Pk(γ) a k-path coverage.Apply the definition, with the analysis of the simple loops in matrix directedgraph, to give rise to the further results of the upper and lower bounds estimationfor the Perron root of a nonnegative matrix.In the Chapter 2, first of all, with 1-path coverage in matrix directed graph,the main results of the upper and lower bounds estimation for the Perron root ofa nonnegative matrix are given as follows:Theorem 2.4.1 Let A = (aij)∈Nn , forγ∈C+(A)(or C?(A)) , use Then, there exists the following estimation about the Perron rootρ(A) of A,Corollary 2.4.3 Let A = (aij)∈Nn , and notions as Theorem 2.4.1, anddenoteThen, there exists the following estimation about the Perron rootρ(A) of A,Theorem 2.4.1 and Corollary 2.4.3 are the Brualdi-type estimation for thePerron root of nonnegative matrices. The following Theorem 2.4.2 and Corollary2.4.8 are its improved one.Theorem 2.4.2 Let A = (aij)∈Nn, P1(γ) is 1-path coverage ofγ∈C(A),and denoteThen, there exists the following estimation about the Perron rootρ(A) of A,Corollary 2.4.8 Let A = (aij)∈Nn, P1(A) is 1-path coverage of G(A),and denote Then, there exists the following estimation about the Perron rootρ(A) of A,At the same time, we introduce the definition of the k-path advantage cov-erage two nonnegative matrices'comparison as follows (here, k-path coverage inmatrix A directed graph is seen on its simple loop and the trivial loop includingaii = 0, namely on C(A)):Definition 2.5.1 Let A,B∈Nn, Pk(A),Pk(B) be the k-path coverage ofA,B respectively, and C(B) is the sub-graph of C(A) . If for ?ρ∈Pk(γ)∈Pk(A),without loss of generality, denoteρ: i1,i2,···,ik, ik+1 , there existsThen say A is greater than or equal to B by k-path coverage.DenoteWith the help of k-path coverage on the simple loops in matrix directedgraph, we get the further results about the upper and lower bounds estimationfor the Perron root of a nonnegative matrix are obtained:Theorem 2.5.7 Let A = (aij)∈Nn, P1(A) is 1-path coverage of Adirected graph ,eij∈P1(A){δiαδj1 ?α}ρ(??1A)≤ρ(A)≤eijm∈Pa1x(A){δiαδj1 ?α}ρ(??1A),Furthermore, if A is irreducible, two sides of the inequalities are either simulta-neously equal or simultaneously strictly inequalities. Especially, takeα= 12 , there existsMoreover, if A is irreducible, two sides of the inequalities are either simultaneouslyequal or simultaneously strictly inequalities.Extending the above results further, the following results can be obtained:Theorem 2.5.10 Let A∈Nn, Pk(A) is k-path coverage of A .LetFurthermore, if A is irreducible, two sides of the inequalities are either simulta-neously equal or simultaneously strictly inequalities.Corollary 2.5.5 Set A∈Nn, Pk(A) is k-path coverage of G(A), k≥1,then for ?α∈[0, 1] , the Perron rootρ(A) of A satisfiesMoreover, if there is no zero row in A, then the lower bound ofρ(A) satisfiesEspecially, takeα= 1 ,and there exists Moreover, if there is no zero row in A , thenFor an irreducible nonnegative matrix A , denote |γ|max = maxγ∈C(A) |γ|. Whenk≥|γ|max , for any simple loop and the trivial loopγof G(A) , the k-pathcoverage on it has been reducible toγitself. Therefore, we can get the furtherextensive results.Theorem 2.5.12 Let A∈Nn . LetFurthermore, if A is irreducible, two sides of the inequalities are either simulta-neously equal or simultaneously strictly inequalities.In the Chapter 3, we use the matrix diagonal similarity transformation toconstruct a diagonal iteration algorithm to compute the Perron root of a nonneg-ative irreducible matrix. Through choosing the parameter, the Perron root of anirreducible nonnegative matrix can be calculated quickly and stably. The mainalgorithms are as follows:Algorithm 3.4.1 Step 4. Outputρ(A) = (rmax + rmin)/2.In Algorithm 3.4.1,δcan be taken as (3.3.1).Algorithm 3.4.2Step 0. Given a nonnegative irreducible A = (aij)n×n,ε> 0 ;Step 1. Compute ri = nLet D = diag(r1,r2,···,rn) +δIn, D?1AD := A, go to step 1;Step 4. Outputρ(A) = (rmax + rmin)/2 .As an application, we further discuss the estimation and algorithm for theminimal eigenvalue of M-matrices closely related to nonnegative matrices (or theupper and lower bounds of Z-matrices'minimal eigenvalue for real parts) anditerative determinant for M-matrices. The main results are as follows:1. Iterative Determinant for M-matricesAlgorithm 4.3.1 Step 5. Set D(m+1) = diag(r1(m ),r2(m ),···,rn(m )) +δIn, m = m + 1, go to step3;Step 6. Output'A is not an M-matrix';Step 7. Output'A is an M-matrix', D = D(0)D(1)···D(m).In Algorithm 4.3.1, we may takeδ= rmax(B(0)) +n rmin(B(0)).Algorithm 4.3.2Step 0. Input an irreducible matrix A = (aij)∈Zn×n;Step 1. If aii > 0,i∈N, go to step 2, else go to step 6;Step 2. Denote DA := diag(a11,a22,···,ann), A = DA ?P, B(0) = DA? 1P :=(bi(j0 )), D(0) = In, m = 1;Step 3. Compute B(m) = D(?m1?1)B(m?1)D(m?1), ri( m)= nj=1b(ijm ), rm(min) =mini∈N ri( m), rm(ma)x = mi∈aNx ri( m);Step 4. If rm(min) 1, go to step 6; if rm(ma)x < 1, go to step 7, else go to step 5;Step 5. Takeδ(m) = rm(ma)x +n rm(min)and set D(m+1) = diag(r1(m ),r2(m ),···,rn(m ))+δ(m)In, m = m + 1, go to step 3;Step 6. Output'A is not an M-matrix';Step 7. Output'A is an M-matrix', D = D(0)D(1)···D(m).Algorithm 4.3.3Step 0. Input an irreducible matrix A = (aij)∈Zn×n,n 4;Step 1. If aii > 0,i∈N, go to step 2, else go to step 6;Step 2. Denote DA := diag(a11,a22,···,ann), A = DA ?P, B(0) = DA? 1P := Step 4. If ri(1m )ri(2m )1, go to step 6; if ri(nm?)1ri(nm )< 1, go to step 7, elsego to step 5;Step 5. Takeδ(m) = ri(nm )+n ri(1m)and set D(m+1) = diag(r1(m ),r2(m ),···,rn(m ))+δ(m)In, m = m + 1, go to step 3;Step 6. Output'A is not an M-matrix';Step 7. Output'A is an M-matrix'.Algorithm 4.3.4Step 0. Input an irreducible matrix A = (aij)∈Zn×n,δ> 0,ε> 0;Step 1. If aii > 0,i∈N, go to step 2, else go to step 6;Step 2. s = maxi∈N aii,B(0) = sIn ? A := (b(ij0 ))n×n, D(0) = In, m = 1;Step 3. Compute B(m) = D(?m1?1)B(m?1)D(m?1), ri( m)= nj=1b(ijm ), rm(min) =mini∈N ri( m), rm(ma)x = mi∈aNx ri( m);Step 4. If rm(min) s, go to step 6; if rm(ma)x < s, go to step 7, else go to step 5;Step 5. Set D(m+1) = diag(r1,r2,···,rn) +δIn, m = m + 1, go to step 3;Step 6. Output'A is not an M-matrix';Step 7. Output'A is an M-matrix', D = D(0)D(1)···D(m).In Algorithm 4.3.4, we may takermax(B(0)) + rmin(B(0))n ? trBn (0),若rmax(B(0)) +n rmin(B(0))? trBn (0)ε,ε, else.where rmax(B(0)) = mi∈aNx (ri(B(0)) ? bi(i0 )), rmin(B(0)) = mi∈iNn (ri(B(0)) ? bi(i0 )).Algorithm 4.3.5Step 0. Input an irreducible matrix A = (aij)∈Zn×n,ε> 0;Step 1. If aii > 0,i∈N, go to step 2, else go to step 6;Step 2. Let s = maxi∈N aii, B(0) = sIn ? A := (b(ij0 ))n×n, D(0) = In, m = 1; Step 3. Compute B(m) = D(?m1?1)B(m?1)D(m?1), ri( m)= nj=1b(ijm ), rm(min) =mini∈N ri( m), rm(ma)x = mi∈aNx ri( m), ri( m)= ri( m)?bi(i0 ), rm(ma)x = mi∈aNx ri( m), rm(min) = mi∈iNn ri( m);Step 4. If rm(min) s, go to step 6; if rm(ma)x < s, go to step 7, else go to step 5;Step 5. Takerm(ma)x + rm(min)n ? trBn (0), ifrm(ma)x +n rm(min)? trBn (0)ε;ε, else,set D(m+1) = diag(r1(m ),r2(m ),···,rn(m )) +δ(m)In, m = m + 1, go to step 3;Step 6. Output'A is not an M-matrix';Step 7. Output'A is an M-matrix', D = D(0)D(1)···D(m).Algorithm 4.3.6Step 0. Input an matrix A = (aij)∈Mn(C), G+(i) = ?, i∈N;Step 1. If aii = 0, for i∈N, go to step 6;Step 2. Set A(0) = A, D(0) = In, m = 1;Step 3. Compute A(m) = A(m?1)D(m?1), ri( m)=Step 4. If N1 = {i : aii > ri( m)} = ?, go to step 6; If |N1| = n go to step 7;else go to step 5;Step 5. Computed(i m)= r|ia( mii)| ++ aa((mm)) , i = 1, 2,···, n,D(m+1) = diag{d(1m ),···, dn(m )}, m = m + 1 go to step 3;Step 6. Output'A is not an Nonsingular H-matrix';Step 7. Output'A is an Nonsingular H-matrix', D = D(0)D(1)···D(m).2. Estimation for the minimal eigenvalue of M-matrices The following results are about the estimation for the minimal eigenvalue ofnonsingular eigenvalue of M-matrices:Theorem 4.4.1 Let A∈Zn×n be a nonsingular M-matrix. For ?γ∈C(A), denote lA(γ) the real roots less than mi∈iρn {aii} of the equation i∈γ(aii ?x) =i∈γri(?A), and denotemcl(A) = min{γ∈mCi(nA) lA(γ), minΘA},Mcl(A) = min{γm∈Ca(xA) lA(γ), minΘA}.Then for the minimal eigenvalueω0(A) of A, there is the following estimationmcl(A)≤ω0(A)≤Mcl(A).Theorem 4.4.2 Let A∈Zn×n be a nonsingular M-matrix. P1(A) is the1-path coverage on the simple loops of G(A). DenoteThen for the minimal eigenvalueω0(A) of A, there is the following estimationmel(A)≤ω0(A)≤Mel(A).3.Algorithm for the minimal eigenvalue of M-matricesAlgorithm 4.5.1Step 0. Given an irreducible Z-matrix A = (aij)n×n,δ> 0,ε> 0;Step 1. Denote s = maxi∈N aii, B = sI?A := (bij), compute ri = j=n1 bij, rmin = Step 2. If rmax ? rmin <ε, go to step 4, else go to step 3;Step 3. Set D = diag(r1,r2,···,rn) +δIn, D?1BD := B, go to step 2;Step 4. Outputω= s ? (rmax + rmin)/2.In Algorithm 4.5.1, we may takeAlgorithm 4.5.2Step 0. Given an irreducible Z-matrix A = (aij)n×n,δ> 0,ε> 0;Step 1. Denote s = maxi∈N aii, B = sIn?A := (bij), compute ri = j=n1 bij, rmin =mini∈N ri, rmax = mi∈aNx ri, ri = ri ? bii, rmax = mi∈aNx ri, rmin = mi∈iNn ri;Step 2. If rmax ? rmin <ε, go to step 4, else go to step 3;Step 3. TakeSet D = diag(r1,r2,···,rn) +δIn, D?1BD := B, go to step 1;Step 4. Outputω= s ? (rmax + rmin)/2.Finally, as the end of the paper, we have an outlook on the estimation andalgorithm for the Perron root of nonnegative matrices and those for the minimaleigenvalue of nonsingular M-matrices. In the mean time, the iterative determinantof general M-matrices is looked forward.