A polynomial-time test for M-matrices

DOI10.1016/0024-3795(91)90218-LMaRDI QIDQ805154zbMATH OpenFDO

Authors Hannu Väliaho

Publication date 1991

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0024-3795(91)90218-L

zbMATH Keywords

complexity orderM-matricesmatrix inversionpolynomial-time testZ-matrices

Mathematics Subject Classification ID

Miscellaneous inequalities involving matrices (15A45) Positive matrices and their generalizations; cones of matrices (15B48) Direct numerical methods for linear systems and matrix inversion (65F05)

Review text

The author studies some properties of M-matrices, defined as a subclass of real square matrices with nonpositive off-diagonal elements (called Z- matrices) but having nonnegative all principal minors. Six theorems concerning with zero-nonzero structure of inverses of non-singular M- matrices and with inequalities between two such matrices are proved after recalling some properties of M-matrices themselves (structure, reducibility, etc.). As the main result the author proves two theorems characterizing M- matrices in the class of Z-matrices and presents a polynomial-time \((n(n^ 2-1)/3\) operations at most) algorithm testing whether a Z-matrix is an M-matrix. This test is less complicated than one having the same complexity order, due to \textit{K. G. Ramamurthy} [ibid. 83, 39-47 (1986; Zbl 0602.15015)].

Recommendations

• On testing nonnegativity of principal minors of \({\mathbf{Z}} \)-matrices using simplex method
• A stable test to check if a matrix is a nonsingular $M$-matrix
• scientific article; zbMATH DE number 1530329
• Algorithmic detection and construction of N-matrices
• scientific article; zbMATH DE number 4168855

Cites work

• A generalization of N-matrices
• A polynomial algorithm for testing the nonnegativity of principal minors of Z-matrices
• scientific article; zbMATH DE number 4109935 (Why is no real title available?)
• scientific article; zbMATH DE number 3760340 (Why is no real title available?)
• scientific article; zbMATH DE number 3212891 (Why is no real title available?)
• Inverse M-matrices
• Nonnegative matrices with power invariant zero patterns
• On the inverse M-matrix problem for (0,1)-matrices
• The general quadratic optimization problem

Cited in

(6)

• Perturbations of M-matrices via ABS methods and their applications to input-output analysis
• A polynomial-time dependence test for determining integer-valued solutions in multi-dimensional arrays under variable bounds
• On testing nonnegativity of principal minors of \({\mathbf{Z}} \)-matrices using simplex method
• The Boolean pivot operation, \(M\)-matrices, and reducible matrices
• A polynomial time spectral decomposition test for certain classes of inverse M-matrices
• A stable test to check if a matrix is a nonsingular $M$-matrix

This page was built for publication: A polynomial-time test for M-matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q805154)