EXTENDED P-PAIRS

A P-matrix is a square matrix with positive principal miners. We intro duce a natural extension of the class of P-matrices, the class of exte nded P-pairs. A pair {I, M}, for a P-matrix M, is shown to be containe d in an extended P-pair iff SMS has an n-step vector for some sign mat rix S. Such a matrix M is called extendable, and an example of a P-mat rix that is not extendable is given. Applications to the linear comple mentarity problem are discussed. A polynomial time algorithm to determ ine if a pair of matrices is an extended P-pair is given. (C) Elsevier Science Inc., 1997.