A New Upper Bound for A - 1 of a Strictly [alpha] -Diagonally Dominant M -Matrix

Abstract

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

(ProQuest: ... denotes non-US-ASCII text omitted.)

Zhanshan Yang 1 and Bing Zheng 2 and Xilan Liu 1

Academic Editor:Ting-Zhu Huang

1, Department of Mathematics and Statistics, Qinghai University for Nationalities, Xining 810007, China
2, School of Mathematics and Statistics, Lanzhou University, Lanzhou 730000, China

Received 22 September 2013; Accepted 10 December 2013

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

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 = ( _{a i j ) n × n} ∈ ^{R n × n} and obtained the following estimation: [figure omitted; refer to PDF] 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 { | _{a i i} | - ^{∑ j = 1 , j ...0; i} | _{a i j} | } 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 [figure omitted; refer to PDF] and then Wang [4] further improved this bound and gave the following result: [figure omitted; refer to PDF] 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 = ( _{a i j ) n × n} ∈ ^{R n × 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, let I be an identity matrix of order n . If there exists an n × n nonnegative matrix B and a real number a such that A = a I - 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].

An n × n matrix A = ( _{a i j} ) is called a strictly diagonally dominant matrix if | _{a i i} | > ^{∑ j = 1 , j ...0; i} | _{a i j} | for i ∈ N . Let [figure omitted; refer to PDF] 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 _{n 1} and _{n 2} is denoted by ^{A ( _{n 1} , _{n 2} )} .

Definition 1 (see [8]).

A ∈ ^{R n × n} is weakly chained diagonally dominant if, for all i ∈ N , _{d i} ...4; 1 and J ( A ) ...0; ∅ and for all i ∈ N , i ∉ J ( A ) , there exist indices _{i 1} , _{i 2} , ... , _{i k} in N with _{a i r i r + 1} ...0; 0 , 0 ...4; r ...4; k - 1 , where _{i 0} = i and _{i k} ∈ J ( A ) .

Definition 2 (see [9]).

Let A ∈ ^{R n × n} , A is strictly diagonally dominant if J ( A ) = N .

Obviously, if A ∈ ^{R n × 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 ...0; j , _{a i j} ...4; 0 and _{a i i} > 0 .

Definition 4 (see [10]).

Let A ∈ ^{R n × n} ; if there exist α ∈ [ 0,1 ] , such that [figure omitted; refer to PDF] for all i ∈ N , then A is said to be an α -diagonal dominant matrix, denoted by ^{D n α} .

Remark 5.

By Definition 4, 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 ( S ^{D n α} ).

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]).

Let A = ( _{a i j} ) be an n × n weakly chained diagonally dominant M -matrix, B = ^{A ( 2 , n )} , ^{A - 1} = ( _{α i j} ^{) i , j = 1 n} , and ^{B - 1} = ( _{β i j} ^{) i , j = 2 n} . Then, for i , j = 1,2 , ... , n , [figure omitted; refer to PDF] where [figure omitted; refer to PDF] Furthermore, if J ( A ) = N , then Δ ...5; _{a 11} ( 1 - _{d 1 l 1} ) ...5; _{a 11} ( 1 - _{d 1} ) .

Lemma 8 (see [11]).

A weakly chained diagonally dominant L -matrix is a nonsingular M -matrix.

Lemma 9 (see [11]).

Let A = ( _{a i j} ) 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} = ( _{β i j} ) exists and _{β i j} ...5; 0 ( i , j = 2,3 , ... , n ) .

Lemma 10 (see [11]).

Let A = ( _{a i j} ) be an n × n weakly chained diagonally dominant M -matrix, ^{A - 1} = ( _{α i j} ) . Then, for i ...0; j , [figure omitted; refer to PDF]

Lemma 11 (see [11]).

Let A = ( _{a i j} ) be an n × n row strictly diagonally dominant M -matrix; then [figure omitted; refer to PDF]

Lemma 12 (see [2]).

Let A = ( _{a i j} ) be an n × n row strictly diagonally dominant M -matrix; then, for ^{A - 1} = ( _{α i j} ^{) i , j = 1 n} , we have [figure omitted; refer to PDF]

Lemma 13 (see [1]).

Let A = ( _{a i j} ) be an n × n weakly chained diagonally dominant M-matrix, ^{A - 1} = ( _{α i j} ) , and q = q ( A ) , N = 1,2 , ... , n . Then [figure omitted; refer to PDF] where [figure omitted; refer to PDF]

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.

