# An Efficient Algorithm for Finding the Maximal Eigenvalue of Zero Symmetric Nonnegative Matrices

Authors: Gang Wang; Lihong Sun
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

In this paper, we propose an improved power algorithm for finding maximal eigenvalues. Without any partition, we can get the maximal eigenvalue and show that the modified power algorithm is convergent for zero symmetric reducible nonnegative matrices. Numerical results are reported to demonstrate the effectiveness of the modified power algorithm. Finally, a modified algorithm is proposed to test the positive definiteness (positive semidefiniteness) ofZ-matrices.


---

## Body

## 1. Introduction

The maximum eigenvalue problems of nonnegative matrices are important tools for matrix analysis and calculation and are widely used in many fields, such as principal component analysis, Markov chain [1], and stability of control systems [2–7]. Some researchers directly estimated the bounds of the maximum eigenvalues according to the nature of the nonnegative irreducible matrices [8–11]. Based on a geometric symmetrization of powers of matrix, Szyld [10] presented a sequence of lower bounds for the spectral radius. Dursun et al. [8] gave a sequence of upper bounds for maximal eigenvalue of a nonnegative matrix, which complemented results of [10]. Due to the complexity of the maximal eigenvalue problem, it is difficult to obtain exact solutions by means of estimation methods. Hence, some efficient algorithms for computing eigenpairs of nonnegative matrices have been proposed such as (improved) Arnoldi's algorithm [12, 13], (modified) diagonal transformation algorithm [14–17], and power algorithm [18–24]. Generally, (improved) Arnoldi’s method [12] is suitable for computing some selected eigenpairs of large asymmetrical matrices. The (modified) diagonal transformation algorithm is convergent for irreducible nonnegative matrices [15, 17]. Wood et al. [22, 23] proposed the convergent power method to calculate maximum eigenvalue of irreducible nonnegative matrices. For reducible matrices, the diagonal transformation algorithm and power algorithm may not be convergent [15, 22]. As we know, reducible matrices can be decomposed into some irreducible matrices. However, it is very costly to test the irreducibility and determine the partition for large-size matrices. Motivated by these observations, we want to establish a modified power algorithm and obtain the maximal eigenvalue of zero symmetric reducible nonnegative matrices without any partition.This paper is organized as follows. In Section2, we introduce important notation and recall fundamental results. In Section 3, we propose a modified power algorithm for computing the maximal eigenvalue of zero symmetric reducible nonnegative matrices. It is worth noting that the algorithm is convergent and does not require the partition for zero symmetric reducible nonnegative matrices. Numerical results are reported to demonstrate the effectiveness of the proposed algorithm. As an application, we can test the positive definiteness (positive semidefiniteness) of Z-matrices in Section 4.


## 2. Notation and Preliminaries

We start this section with some fundamental notion and properties of a nonnegative matrix, which are needed in the subsequent analysis.Definition 1.
(i) A matrixA=(aij)n×n∈Rn,n is called symmetric if (1)aij=aji
(ii) A matrixA=(aij)n×n∈Rn,n is called zero symmetric if (2)aij=0⇒aji=0andaji=0⇒aij=0Obviously, if a matrixA is symmetric, then A is zero symmetric. Conversely, the result may not hold.Definition 2.
A matrixA∈Rn,n is said to be reducible if there exists a permutation matrix P∈Rn,n such that(3)PAPT=A110A21A22,where A11∈Rr,r,A22∈Rn-r,n-r,A21∈Rn-r,r,1≤r≤n-1, and 0∈Rr,n-r is the zero matrix. If such a permutation matrix does not exist, A is called irreducible.Definition 3.
LetA=(aij) be a nonnegative matrix of dimension n and I⊂{1,…,n} with I=r. A submatrix AI of the matrix A with index set I is an r-dimensional submatrix of A consisting of r2 elements defined as follows: (4)AI=dij=aij,i,j∈I,where I is the number of elements of I.Definition 4.
We callσ(A) the set of all eigenvalues of A. Assume σ(A)≠∅. Then the spectral radius of A is denoted by (5)ρA=max⁡λ:λ∈σA.IfA is a nonnegative matrix, then ρ(A) is the maximal eigenvalue.LetPn={x∈Rn:xi≥0,1≤i≤n} and int⁡(Pn)={x∈Rn:xi>0,1≤i≤n}. For any nonnegative column vector x∈Rn, we define ϕ:Pn→P1 by (6)ϕx=∑i=1nxi.Now, we give the power algorithm [22, 23] of irreducible nonnegative matrices as follows.Algorithm 5.
⁡
Step  1. Choose x(1)∈int⁡(Pn), α>0, ϵ>0, and a unit matrix I,k=1.
Step  2. Compute (7)yk=A+αIxk,λ¯k=max1≤i≤n⁡ykixki,λ_k=min1≤i≤n⁡ykixki.
Step  3. If λ¯k-λ_k<ϵ, stop. Output the maximal eigenvalue ρ(A)=1/2(λ¯k+λ_k)-α. Otherwise, set k=k+1 and compute (8)xk+1=ykϕyk,
and go to Step 2.For irreducible nonnegative matrices, we have the following convergent theorems.Lemma 6 (Theorem 9 of [22]).
IfA is an irreducible nonnegative matrix, then the matrix qI+A is primitive, where q>0 and I is a unit matrix.Lemma 7 (Theorem 8 of [22]).
{ λ ¯ k } , { λ _ k } generated by Algorithm 5 converge to ρ(A), if and only if the irreducible nonnegative matrix A is primitive.


