On the intersection of the classes of doubly diagonally dominant matrices and S-strictly diagonally dominant matrices

XX Congreso de Ecuaciones Diferenciales y Aplicaciones X Congreso de Matem´ atica Aplicada Sevilla, 24-28 septiembre 2007 (pp. 1–7) On the intersection of the classes of doubly diagonally dominant matrices and S-strictly diagonally dominant matrices F. Pedroche1,R.Bru 1,L.Cvetkovi ´ c2,V.Kosti ´ c2 1Institut de Matem`atica Multidisciplinar, Universitat Polit`ecnica de Val`encia. Cam´ıdeVeras/n. 46022 Val`encia. Spain. E-mails: [email protected], [email protected]. 2Department of Mathematics and Informatics, Faculty of Science, University of Novi Sad. Serbia, 21000 Novi Sad. E-mails: [email protected], [email protected]. Keywords: H-matrices, Doubly diagonally matrices, S-strictly diagonally dominant matrices Abstract We denote by H0the subclass of H-matrices consisting of all the matrices that lay simultaneously on the classes of doubly diagonally dominant (DDD) matrices (A= [aij ]∈Cn×n:|aii||ajj|≥k=i|aik|k=j|ajk|,i =j)andS-strictly diagonally dominant (S-SDD) matrices. Notice that strictly doubly diagonally dominant matrices (also called Ostrowsky matrices) are a subclass of H0. Strictly diagonally dominant matrices (SDD) are also a subclass of H0. In this paper we analyze some properties of the class H0= DDD ∩S-SDD. 1 Introduction In this paper we analyze some properties of the matrices that lay simultaneously on the classes of doubly diagonally dominant (DDD) matrices, see [11], and S-strictly diagonally dominant (S-SDD) matrices; see [4], [15]. This class, that we denote here by H0= DDD ∩S-SDD is a subclass of H-matrices. In several practical applications H-matrices play a key role; e.g., in the numerical solution of Euler equations in fluid dynamics [7], in nonlinear boundary problems and in the Lyapounov stability analysis for large scale evolution systems (see [14] and the references therein, for more details). H-matrices were defined by Ostrowsky in [13] as a generalization of M-Matrices. H-matrices and M-matrices are called this way in homage to Hadamard and Minkowsky, respectively [15]. We recall that a nonsingular matrix Ahaving all non-positive off-diagonal entries is called an M-matrix if the inverse is (entry-wise) nonnegative, i.e., A−1≥O; see, e.g., 1 F. Pedroche, R. Bru, L. Cvetkovi´c, V.Kosti´c [1] for more characterizations. For any matrix A=(aij)∈Rn×n,itscomparison matrix A=(αij) can be defined by αii =|aii|,α ij =−|aij|,i=j. AmatrixAis said to be an H-matrix if Ais a nonsingular M-matrix. In particular, Ais a nonsingular H-matrix if and only if it is (strictly) generalized (row) diagonally dominant, i.e., |aii|wi> i=j |aij|wj,i=1,...,n, (1) for some positive vector w=(w1,...,w n)T. ThisisequivalenttosaythatAis an H-matrix if and only if there exists a positive diagonal matrix W=diag(w1,w 2,...,w n) such that AW is an strictly (row) diagonally dominant (SDD) matrix. Some useful characterizations of H-matrices (see, for example, [10], [8], [14], [9], [5]) are based on devising adequate scaling matrices W. A different strategy to the problem of finding classes of H-matrices resides in describing subclasses of H-matrices which are easily characterizable. Following this approach some new subclasses of H-matrices were introduced in [4]. In this paper we focus on the subclass of H0-matrices. It is also interesting to note that SDD matrices are the simplest case for this class; these ideas are depicted in Figure 1 below. S-SDD SDD Ostr DDD DDD H0 H Figure 1: DDD matrices and some subclasses of H-matrices 2S-SDD matrices We begin with some definitions which can be found, e.g., in [2], [4], [6], [15]. Definition 1 Given a matrix A=(aij)∈Cn×n, let us define the ith deleted absolute row sum as ri(A)= n  j=i, j=1 |aij|,∀i=1,2,...,n, 2 On the intersection of the classes of DDD and S-SDD and the ith deleted absolute row-sum with columns in the set of indices S={i1,i 2,...}⊆N:= {1,2,...n}as rS i(A)=  j=i, j∈S |aij|,∀i=1,2,...,n. Given any nonempty set of indices S⊆Nwe denote its complement in Nby ¯ S:= N\S. Note that for any A=(aij)∈Cn×nwe have that ri(A)=rS i(A)+r¯ S i(A). Definition 2 Given a matrix A=(aij)∈Cn×n,n≥2and given a nonempty subset S of {1,2,...,n},thenAis an S-strictly diagonally dominant matrix if the following two conditions hold i)|aii|>r S i(A)∀i∈S, ii)(|aii|−rS i(A)) (|ajj|−r¯ S j(A)) >r¯ S i(A)rS j(A)∀i∈S, ∀j∈¯ S. (2) It was shown in [6] that an S-strictly diagonally dominant matrix (S-SDD) is a nonsingular H-matrix. In particular, when S={1,2,...n},thenA=(aij)∈Cn×nis a strictly diagonally dominant matrix (SDD). It is easy to show that an SDD matrix is an S-SDD matrix for any proper subset S, but the converse is not always true [3]. Notice that condition 1) of definition 2 implies that the diagonal of any S-SDD matrix is nonzero. We also note that condition 1) can be substituted for |aii|>r S i(A), for some i∈S, since the condition 2) ensures that 1) will be satisfied for all i∈S; see [4]. The class of S-SDD can be expressed equivalently in the following way. For arbitrary nonempty proper set of indices Slet us define the interval JA(S)as JA(S):=(µS 1(A),µ S 2(A)),(3) where µS 1(A):=max i∈S rS i(A) |aii|−rS i(A)and µS 2(A):= min j∈S,rS j(A)=0 |ajj|−rS j(A) rS j(A).(4) By convention, when S=∅or S=Nwe define JA(S)=(0,+∞). Furthermore, when rS j(A)=0,∀j∈Sthen we take µS 2(A)=+∞. The next lemma, which is proved in [2], shows another characterization of S-SDD matrices. Here we denote by A[S] the principal submatrix of Awith indices from the set S. Lemma 1 Given S∈N,letA[S]and A[S]be strictly diagonally dominant matrices. Then A∈Cn×nis an S-SDD matrix if and only if the interval JA(S)given by (3) is nonempty. 3 Doubly diagonally dominant matrices The class of DDD matrices, see [11], is defined as follows. {A=[aij]∈Cn×n:|aii||ajj|≥ri(A)rj(A),i=j}(5) 3 F. Pedroche, R. Bru, L. Cvetkovi´c, V.Kosti´c Example 1 The matrices 00 00 and −10 00 are DDD matrices. Example 2 The matrix   110 1 211 2 01 21   isDDDbutitisnotintotheclassH0, i.e., is not an S-SDD matrix for any S. But it is a nonsingular Hmatrix. We remark that we are interested in DDD matrices with at least one equality in (5). Otherwise, we would have SDDD (Ostrowsky) matrices or simply SDD matrices, which are known classes. 4H0-matrices In order to study the class H0= DDD ∩S-SDD we can adopt three points of view: a) we can stay in the DDD class and look for conditions to be in the class S-SDD, b) we can stay in the class S-SDD and look for conditions to be in the DDD class and c) we can impose all the conditions to be in the class DDD ∩S-SDD and try to simplify the derived relations. In this communication we explore the options a) and c). Before giving sufficient conditions for a DDD matrix to be an S-SDD matrix we establish the following result. Lemma 2 Let A∈Cn×nand S⊆N:= {1,2,...,n}.If 1) A[S]and A[S]are SDD matrices 2) rS i(A)rj(A)>r S j(A)|aii|,∀i∈S, ∀j∈S 3) ri(A)rS j(A)>r S i(A)|ajj|,∀i∈S, ∀j∈S then Ais an S-SDD matrix. Proof We first note that 1) implies: |aii|>r S i(A),∀i∈Sand |ajj|>r S j(A),∀j∈S. According to Lemma 1, we only have to show that the interval JA(S) given by equation (3) is nonempty. Note that condition 2) can be written as rS i(A)rS j(A)>r S j(A)|aii|−rS i(A),∀i∈S, ∀j∈S(6) and since A[S] is SDD, equation (6) implies that rS i(A)rS j(A)>0,∀i∈S, ∀j∈S. Now, from (6) and the definition of µS 1(A), see equation (4), we conclude that µS 1(A)>rS i(A)rS j(A) rS i(A)rS j(A),∀i∈S, ∀j∈S 4 On the intersection of the classes of DDD and S-SDD In a similar way, condition 3) yields to rS i(A)rS j(A)>r S i(A)|ajj|−rS j(A),∀i∈S, ∀j∈S(7) and this equation jointly with the definition of µS 2(A), equation (4), leads to µS 2(A)<rS i(A)rS j(A) rS i(A)rS j(A),∀i∈S, ∀j∈S and the proof follows. In the following result we show that when Ais a DDD matrix then we can replace the condition 1) of Lemma 2 by the simple condition |aii|>r S i(A)forsomei∈S. Proposition 1 Let A∈Cn×nbe a DDD matrix. Let S⊆N:= {1,2,...,n}.If 1) |aii|>r S i(A)for some i∈S 2) rS i(A)rj(A)>r S j(A)|aii|,∀i∈S, ∀j∈S 3) ri(A)rS j(A)>r S i(A)|ajj|,∀i∈S, ∀j∈S then Ais an S-SDD matrix. Proof Since Ais a DDD matrix we have that |aii||ajj|≥ri(A)rj(A),i=j Note that |aii||ajj|≥ri(A)rj(A) =[rS i(A)+r¯ S i(A)] [rS j(A)+r¯ S j(A)] =rS i(A)rS j(A)+rS i(A)r¯ S j(A)+r¯ S i(A)rS j(A)+r¯ S i(A)r¯ S j(A) =rS i(A)rj(A)+rS i(A)r¯ S j(A)−rS i(A)r¯ S j(A)+r¯ S i(A)rS j(A)+r¯ S i(A)r¯ S j(A) =rS i(A)rj(A)+ri(A)r¯ S j(A)−rS i(A)r¯ S j(A)+r¯ S i(A)rS j(A) (8) and using conditions 2) and 3) we conclude |aii||ajj|>r¯ S j(A)|aii|+rS i(A)|ajj|−rS i(A)r¯ S j(A)+r¯ S i(A)rS j(A) from which we obtain (|aii|−rS i(A)) (|ajj|−r¯ S j(A)) >r¯ S i(A)rS j(A) and this holds ∀i∈S, ∀j∈S. In conclusion, we have that Ais an S-SDD matrix. 5 F. Pedroche, R. Bru, L. Cvetkovi´c, V.Kosti´c In the next section we will show some properties of the matrices that lay on the class H0. 4.1 Set of pairs of indices In this section we consider N:= {1,2,...,n}, such that n≥2. Let us define the set N2={(i, j):i, j ∈N,i =j}. Obviously, card(N2)=n(n−1) 2. Definition 3 Let A∈Cn×nbe a DDD matrix such that n≥2.Wedefinethesetofpairs of indices E(A)={(i, j)∈N2:|aii||ajj|=ri(A)rj(A)}. We denote its complement by E(A)=N2\E(A). Example 3 Given the following DDD matrix A=  10.50.5 0.510.5 012   we have N2={(1,2),(1,3),(2,3)}and E(A)={(1,2)}. Definition 4 We define the class of matrices H0(S)which is formed by square matrices Aof order nsuch that they are simultaneously DDD matrices and S-SDD matrices for some proper subset S⊆N. Example 4 The matrix given by example 3 is DDD and {1,2}-SDD, therefore it belongs to the class H0({1,2}). Lemma 3 Let A∈Cn×nsuch that A∈H0(S)for some proper subset Sand such that there exists i∈N:ri(A)=0.Then(i, j)∈E(A),∀j∈N. Proof Let us suppose that there exists j∈N:(i, j)∈E(A). Therefore |aii||ajj|= ri(A)rj(A) = 0 which implies aii =0orajj = 0. But this is a contradiction because Ais a nonsingular H-matrix. Remark 1 Note that this lemma still holds when Ais a DDD matrix whose diagonal entries are nonzero. Lemma 4 Let A∈Cn×nsuch that A∈H0(S)for some proper subset Sand such that there exists i∈S:|aii|=ri(A).Then(i, j)∈E(A),∀j∈S. Proof Let us suppose that there exists j∈S:(i, j)∈E(A). Therefore |aii||ajj|= ri(A)rj(A) and using the hypothesis |aii|=ri(A) we conclude that |ajj|=rj(A). Therefore we have (|aii|−rS i(A)) (|ajj|−r¯ S j(A)) = r¯ S i(A)rS j(A),with i∈S, j ∈S and the condition ii) of the definition of S-SDD matrices is not satisfied. Therefore A does not belong to H0(S), which is a contradiction. The counterpart of the previous lemma is the following. 6 On the intersection of the classes of DDD and S-SDD Lemma 5 Let A∈Cn×nsuch that A∈H0(S)for some proper subset Sand such that there exists i∈S:|aii|=ri(A).Then(i, j)∈E(A),∀j∈S. As a consequence of the two previous results we have the following. Proposition 2 Let A∈Cn×nsuch that A∈H0(S)and let Tbe the set of indices T={i∈N:|aii|=ri(A)}. Then T⊆Sor T⊆S. Acknowledgement F. Pedroche and R. Bru are supported by the Spanish DGI grant MTM2004-02998. L. Cvetkovi´candV.Kosti´c are supported by the Provincial Secretariat of Science and Technological Development of Vojvodina, Serbia, grant 01123. Bibliography [1] A. Berman, and R. J. Plemmons, Nonnegative matrices in the mathematical sciences,Academic Press, New York. Reprinted and updated, SIAM, Philadelphia, 1994. [2] R. Bru, L. Cvetkovic., V. Kostic and F. Pedroche. Sums of S-strictly diagonally dominant matrices Electron. Trans. Numer. Anal., 2007 (submitted). [3] R. Bru, F. Pedroche, and D. B. Szyld. Subdirect sums of S-Strictly Diagonally Dominant matrices, Electron. J. Linear Algebra, 15:201–209, 2006. [4] L. Cvetkovic. H-matrix theory vs. eigenvalue localization Numerical Algorithms, 42: 229-245, 2006. [5] L. Cvetkovic and V. Kostic. New criteria for identifying H-matrices, J. Comput. Appl. Math., 180:265–278, 2005. [6] L.Cvetkovic,V.KosticandR.S.Varga.AnewGerˇsgoring-type eigenvalue inclusion set, Electron. Trans. Numer. Anal., 18:73–80, 2004. [7] L. Elsner and V. Mehrmann. Convergence of Block-Iterative Methods for Linear Systems Arising in the Numerical Solution of Euler Equations. Numerische Mathematik, Vol. 59, pp. 541-560, 1991. [8] T. B. Gan, and T. Z. Huang. Simple criteria for nonsingular H-matrices, Linear Algebra Appl., 374:317–326, 2003. [9] T-Z Huang, J-S Leng, E.L. Wachspress and Y. Y. Tang. Characterization of H-matrices. Computers & Mathematics with applications, 48 (10-11): 1587-1601, 2004. [10] B. Li, L. Li, M. Harada, H. Niki, M. J. Tsatsomeros, An iterative criterion for H-matrices, Linear Algebra Appl., 271:179–190, 1998. [11] B. Li and M. J. Tsatsomeros. Doubly diagonally dominant matrices. Linear Algebra and its Applications, 261:221–235, 1997. [12] J. Liu and Y. Huang. Some properties on Schur complements of H-matrices and diagonally dominant matrices. Linear Algebra and its Applications, 389:365–380, 2004. [13] A. M. Ostrowski, (1937), ¨ Uber die Determinanten mit ¨uberwiegender Hauptdiagonale, Comentarii Mathematici Helvetici 10 pp. 69–96. [14] P. Spiteri. A new characterization of M-matrices and H-matrices. BIT Numerical Mathematics, 43:1019-1032, 2003. [15] R. S. Varga. Gerˇsgorin and his circles. Springer Series in Computational Mathematics, vol. 36. Springer, Berlin, Heidelberg, 2004. 7