Extended \(P\)-pairs (Q1355215)

A class of extendable P-matrices is defined which is properly contained in the class of P-matrices. It is shown that the linear complementarity problem (LCP): find \(x, y \in {\mathcal R}^n \) such that \(y - Mx = q\) and \( x^t y = 0,\) can be solved in \(2n + 1 \) pivots if \(M\) is P-extendable and an \(n\) step vector \(d\) for the matrix \(S M S\) is known where \(S\) is a sign matrix. Solving the LCP with \(M\) an extendable P-matrix appears to be difficult when \(d\) and \(S\) are not available. A special case of the LCP, where \(M\) is P-extendable and a sign matrix \(S\) exists such that \(S M S\) is a \(Z\)-matrix is shown to be efficiently solvable and an algorithm is given for finding the \(S\) if it exists and else the algorithm shows that no such \(S\) exists. The usefulness of the class of P-extendable matrices has been amply demonstrated, however the problem of characterising the extendable P-matrices appears to be very difficult.