Good hidden \(P\)-matrix sandwiches (Q996290): Difference between revisions

A real square matrix is called a \(P\)-matrix if all its principal minors are positive. The problem of recognizing when a matrix is a \(P\)-matrix is known to be co-NP-complete [see \textit{G. E. Coxson}, Math. Program. 64, 173--178 (1994; Zbl 0822.90132)] and so is expected to be hard. The problem arises in the theory of the linear complementarity problem, and in this context several subclasses of the class of \(P\)-matrices for which polynomial time recognition algorithms are known have been investigated. Some of these classes are investigated here, in particular, ``hidden \(prdd\)'' and ``hidden \(Z^0\)'' matrices which are defined as follows. A square matrix \(C\) is positive row diagonally dominant (\(prdd\)) if \(C_{ii}>\sum_{j\neq i}\left| C_{ij}\right| \) for all \(i\), and \(C\) is called hidden \(prdd\) if \(CA=B\) where \(A\) and \(B\) are \(prdd\) matrices. Similarly \(C\) is called a \(Z^{0}\)-matrix if its diagonal entries are positive and its off-diagonal entries negative; and \(C\) is a hidden \(Z^{0}\)-matrix if \(CA=B\) where \(A\) and \(B\) are \(Z^{0}\)-matrices. The authors show that every hidden \(prdd\) matrix is a \(P\)-matrix and that every \(P\)-matrix is a hidden \(Z^{0} \)-matrix, so the class of \(P\)-matrices is ``sandwiched'' between two easily recognized classes. They prove similar results for related classes of matrices.