# A New Upper Bound forA-1 of a Strictly α-Diagonally Dominant M-Matrix

Authors: Zhanshan Yang; Bing Zheng; Xilan Liu
Journal: Advances in Numerical Analysis
 (2013)

---

## Abstract

A new upper bound forA-1 of a real strictly diagonally dominant M-matrix A is present, and a new lower bound of the smallest eigenvalue λminA of A is given, which improved the results in the literature. Furthermore, an upper bound for A-1 of a real strictly α-diagonally dominant M-matrix is shown.


---

## Body

## 1. Introduction

The estimation for the bound for the norm∥A-1∥ of a real invertible n×n matrix A is important in numerical analysis, so many researchers were devoted to studying this kind of problems. For example, Varah [1] discussed the bound for the infinity norm ∥A-1∥∞ of a strictly diagonally dominant matrix A=(aij)n×n∈Rn×n and obtained the following estimation:
(1)∥A-1∥∞≤maxi{1|aii|-∑j=1,j≠i‍|aij|},i∈N.
After that Varga [2] extended the result of [1] to H-matrices. Evidently, the upper bound for ∥A-1∥∞ in (1) only involves the entries in the matrix A. If the diagonal dominance of A is weak, that is, min{|aii|-∑j=1,j≠i|aij|} is small, then the bound given by (1) may be large. For this reason, some authors were devoted to improving the result of (1). Recently, Cheng and Huang [3] presented a more compacted upper bound for a strictly diagonally dominant M-matrix
(2)∥A-1∥∞≤1a11(1-u1d1)+∑i=2n‍[1aii(1-uidi)∏j=1i-1‍(1+uj1-ujlj)],
and then Wang [4] further improved this bound and gave the following result:
(3)∥A-1∥∞≤1a11(1-u1d1)+∑i=2n‍[1aii(1-uidi)∏j=1i-1‍11-ujlj],
where notations in (2) and (3) have the same meanings as those used in this paper, which will be shown later.In this paper, we present a new upper bound∥A-1∥∞ of a strictly diagonally dominant matrix A=(aij)n×n∈Rn×n, which is better than that obtained by Wang, and a new lower bound of the smallest eigenvalue q(A) of A is also obtained. In addition, an upper bound for ∥A-1∥∞ of a strictly α-diagonal dominant matrix is presented. To our knowledge, little has been done for upper bound of strictly α-diagonal dominant matrices. Further, examples are given to illustrate the performance of our results.Next, we introduce some notations and definitions. As usual, letI be an identity matrix of order n. If there exists an n×n nonnegative matrix B and a real number a such that A=aI-B with a>ρ(B), then A is called a nonsingular M-matrix, where ρ(B) is the spectral radius of the nonnegative matrix B. It is well known that the inverse matrix A-1 of a M-matrix A is nonnegative and, therefore, 1/ρ(A-1) is a positive eigenvalue of A related to the Perron eigenvalue of the nonnegative matrix A-1. If q(A) denotes the minimum of the real parts of the eigenvalues of A, that is, q(A)=a-ρ(B), then q(A)=1/ρ(A-1). For further properties of the M-matrix A, we refer the readers to [5–7].Ann×n matrix A=(aij) is called a strictly diagonally dominant matrix if |aii|>∑j=1,j≠i|aij| for i∈N. Let
(4)Ri(A)=∑j=1,j≠in‍|aij|,ri(A)=∑j=1n‍|aij|,di=1|aii|∑j=1,j≠in‍|aij|,J(A)={i∈N:di<1},ui=1|aii|∑j=i+1n‍|aij|,lk=maxk≤i≤n∑j≠i,k≤j≤n‍|aij||aii|,ln=un=0,wij=|aij||aii|-∑k≠i,j‍|aik|,i≠j,j<k≤n,wi=maxj≠i{wij},Ci(A)=∑j=1,j≠in‍|aji|,mij=|aij|+∑k≠i,j‍|aik|wk|aii|,i≠j,j<k≤n,
where N is the set of positive integers. For an n×n matrix A, the principal matrix of A formed by rows and columns with indices between n1 and n2 is denoted by A(n1,n2).Definition 1 (see [8]).
A
∈
R
n
×
n is weakly chained diagonally dominant if, for all i∈N, di≤1 and J(A)≠∅ and for all i∈N, i∉J(A), there exist indices i1,i2,…,ik in N with airir+1≠0, 0≤r≤k-1, where i0=i and ik∈J(A).Definition 2  (see [9]).
LetA∈Rn×n, A is strictly diagonally dominant if J(A)=N.Obviously, ifA∈Rn×n is a strictly diagonally dominant matrix, then A be a weakly chained diagonally dominant matrix.Definition 3 (see [9]).
A
∈
R
n
×
n is an L-matrix if, for all i,j∈N with i≠j, aij≤0 and aii>0.Definition 4 (see [10]).
LetA∈Rn×n; if there exist α∈[0,1], such that
(5)|aii|≥αRi(A)+(1-α)Ci(A),
for all i∈N, then A is said to be an α-diagonal dominant matrix, denoted by Dnα.Remark 5.
By Definition4, we know that A is just a diagonal dominant matrix while α=1.Definition 6.
If all the inequalities in (5) strictly hold, then A is said to be strictly α-diagonal dominant matrix (SDnα).