Let A = ( _{a i j} ) be an n × n row strictly diagonally dominant M-matrix, ^{A - 1} = ( _{α i j} ) . Then [figure omitted; refer to PDF]

Proof.

We prove this theorem by induction.

(1) Let _{r i} = ^{∑ j = 1 n} _{α i j} , B = ^{A ( 2 , n )} , _{M A} = _{|| ^{A - 1} || ∞} , and _{M B} = _{|| ^{B - 1} || ∞} . Then [figure omitted; refer to PDF]

By Lemmas 7, 11, and 12, we know that [figure omitted; refer to PDF] Let 2 ...4; i ...4; n . By (8) and the second equality in (6), we have [figure omitted; refer to PDF] From (8) with 2 ...4; j ...4; n , we have [figure omitted; refer to PDF] Thus, for 2 ...4; i ...4; n , we obtain [figure omitted; refer to PDF] So by (15) and (18), we get [figure omitted; refer to PDF]

(2) Applying induction with respect to k of ^{A ( k , n )} in (19) finishes the proof.

From Theorem 14 and Lemma 13, the following theorem can be obtained easily.

Theorem 15.

Let A = ( _{a i j} ) be an n × n row strictly diagonally dominant M -matrix. Then the smallest eigenvalue of A is [figure omitted; refer to PDF]

Theorem 16.

Let A = ( _{a i j} ) be an n × n row strictly diagonally dominant M -matrix. Then the bound in (13) is sharper than that in (3), that is, [figure omitted; refer to PDF]

Proof.

Since A is a strictly diagonally dominant matrix, 0 ...4; _{d k} < 1 , _{m k i} ...4; _{d i} < 1 , and 1 ...4; j ...4; n - 1 , then we have [figure omitted; refer to PDF] The results follow Lemma 12. Inequality (21) shows that the bound in (13) is better than that in (3).

For all i , _{max i ...4; k ...4; n} { 1 / ( _{a i i} - ^{∑ k = 2 n} | _{a i k} | _{m k i} ) } < _{max i ...4; k ...4; n} { 1 / _{a i i} ( 1 - _{u i d i} ) } , we have [figure omitted; refer to PDF]

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]).

Let A , B ∈ ^{R n × n} , A , A - B be nonsingular, then [figure omitted; refer to PDF]

Lemma 18.

Let A = ( _{a i j} ) ∈ ^{R n × n} is a strictly diagonal dominant M -matrix. If B = ( ^{b i j} ) ∈ ^{R n × n} , with [figure omitted; refer to PDF] and if [figure omitted; refer to PDF] then _{|| ^{A - 1} B || ∞} < 1 , where [figure omitted; refer to PDF]

Proof.

By Theorem 14, we get [figure omitted; refer to PDF]

It is easy to see that _{|| ^{A - 1} B || ∞} < 1 , if [figure omitted; refer to PDF] where [figure omitted; refer to PDF]

Lemma 19 (see [12]).

If _{|| ^{A - 1} || ∞} < 1 , then I - A is nonsingular and [figure omitted; refer to PDF]

Theorem 20.

Let A = ( _{a i j} ) ∈ ^{R n × n} be a strictly α -diagonal dominant matrix, α ∈ ( 0,1 ] , and A be an M -matrix. If, for those i ∈ _{N 1} ⊂ N , _{R i} ( A ) > _{C i} ( A ) , and _{κ 1} < 1 / _{max 1 ...4; i ...4; n} α ( _{R i} ( A ) - _{C i} ( A ) ) , then [figure omitted; refer to PDF] where [figure omitted; refer to PDF]

Proof.

