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

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. We point out that this strengthens some recent results on M-matrices in the literature.

Minor corrections to Alg. 2, Ex. B.3, Lemma 2.22's proof, Sec. 3.2's analysis. Specified that matrices are square in Def. 2.19, Alg. 1, Lemma 3.3. Specified nnz>=1 in Lemma 3.3. Main results, numerics, and figures unchanged. Minor bib/LaTeX updates