## 2. Estimation for an Upper Bound for∥A-1∥∞ of Strictly Diagonally Dominant M-Matrix

We state some lemmas before giving a new upper bound for∥A-1∥∞.Lemma 7 (see [3]).
LetA=(aij) be an n×n weakly chained diagonally dominant M-matrix, B=A(2,n), A-1=(αij)i,j=1n, and B-1=(βij)i,j=2n. Then, for i,j=1,2,…,n,
(6)α11=1Δ,αi1=1Δ∑k=2n‍βik(-ak1),α1j=1Δ∑k=2n‍βkj(-a1k),αij=βij+α1j∑k=2n‍βik(-ak1),
where
(7)Δ=a11-∑k=2n‍a1k∑i=2n‍βkiai1>0.
Furthermore, if J(A)=N, then Δ≥a11(1-d1l1)≥a11(1-d1).Lemma 8 (see [11]).
A weakly chained diagonally dominantL-matrix is a nonsingular M-matrix.Lemma 9 (see [11]).
LetA=(aij) be an n×n weakly chained diagonally dominant M-matrix; then B=A(2,n) is an (n-1)×(n-1) weakly chained diagonally dominant M-matrix; that is, B-1=(βij) exists and βij≥0(i,j=2,3,…,n).Lemma 10 (see [11]).
LetA=(aij) be an n×n weakly chained diagonally dominant M-matrix, A-1=(αij). Then, for i≠j,
(8)αij≤diαjj≤αjj.Lemma 11 (see [11]).
LetA=(aij) be an n×n row strictly diagonally dominant M-matrix; then
(9)Δ≥a11(1-d1l1)>a11(1-d1)>0.Lemma 12 (see [2]).
LetA=(aij) be an n×n row strictly diagonally dominant M-matrix; then, for A-1=(αij)i,j=1n, we have
(10)1aii≤αii≤1aii-∑j≠i‍|aij|mji.Lemma 13 (see [1]).
LetA=(aij) be an n×n weakly chained diagonally dominant M-matrix, A-1=(αij), and q=q(A),  N=1,2,…,n. Then
(11)q≤mini∈N{aii},q≤maxi∈N{∑j∈N‍aij},q≥mini∈N{∑j∈N‍aij},1M≤q≤1m,
where
(12)M=maxi∈N{∑j∈N‍αij}=∥A-1∥∞,m=mini∈N{∑j∈N‍αij}.Now we give an upper bound for∥A-1∥∞ and q(A) of a strictly diagonally dominant M-matrix A by the following theorem.Theorem 14.
LetA=(aij) be an n×n row strictly diagonally dominant M-matrix, A-1=(αij). Then
(13)∥A-1∥∞≤1a11-∑k=2n‍|a1k|mk1+∑i=2n‍[1aii-∑k≠i,i≤k≤nn‍|aik|mki∏j=1i-1‍11-ujlj].Proof.
We prove this theorem by induction.(1)
Letri=∑j=1nαij,  B=A(2,n), MA=∥A-1∥∞, and MB=∥B-1∥∞. Then
(14)MA=max{ri:i∈N},MB=max{∑j=2n‍βij:2≤i≤n}.By Lemmas 7, 11, and 12, we know that
(15)r1=α11+∑j=2n‍α1j=1Δ+∑j=2n‍1Δ∑k=2n‍βkj(-ak1)=1Δ(1+∑k=2n‍(-ak1)∑j=2n‍βkj)≤1Δ(1+a11·d1·MB)≤1Δ+d1MB1-d1l1≤1Δ+MB1-d1l1≤1a11-∑k=2n‍|a1k|mk1+MB1-d1l1.
Let 2≤i≤n. By (8) and the second equality in (6), we have
(16)∑k=2n‍βik(-ak1)=Δαi1≤Δdiα11=di<1.
From (8) with 2≤j≤n, we have
(17)αij≤βij+α1jdi<βij+α1j.
Thus, for 2≤i≤n, we obtain
(18)ri=αi1+∑j=2n‍αij≤diα11+∑j=2n‍(βij+α1jdi)=diα11+∑j=2n‍βij+∑j=2n‍α1jdi≤r1di+∑j=2n‍βij≤r1l1+MB≤{1Δ+d1MB1-d1l1}l1+MB≤l1Δ+d1l1MB1-d1l1+MB≤1Δ+MB1-d1l1≤1a11-∑k=2n‍|a1k|mk1+MB1-d1l1.
So by (15) and (18), we get
(19)∥A-1∥∞≤1a11-∑k=2n‍|a1k|mk1+MB1-u1l1.(2)
Applying induction with respect tok of A(k,n) in (19) finishes the proof.From Theorem14 and Lemma 13, the following theorem can be obtained easily.Theorem 15.
LetA=(aij) be an n×n row strictly diagonally dominant M-matrix. Then the smallest eigenvalue of A is
(20)q(A)≥{{[∏j=1i-1‍11-ujlj]}1a11-∑k=2n‍|a1k|mk1+∑i=2n‍[1aii-∑k≠i,i≤k≤nn‍|aik|mki∏j=1i-1‍11-ujlj]}-1.Theorem 16.
LetA=(aij) be an n×n row strictly diagonally dominant M-matrix. Then the bound in (13) is sharper than that in (3), that is,
(21)1a11-∑k=2n‍|a1k|mk1+∑i=2n‍[1aii-∑k≠i,i≤k≤nn‍|aik|mki∏j=1i-1‍11-ujlj]≤1a11(1-u1d1)+∑i=2n‍[1aii(1-uili)∏j=1i-1‍11-ujlj].Proof.
SinceA is a strictly diagonally dominant matrix, 0≤dk<1, mki≤di<1, and 1≤j≤n-1, then we have
(22)1aii-∑k=2n‍|aik|mki≤1aii(1-uidi).
The results follow Lemma 12. Inequality (21) shows that the bound in (13) is better than that in (3).
For alli, maxi≤k≤n{1/(aii-∑k=2n|aik|mki)}<maxi≤k≤n{1/aii(1-uidi)}, we have
(23)1a11-∑k=2n‍|a1k|mk1+∑i=2n‍[1aii-∑k≠i,i≤k≤nn‍|aik|mki∏j=1i-1‍11-ujlj]<1a11(1-u1d1)+∑i=2n‍[1aii(1-uili)∏j=1i-1‍11-ujlj].
With the help of the above discussions, we give the upper bound for∥A-1∥∞ of a real strictly α-diagonally dominant M-matrix.