## 3. Modified Power Algorithm for the Maximal Eigenvalue of Zero Symmetric Nonnegative Matrices

In this section, we give the modified power algorithm for computing the maximal eigenvalue of zero symmetric reducible nonnegative matrices without any partition. Furthermore, we demonstrate that this algorithm is convergent by Theorem10. We state the algorithm as follows.Algorithm 8.
⁡
Step  1. Choose x(1)∈int⁡(Pn), and α>0, ϵ>0, and k=1.
Step  2. Compute (9)yk=A+αIxk,λ¯k=max1≤i≤n⁡ykixki.
Step  3. If (λ¯k-1-λ¯k)<ϵ, stop. Output the maximal eigenvalue ρ(A)=λ¯k-α. Otherwise, set k=k+1 and compute (10)xk+1=ykϕyk,
and go to Step 2.We show that the sequence{λ¯k} generated by Algorithm 8 is convergent and the limit is the maximal eigenvalue for any zero symmetric nonnegative matrices. In what follows, we give the following lemma.Lemma 9.
LetA=(aij)n×n be a zero symmetric reducible nonnegative matrix. Then, we have the following results:
(I) There exists a partition{I1,I2,…,Is} of {1,2,…,n} such that each induced matrix AIi, i=1,2,…,s, either is irreducible or is a zero matrix
(II) Forx∈Rn, there exists an n×n permutation P such that (11)PAx=AI1xI1AI2xI2⋮AIkxIs(III) ρ(A)=max1≤i≤sρ(AIi).For a zero symmetric reducible nonnegative matrixA, by Lemma 9, it holds that (12)ρA=max⁡ρAI1,ρAIi,…,ρAIsAs we know, it is very costly to determine the partition for large-size reducible matrices. Fortunately, Algorithm 8 is not necessary to decompose the matrix and can compute the maximal eigenvalue of each block matrix.Theorem 10.
Suppose thatA is a zero symmetric reducible nonnegative matrix and the sequence {λ¯k} is generated by Algorithm 8. Then, ρ(A)=limk→∞λ¯k.Proof.
For the sequence{λ¯k}, it holds that {λ¯k} is monotonously decreasing and bounded to the below. According to Algorithm 8, it is easy to get λ¯k≥α. Now, we show that {λ¯k} is a decreasing sequence. For any k≥1, by Algorithm 8, we have(13)yk=A+αIxk≤λ¯kxk.So, (14)xk+1=ykϕyk≤λ¯kxkϕyk.Since A is nonnegative, we get (15)A+αIxk+1≤A+αIλ¯kxkϕyk=λ¯kA+αIxkϕyk=λ¯kykϕyk=λ¯kxk+1.For i=1,2,⋯,n, one has (16)λ¯k≥max1≤i≤n⁡A+αIxk+1ixk+1i=max1≤i≤n⁡yk+1ixk+1i=λ¯k+1,which means that {λ¯k} is a decreasing sequence. So, the sequence {λ¯k} is convergent. Hence, there exists λ¯ such that λ¯k→λ¯ when k→∞. Next, we show that λ¯=ρ(A)+α. Without loss of generality, we assume that the matrix A+αI is stated as follows: (17)A+αI=AI1+αII10⋯00AI2+αII2⋯0⋮⋮⋱⋮00⋯AIs+αIIs,where each block AIi+αIIi(i=1,2,…,s) is square and either is primitive or is a 1×1 unit matrix. It follows from Lemma 9 that (18)ρA=max⁡ρAI1,ρAI2,…,ρAIs.We divide the proof into two parts.
Case  1. A has a unique maximal eigenvalue. Without loss of generality, we assume (19)ρA=ρAI1>max⁡ρAI2,…,ρAIsi=2,3,…,s.Let λ¯k be the maximum value of matrix A+αI generated by Algorithm 8. Let (λ¯ki,(x(k))Ii)(i=1,2,…,s) be the maximum value and eigenvector of (AIi+αIIi) and let ρ(AIi) be the maximum eigenvalue of AIi(i=1,2,…,s). Set (20)βi=ρAI1-ρAIii=2,3,…,s.Obviously, βi>0. Taking into account that each block AIi+αIIi is primitive, from Lemma 7, we have (21)limk→∞⁡λ¯ki=ρAIi+αi=1,2,…,s.Since AI1+αII1 is primitive and x(k+1)=y(k)/ϕ(y(k)), from Algorithm 8, we obtain (22)ykI1=AI1+αII1xkI1>0.For 0<ϵ<min2≤i≤sβi,∃K, when k>K, we have (23)λ¯ki-ρAIi-α<ϵ,and, furthermore,(24)ρAIi+α+ϵ>λ¯ki,∀i=1,2,…,s.On the other hand, since ρ(AI1)-ρ(AIi)=βi and 0<ϵ<βi, it holds that (25)ρAI1+α>ρAIi+α+ϵ,∀i=2,…,s.For k>K, it follows from (24) that (26)λ¯k1≥ρAI1+α>λ¯ki,∀i=2,…,s,and, equivalently, (27)λ¯k1>λ¯ki,∀i=2,…,s.It follows from λ¯k=max⁡{λ¯k1,λ¯k2,…,λ¯ks} that (28)λ¯k1=λ¯k,∀k>K.From Lemma 7, we obtain (29)ρAI1+α=limk→∞⁡λ¯k1=limk→∞⁡λ¯k=ρA+α.
Case  2. A has two maximal eigenvalues, that is, (30)ρA=ρAI1=ρAI2>max⁡ρAI1,ρAI2,…,ρAIsi=3,4,…,s.According to the above analysis, ∃K, when k>K, we know (31)λ¯k1>λ¯kiorλ¯k2>λ¯ki,i=3,4,…,s.For k>K, we deduce λ¯k1=λ¯k or λ¯k2=λ¯k. It follows from Lemma 7 that (32)limk→∞⁡λ¯k1=ρAI1+αorlimk→∞⁡λ¯k2=ρAI2+α,and, equivalently, (33)ρAI1+α=limk→∞⁡λ¯k1=limk→∞⁡λ¯k=ρA+αorρAI2+α=limk→∞⁡λ¯k2=limk→∞⁡λ¯k=ρA+α.When A has more than two maximal eigenvalues, we repeat the above process and can obtain the same convergent conclusions.Remark 11.
We are able to obtain an eigenvector corresponding toρ(A) as follows. Since the sequence {x(k)} is bounded, it has an accumulation point. Suppose that x∗ is an accumulation point of {x(k)}. Define x¯∗ by(34)x¯j∗=xj∗,j∈I∗,0,otherwise,j=1,…,n,where I∗={1≤j≤n:(Ax∗)j=ρ(A)xj∗andxj∗>0}. By Lemma 9, x¯∗ is an eigenvector corresponding to ρ(A) when x¯∗≠0.In the following, we report numerical results for Algorithm8. In order to show this algorithm is efficient, we compare it with improved Arnoldi's algorithm in [13] and the modified diagonal algorithm in [17]. For Algorithm 8, we stop the iteration as long as |λ¯k-1-λ¯k|≤ε, ε=10-10. (Detailed information is in Tables 1 and 2.)Table 1
Comparisons of Algorithm8 and improved Arnoldi's algorithm in [13].
Algorithm8 Improved Arnoldi Algorithm n ρ c p u ( s ) c p u ( s )  600 2.5024e+02 0.032054 0.129545  1200 9.9961e+02 0.092272 0.225116  1800 1.4999e+03 0.186048 0.400719  2400 2.0000e+03 0.295846 0.678812  3000 2.5001e+03 0.459340 0.990805  6000 3.9026e+03 1.248525 2.255433  9000 5.0004e+03 3.812981 5.945294  12000 7.4995e+03 7.414798 11.958425Table 2
Comparisons of Algorithm8 and the modified diagonal algorithm in [17].
Algorithm8 Modified diagonal algorithm n ρ c p u ( s ) c p u ( s )  500 5.0033e+02 0.030557 1.207591  1000 1.0007e+03 0.089176 7.937777  1500 1.4994e+03 0.154085 21.985712  2000 2.0000e+03 0.263202 47.984927  2500 2.4994e+03 0.415304 91.207171  3000 3.0004e+03 0.594669 150.432479All testingn×n matrices B are generated as follows: Give an integer p and generate randomly three positive matrices BI1,BI2,BI3. Let I1={1,2,…,p}, I2={p+1,…,2p}, and I3={2p+1,…,3p}. Then, define B=(BI1,BI2,BI3), where n=3p, other elements being zero. Clearly, B is zero symmetric reducible. Algorithm 8 is implemented in MATLAB (R2011a) and all the numerical computations are conducted using an Intel 3.60 GHz computer with 8 GB of RAM. In Table 1, the CPU time is the average of 10 instances for each n. From Table 1, we can see that both algorithms can find maximal eigenvalues of the testing matrices but Algorithm 8 uses much less CPU time than improved Arnoldi's algorithm in [13], especially for large-size matrices.Considering that the matrix is nonnegative and irreducible for the modified diagonal algorithm in [17], all testing matrices B are positive matrices generated randomly in Table 2. Compared with the modified diagonal algorithm in [17], the Algorithm 8 has better execution efficiency in CPU time.


