Good hidden \(P\)-matrix sandwiches
type: Item
instance of: scholarly article
title: Good hidden \(P\)-matrix sandwiches
zbMATH Open document ID: 1126.15031
author: Makoto Namiki
author: Walter Morris
published in: Linear Algebra and its Applications
publication date: 2007-09-14T00:00:00Z
review text: 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.
reviewed by: John D. Dixon
Mathematics Subject Classification ID: 15B57
Mathematics Subject Classification ID: 90C33
zbMATH DE Number: 5190944
zbMATH Keywords: diagonally dominant matrix
zbMATH Keywords: linear complementarity problem
zbMATH Keywords: hidden Minkowski matrix
MaRDI profile type: Publication
full work available at URL: j.laa.2007.05.004
OpenAlex ID: W2030374427
cites work: The P-matrix problem is co-NP-complete
cites work: Q4003375
cites work: Q4039868
cites work: On total functions, existence theorems and computational complexity
cites work: Linear complementarity problems solvable by A single linear program
cites work: Linear complementarity problems solvable by a polynomially bounded pivoting algorithm
cites work: Geometric Properties of Hidden Minkowski Matrices
cites work: CP-rays in simplicial cones
cites work: Convex sets of nonsingular and P:–Matrices
cites work: Recognition of hidden positive row diagonally dominant matrices
cites work: Q5638112
cites work: Second-order cone programming
cites work: Q4182279
cites work: Q4040931
DOI: 10.1016/J.LAA.2007.05.004
Recommended article: Recognition of hidden positive row diagonally dominant matrices
Recommended article: On semimonotone matrices with nonnegative principal minors
Recommended article: On some classes of matrices related to solving linear complementarity problems as linear programs
Recommended article: On hidden \(\mathbf{Z}\)-matrices and the linear complementarity problem
Recommended article: The fibre of P-matrices: the recursive construction of all matrices with positive principal minors
Recommended article: Linear complementarity problems solvable by a polynomially bounded pivoting algorithm
Recommended article: A polynomial algorithm for testing the nonnegativity of principal minors of Z-matrices
Recommended article: Generalizations of the hidden Minkowski property
Recommended article: A recursive test for P-matrices
Recommended article: N-matrices
description: scientific article; zbMATH DE number 5190944