Note that _{R i} ( A ) > _{C i} ( A ) . Then [figure omitted; refer to PDF] So we can split A , such that A = B - C , where B = ( _{b i j} ) and [figure omitted; refer to PDF] We know _{b i i} = _{a i i} + α ( _{R i} ( A ) - _{C i} ( A ) ) > _{R i} ( A ) = _{R i} ( B ) and A is an M -matrix. Thus, B is a strictly diagonal dominant M -matrix; hence, ^{B - 1} > 0 . Let _{β i} = max { _{a i i} , _{a i i} + α ( _{R i} ( A ) - _{C i} ( A ) ) } , i = 1,2 , ... , n . If _{κ 1} < 1 / _{max 1 ...4; i ...4; n} α ( _{R i} ( A ) - _{C i} ( A ) ) , by Lemma 18, we get _{|| ^{B - 1} C || ∞} ...4; 1 . By Lemmas 17 and 19 and Theorem 14, we can obtain [figure omitted; refer to PDF] Let _{κ 1} = 1 / ( _{β 1} - ^{∑ k = 2 n} | _{a 1 k} | _{m k 1} ) + ^{∑ i = 2 n} [ ( 1 / ( _{β i} - ^{∑ k ...0; i , i ...4; k ...4; n n} | _{a i k} | _{m k i} ) ) ^{∏ j = 1 i - 1} 1 / ( 1 - _{u j l j} ) ] .

Then [figure omitted; refer to PDF] Further, we have [figure omitted; refer to PDF] where [figure omitted; refer to PDF] 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 [figure omitted; refer to PDF]

Direct calculation by MATLAB R2010a gives [figure omitted; refer to PDF] 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 , [figure omitted; refer to PDF]

Note that [figure omitted; refer to PDF]

We know that A 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 matrix A such that A = B - C , where B = ( _{b i j} ) and _{b 11} = _{a 11} + α ( _{R 1} ( A ) - _{C 1} ( A ) ) = 2 + 0.5 × ( 2 - 1.5 ) = 2.25 , _{b 22} = _{a 22} + α ( _{R 2} ( A ) - _{C 2} ( A ) ) = 2 + 0.5 × ( 2 - 1 ) = 2.5 , Then [figure omitted; refer to PDF] The bound for _{|| ^{A - 1} || ∞} can be estimated by (13) in Theorem 14 and (32) in Theorem 20 as follows: [figure omitted; refer to PDF]

Conflict of Interests

There is no conflict of interests regarding the publication of this paper.

Acknowledgment

This paper is supported by the NNSF of China (11171371, 11361047) and the NSF of Qinghai Province (2012-Z-910).

References

[1] J. M. Varah, "A lower bound for the smallest singular value of a matrix," Linear Algebra and Its Applications , vol. 11, pp. 3-5, 1975.

[2] R. S. Varga, "On diagonal dominance arguments for bounding _{|| ^{A - 1} || ∞} ," Linear Algebra and Its Applications , vol. 14, no. 3, pp. 211-217, 1976.

[3] G.-H. Cheng, T.-Z. Huang, "An upper bound for _{|| ^{A - 1} || ∞} of strictly diagonally dominant M -matrices," Linear Algebra and Its Applications , vol. 426, no. 2-3, pp. 667-673, 2007.

[4] P. Wang, "An upper bound for _{|| ^{A - 1} || ∞} of strictly diagonally dominant M -matrices," Linear Algebra and Its Applications , vol. 431, no. 5-7, pp. 511-517, 2009.

[5] R. A. Horn, C. R. Johnson Topics in Matrix Analysis , pp. viii+607, Cambridge University Press, Cambridge, Mass, USA, 1991.

[6] C. R. Johnson, "A Hadamard product involving M -matrices," Linear and Multilinear Algebra , vol. 4, no. 4, pp. 261-264, 1977.

[7] M. Fiedler, C. R. Johnson, T. L. Markham, "A trace inequality for M -matrices and the symmertrizability of a real matrix by a positive diagonal matrix," Linear Algebra and Its Applications , vol. 102, pp. 1-8, 1988.

[8] P. N. Shivakumar, J. J. Williams, Q. Ye, C. A. Marinov, "On two-sided bounds related to weakly diagonally dominant M -matrices with application to digital circuit dynamics," SIAM Journal on Matrix Analysis and Applications , vol. 17, no. 2, pp. 298-312, 1996.

[9] A. Berman, R. J. Plemmons Nonnegative Matrices in the Mathematical Sciences , Academic Press, New York, NY, USA, 1994.

[10] Y. L. Zhang, H. M. Mo, J. Z. Liu, " α -diagonal dominance and criteria for generalized strictly diagonally dominant matrices," Numerical Mathematics , vol. 31, no. 2, pp. 119-128, 2009.

[11] P. N. Shivakumar, K. H. Chew, "A sufficient condition for nonvanishing of determinants," Proceedings of the American Mathematical Society , vol. 43, pp. 63-66, 1974.

[12] S. Xu Theory and Methods about Matrix Computation , Tshua University Press, Beijing, China, 1986.