## 4. Applications

In this section, we give an application of Algorithm8 for testing the positive definiteness (positive semidefiniteness) for large-size Z-matrices. We recall some definitions and notations about Z-matrices and M-matrices.Definition 12.
A matrixA∈Rn,n is called a Z-matrix if it can be written as A=cI-B, where I is a unit matrix and B is a nonnegative matrix. Furthermore, if c≥ρ(B), then A is said to be an M-matrix; if c>ρ(B), then A is said to be a strong M-matrix.LetA∈Rn,n and x∈Rn. Define a quadratic polynomial form fA(x) as follows: (35)fAx≔∑i,j=1naijxixj.Definition 13.
(i)A is called positive definite if fA(x)>0 for all x∈Rn,x≠0.
(ii)A is called positive semidefinite if fA(x)≥0 for all x∈RnAs we know, for a symmetric matrixA, A is positive definite if and only if all of its eigenvalues are positive, and A is positive semidefinite if and only if all of its eigenvalues are nonnegative. For an asymmetric Z-matrix A, we can do the following transformation to verify whether A is a positive definite (semidefinite) matrix.For aZ-matrix A∈Rn,n, consider the following optimization problem: (36)v∗=min⁡fAx:∑i=1nxi2=1Clearly, we observe that A is positive definite if and only if v∗>0, and A is positive semidefinite if and only if v∗≥0. Set (37)c¯=max⁡aii:1≤i≤n,c_=min⁡aii:1≤i≤n.Then, A can be written as A=c¯I-B, where B is a nonnegative matrix.Given indicesr1,r2, where r1,r2=1,2,…,n, let S(r1,r2) be the set of all permutations of the indices r1,r2. For any π(r1,r2)∈S(r1,r2), let (38)b¯πr1,r2=12∑σr1,r2∈Sr1,r2bσr1,r2and define(39)B¯=b¯ij,1≤i,j≤n.Hence,B¯ is a symmetrized matrix of B. For any x∈Rn, set (40)fBx≔∑i,j=1nbijxixj,andfB¯x≔∑i,j=1nb¯ijxixj.Clearly, we have that fB¯(x)=fB(x). Therefore, (41)v∗=min⁡fAx:∑i=1nxi2=1=min⁡fc¯I-Bx:∑i=1nxi2=1=min⁡c¯-fBx:∑i=1nxi2=1=min⁡c¯-fB¯x:∑i=1nxi2=1=c¯-max⁡fB¯x:∑i=1nxi2=1=c¯-ρB¯.From the above analysis, we can propose the following algorithm for testing the positive definiteness (positive semidefiniteness) ofZ-matrices.Algorithm 14.
⁡
Step  1. Given a Z-matrix A∈Rn,n, compute (42)c¯=max⁡aii:1≤i≤n,c_=min⁡aii:1≤i≤n.
Ifc_<0, then A is not positive semidefinite and stop. Otherwise, go to the next step.
Step  2. Let B=c¯I-A and compute its symmetrized matrix B¯. By Algorithm 8, compute the spectral radius ρ(B¯).
Step  3. Let v∗=c¯-ρ(B¯). If v∗>0, A is positive definite. If v∗≥0, A is positive semidefinite. Otherwise, it is indefinite.


## 5. Conclusions

In this paper, a modified power algorithm was proposed for finding the maximal eigenvalue of zero symmetric nonnegative matrices. The modified power algorithm has the following important properties: (1) the convergence property is guaranteed for any zero symmetric nonnegative matrices and (2) it gets the maximal eigenvalue without any partition. Finally, we proposed Algorithm14 to test the positive definiteness (positive semidefiniteness) of Z-matrices.



---

*Source: 6438106-2018-11-29.xml*