A polynomial-time test for M-matrices (Q805154): Difference between revisions

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