## A fast and stable test to check if a weakly diagonally dominant matrix is a nonsingular M-matrix

HTML articles powered by AMS MathViewer

- by
Parsiad Azimzadeh
**HTML**| PDF - Math. Comp.
**88**(2019), 783-800 Request permission

## Abstract:

We present a test for determining if a substochastic matrix is convergent. By establishing a duality between weakly chained diagonally dominant (w.c.d.d.) L-matrices and convergent substochastic matrices, we show that this test can be trivially extended to determine whether a weakly diagonally dominant (w.d.d.) matrix is a nonsingular M-matrix. The testβs runtime is linear in the order of the input matrix if it is sparse, and quadratic if it is dense. This is a partial strengthening of the cubic test in [J. M. PeΓ±a.,*A stable test to check if a matrix is a nonsingular M-matrix*, Math. Comp., 247, 1385β1392, 2004]. As a by-product of our analysis, we prove that a nonsingular w.d.d. M-matrix is a w.c.d.d. L-matrix, a fact whose converse has been known since at least 1964.

## References

- P. Azimzadeh and P. A. Forsyth,
*Weakly chained matrices, policy iteration, and impulse control*, SIAM J. Numer. Anal.**54**(2016), no.Β 3, 1341β1364. MR**3493959**, DOI 10.1137/15M1043431 - Abraham Berman and Robert J. Plemmons,
*Nonnegative matrices in the mathematical sciences*, Classics in Applied Mathematics, vol. 9, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1994. Revised reprint of the 1979 original. MR**1298430**, DOI 10.1137/1.9781611971262 - Olivier Bokanowski, Stefania Maroso, and Hasnaa Zidani,
*Some convergence results for Howardβs algorithm*, SIAM J. Numer. Anal.**47**(2009), no.Β 4, 3001β3026. MR**2551155**, DOI 10.1137/08073041X - J. H. Bramble and B. E. Hubbard,
*On a finite difference analogue of an elliptic boundary problem which is neither diagonally dominant nor of non-negative type*, J. Math. and Phys.**43**(1964), 117β132. MR**162367** - Guang-Hui Cheng and Ting-Zhu Huang,
*An upper bound for $\Vert A^{-1}\Vert _\infty$ of strictly diagonally dominant $M$-matrices*, Linear Algebra Appl.**426**(2007), no.Β 2-3, 667β673. MR**2350685**, DOI 10.1016/j.laa.2007.06.001 - Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein,
*Introduction to algorithms*, 3rd ed., MIT Press, Cambridge, MA, 2009. MR**2572804** - F. R. Gantmacher,
*Applications of the theory of matrices*, Interscience Publishers, Inc., New York; Interscience Publishers Ltd., London, 1959. Translated by J. L. Brenner, with the assistance of D. W. Bushaw and S. Evanusa. MR**0107648** - Gene H. Golub and Charles F. Van Loan,
*Matrix computations*, 4th ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 2013. MR**3024913** - Nicholas J. Higham,
*The accuracy of floating point summation*, SIAM J. Sci. Comput.**14**(1993), no.Β 4, 783β799. MR**1223274**, DOI 10.1137/0914050 - Ting-Zhu Huang and Yan Zhu,
*Estimation of $\|A^{-1}\|_\infty$ for weakly chained diagonally dominant $M$-matrices*, Linear Algebra Appl.**432**(2010), no.Β 2-3, 670β677. MR**2577710**, DOI 10.1016/j.laa.2009.09.012 - Chaoqian Li and Yaotang Li,
*Weakly chained diagonally dominant $B$-matrices and error bounds for linear complementarity problems*, Numer. Algorithms**73**(2016), no.Β 4, 985β998. MR**3579726**, DOI 10.1007/s11075-016-0125-8 - Chaoqian Li, Yaotang Li, and Ruijuan Zhao,
*New inequalities for the minimum eigenvalue of $M$-matrices*, Linear Multilinear Algebra**61**(2013), no.Β 9, 1267β1279. MR**3175363**, DOI 10.1080/03081087.2012.746332 - Chaoqian Li, Ruidan Ma, Qilong Liu, and Yaotang Li,
*Subdirect sums of weakly chained diagonally dominant matrices*, Linear Multilinear Algebra**65**(2017), no.Β 6, 1220β1231. MR**3615539**, DOI 10.1080/03081087.2016.1233933 - Wen Li,
*The infinity norm bound for the inverse of nonsingular diagonal dominant matrices*, Appl. Math. Lett.**21**(2008), no.Β 3, 258β263. MR**2433738**, DOI 10.1016/j.aml.2007.03.018 - J. M. PeΓ±a,
*A stable test to check if a matrix is a nonsingular $M$-matrix*, Math. Comp.**73**(2004), no.Β 247, 1385β1392. MR**2047092**, DOI 10.1090/S0025-5718-04-01639-4 - R. J. Plemmons,
*$M$-matrix characterizations. I. Nonsingular $M$-matrices*, Linear Algebra Appl.**18**(1977), no.Β 2, 175β188. MR**444681**, DOI 10.1016/0024-3795(77)90073-8 - Yousef Saad,
*Iterative methods for sparse linear systems*, 2nd ed., Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003. MR**1990645**, DOI 10.1137/1.9780898718003 - P. N. Shivakumar and Kim Ho Chew,
*A sufficient condition for nonvanishing of determinants*, Proc. Amer. Math. Soc.**43**(1974), 63β66. MR**332820**, DOI 10.1090/S0002-9939-1974-0332820-0 - P. N. Shivakumar, Joseph J. Williams, Qiang Ye, and Corneliu A. Marinov,
*On two-sided bounds related to weakly diagonally dominant $M$-matrices with application to digital circuit dynamics*, SIAM J. Matrix Anal. Appl.**17**(1996), no.Β 2, 298β312. MR**1384509**, DOI 10.1137/S0895479894276370 - Gui-Xian Tian and Ting-Zhu Huang,
*Inequalities for the minimum eigenvalue of $M$-matrices*, Electron. J. Linear Algebra**20**(2010), 291β302. MR**2653540**, DOI 10.13001/1081-3810.1374 - Richard S. Varga,
*Matrix iterative analysis*, Second revised and expanded edition, Springer Series in Computational Mathematics, vol. 27, Springer-Verlag, Berlin, 2000. MR**1753713**, DOI 10.1007/978-3-642-05156-2 - Feng Wang and De-shu Sun,
*Some new inequalities for the minimum eigenvalue of $M$-matrices*, J. Inequal. Appl. , posted on (2015), 2015:195, 7. MR**3357017**, DOI 10.1186/s13660-015-0723-3 - Ping Wang,
*An upper bound for $\Vert A^{-1}\Vert _\infty$ of strictly diagonally dominant $M$-matrices*, Linear Algebra Appl.**431**(2009), no.Β 5-7, 511β517. MR**2535528**, DOI 10.1016/j.laa.2009.02.037 - Ming Xu, Suhua Li, and Chaoqian Li,
*Inequalities for the minimum eigenvalue of doubly strictly diagonally dominant $M$-matrices*, J. Appl. Math. , posted on (2014), Art. ID 535716, 8. MR**3253625**, DOI 10.1155/2014/535716 - Zhanshan Yang, Bing Zheng, and Xilan Liu,
*A new upper bound for $\|A^{-1}\|$ of a strictly $\alpha$-diagonally dominant $M$-matrix*, Adv. Numer. Anal. , posted on (2013), Art. ID 980615, 6. MR**3149442**, DOI 10.1155/2013/980615 - Jianxing Zhao and Caili Sang,
*Several new inequalities for the minimum eigenvalue of $M$-matrices*, J. Inequal. Appl. , posted on (2016), Paper No. 119, 9. MR**3486018**, DOI 10.1186/s13660-016-1062-8

## Additional Information

**Parsiad Azimzadeh**- Affiliation: David R. Cheriton School of Computer Science, University of Waterloo, Waterloo ON, Canada N2L 3G1
- Address at time of publication: Department of Mathematics, University of Michigan, East Hall, 530 Church Street, Ann Arbor, Michigan 48109
- MR Author ID: 1097701
- Email: parsiad@umich.edu
- Received by editor(s): January 24, 2017
- Received by editor(s) in revised form: June 11, 2017, November 14, 2017, and December 14, 2017
- Published electronically: May 29, 2018
- © Copyright 2018 American Mathematical Society
- Journal: Math. Comp.
**88**(2019), 783-800 - MSC (2010): Primary 65F30, 15B48, 15B51; Secondary 65F50
- DOI: https://doi.org/10.1090/mcom/3347
- MathSciNet review: 3882284