The Principal Pivoting Method (PPM) for the Linear Complementarity Problem (LCP) is shown to be applicable to the class of LCPs involving the newly identified class of sufficient matrices. The classes of row sufficient and column sufficient matrices were recently introduced in a paper by Cottle, Pang, and Venkateswaran. It was shown there that such matrices provide answers to natural theoretical questions concerning the LCP. Further, on the algorithmic side, it was noted that Lemke's Method (Scheme 1) for the LCP can process any problem in which the matrix is row sufficient. In fact, by a theorem of Aganagic' and Cottle', the latter is true for any Qo-matrix having non-negative principal minors, and row sufficient matrices are of this sort. These observations prompt one to ask whether the PPM is also applicable to this class of LCPs. This question is especially relevant inasmuch as the kinds of matrices that the principal pivoting method can handle have heretofore been limited to P-matrices and positive semi-definite matrices, both of which types are row sufficient as well as column sufficient. Thus, a demonstration that the PPM can process LCPs with row sufficient matrices amounts to a unification of the existing theory of the PPM and an extension of its scope. Such is the main goal of this paper. (KR)
展开▼
