P_c-Matrices and the Linear Complementarity Problem

We introduce a new matrix class Pc , which consists of those matrices M for which the solution set of the corresponding linear complementarity problem is connected for every q 2 IR n . We consider Lemke's pivotal method from the perspective of piecewise linear homotopies and normal maps and show that Lemke's method processes all matrices in Pc " Q0 . We further investigate the relationship of the class Pc to other known matrix classes and show that column sufficient matrices are a subclass of Pc , as are 2 \Theta 2 P0 --matrices. 1. INTRODUCTION The linear complementarity problem is a classical problem from optimization theory of finding x 2 IR n with z 0; Mz + q 0; z ? (Mz + q) = 0: Here M 2 IR n\Thetan and q 2 IR n are given data, and the resulting problem will be denoted by LCP(q; M ). We also define the set of feasible points of LCP(q; M ) by FEA(q; M ) := fz j z 0; Mz + q 0g : This material is based on research supported by the National Science Foundation Grant CC..