Good hidden P-matrix sandwiches
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.
- Recognition of hidden positive row diagonally dominant matrices
- On semimonotone matrices with nonnegative principal minors
- On some classes of matrices related to solving linear complementarity problems as linear programs
- On hidden \(\mathbf{Z}\)-matrices and the linear complementarity problem
- The fibre of P-matrices: the recursive construction of all matrices with positive principal minors
- Linear complementarity problems solvable by a polynomially bounded pivoting algorithm
- A polynomial algorithm for testing the nonnegativity of principal minors of Z-matrices
- Generalizations of the hidden Minkowski property
- A recursive test for P-matrices
- N-matrices
- Convex sets of nonsingular and P:–Matrices
- CP-rays in simplicial cones
- Geometric Properties of Hidden Minkowski Matrices
- scientific article; zbMATH DE number 53115 (Why is no real title available?)
- scientific article; zbMATH DE number 192986 (Why is no real title available?)
- scientific article; zbMATH DE number 194139 (Why is no real title available?)
- scientific article; zbMATH DE number 3619645 (Why is no real title available?)
- scientific article; zbMATH DE number 3365044 (Why is no real title available?)
- Linear complementarity problems solvable by a polynomially bounded pivoting algorithm
- Linear complementarity problems solvable by A single linear program
- On total functions, existence theorems and computational complexity
- Recognition of hidden positive row diagonally dominant matrices
- Second-order cone programming
- The P-matrix problem is co-NP-complete
- Matrix sandwich problems
- On hidden Z-matrix and interior point algorithm
- Geometric Properties of Hidden Minkowski Matrices
- The fibre of P-matrices: the recursive construction of all matrices with positive principal minors
- On hidden \(\mathbf{Z}\)-matrices and the linear complementarity problem
- Combinatorial characterizations of \(K\)-matrices
- Efficient computation of a canonical form for a matrix with the generalized P-property
This page was built for publication: Good hidden \(P\)-matrix sandwiches
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q996290)