## 3. Estimation for an Upper Bound  for∥A-1∥∞ of a Strictly α-Diagonally Dominant M-Matrix

We show some notations and lemmas which are necessary to our conclusions.Lemma 17 (see [12]).
LetA,B∈Rn×n, A, A-B be nonsingular, then
(24)(A-B)-1=A-1+A-1B(I-A-1B)-1A-1.Lemma 18.
LetA=(aij)∈Rn×n is a strictly diagonal dominant M-matrix. If B=(bij)∈Rn×n, with
(25)∥A-1B∥∞≤max1≤i≤nκ0·∥B∥∞,
and if
(26)κ0<1∥B∥∞,
then ∥A-1B∥∞<1, where
(27)κ0=1a11-∑k=2n‍|a1k|mk1+∑i=2n‍[1aii-∑k≠i,i≤k≤nn‍|aik|mki∏j=1i-1‍11-ujlj].Proof.
By Theorem14, we get
(28)∥A-1B∥∞≤∥A-1∥∞·∥B∥∞≤max1≤i≤nκ0·∥B∥∞.
It is easy to see that∥A-1B∥∞<1, if
(29)κ0<1∥B∥∞,
where
(30)κ0=1a11-∑k=2n‍|a1k|mk1+∑i=2n‍[1aii-∑k≠i,i≤k≤nn‍|aik|mki∏j=1i-1‍11-ujlj].Lemma 19 (see [12]).
If∥A-1∥∞<1, then I-A is nonsingular and
(31)∥(I-A)-1∥∞≤11-∥A∥∞.Theorem 20.
LetA=(aij)∈Rn×n be a strictly α-diagonal dominant matrix, α∈(0,1], and A be an M-matrix. If, for those i∈N1⊂N, Ri(A)>Ci(A), and κ1<1/max1≤i≤nα(Ri(A)-Ci(A)), then
(32)∥A-1∥∞≤κ11-κ1max1≤i≤nα(Ri(A)-Ci(A)),
where
(33)κ1=1β1-∑k=2n‍|a1k|mk1+∑i=2n‍[1βi-∑k≠i,i≤k≤nn‍|aik|mki∏j=1i-1‍11-ujlj],βi=max{aii,aii+α(Ri(A)-Ci(A))},i=1,2,…,n.Proof.
Note thatRi(A)>Ci(A). Then
(34)|aii|>(1-α)Ri(A)+αCi(A)=Ri(A)-α(Ri(A)-Ci(A)).
So we can split A, such that A=B-C, where B=(bij) and
(35)bij={aii+α(Ri(A)-Ci(A))i=j,Ri(A)>Ci(A)aijothers,cij={α(Ri(A)-Ci(A))i=j,Ri(A)>Ci(A)0others.
We know bii=aii+α(Ri(A)-Ci(A))>Ri(A)=Ri(B) and A is an M-matrix. Thus, B is a strictly diagonal dominant M-matrix; hence, B-1>0. Let βi=max{aii,aii+α(Ri(A)-Ci(A))}, i=1,2,…,n. If κ1<1/max1≤i≤nα(Ri(A)-Ci(A)), by Lemma 18, we get ∥B-1C∥∞≤1. By Lemmas 17 and 19 and Theorem 14, we can obtain
(36)∥B-1∥∞≤1b11-∑k=2n‍|a1k|mk1+∑i=2n‍[1bii-∑k≠i,i≤k≤nn‍|aik|mki∏j=1i-1‍11-ujlj]≤1β1-∑k=2n‍|a1k|mk1+∑i=2n‍[1βi-∑k≠i,i≤k≤nn‍|aik|mki∏j=1i-1‍11-ujlj].
Let κ1=1/(β1-∑k=2n|a1k|mk1)+∑i=2n[(1/(βi-∑k≠i,i≤k≤nn|aik|mki))∏j=1i-11/(1-ujlj)].
Then(37)∥B-1C∥∞<κ1max1≤i≤n∑j=1n‍|cij|<κ1max1≤i≤nα(Ri(A)-Ci(A)).
Further, we have
(38)∥A-1∥∞=∥(B-C)-1∥∞=∥B-1+B-1C(I-B-1C)-1B-1∥∞≤∥B-1∥∞+∥B-1C∥∞·∥(I-B-1C)-1∥∞·∥B-1∥∞≤∥B-1∥∞+∥B-1C∥∞1-∥B-1C∥∞∥B-1∥∞=11-∥B-1C∥∞∥B-1∥∞≤κ11-κ1max1≤i≤nα(Ri(A)-Ci(A)),
where
(39)κ1=1β1-∑k=2n‍|a1k|mk1+∑i=2n‍[1βi-∑k≠i,i≤k≤nn‍|aik|mki∏j=1i-1‍11-ujlj],βi=max{aii,aii+α(Ri(A)-Ci(A))},hhhhhhhhhhhhhhhhhhi=1,2,…,n.
The proof is complete.


## 4. Examples

We illustrate our results by the following two examples.(1)
Consider the bound for∥A-1∥∞ of a strictly diagonal dominant matrix A, where
(40)A=(10-1-1-1-1-110-1-1-1-1-110-1-1-1-1-110-1-1-1-1-110).Direct calculation by MATLAB R2010a gives
(41)∥A-1∥∞=0.1669,∥A-1∥∞≤214.0217(byTheorem3.3in[8])∥A-1∥∞≤175.9183(by(2))∥A-1∥∞≤9.2041(by(3))∥A-1∥∞≤6.5634(byTheorem14(13)).
It is obvious that the bound of Theorem 14 of this paper is better than other known ones. Furthermore, we can estimate q(A) by Theorem 15. (2)
Consider the bound for∥A-1∥∞ of a strictly α-diagonal dominant matrix A for α=0.5,
(42)A=(2-1-1-12-1-0.502),A-1=(0.88890.44440.66670.55560.77780.66670.22220.11110.6667).Note that
(43)∥A-1∥∞≈2.We know thatA is not a strictly diagonal dominant matrix, and the bound of ∥A-1∥∞ cannot be obtained by (2) or (3), but it can be estimated by (32) in Theorem 20.Split the matrixA such that A=B-C, where B=(bij) and b11=a11+α(R1(A)-C1(A))=2+0.5×(2-1.5)=2.25, b22=a22+α(R2(A)-C2(A))=2+0.5×(2-1)=2.5, Then
(44)B=(2.25-1-1-12.5-1-0.502),C=(0.250000.50000).
The bound for ∥A-1∥∞ can be estimated by (13) in Theorem 14 and (32) in Theorem 20 as follows:
(45)∥A-1∥∞≤11.4259.



---

*Source: 980615-2013-12-26.xml*