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.

arXiv commentMinor 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

References in corpus (1)

• Weakly chained matrices, policy iteration, and impulse control

Cited by in corpus (6)

• High order Bellman equations and weakly chained diagonally dominant tensors
• Feedback Nash Equilibria in Differential Games with Impulse Control
• A fixed-point policy-iteration-type algorithm for symmetric nonzero-sum stochastic impulse control games
• Discord in the voter model for complex networks
• Optimal market making under partial information and numerical methods for impulse control games with applications
• "Spectrally gapped" random walks on networks: a Mean First Passage Time formula