Some classes of matrices in linear complementarity theory

The linear complementarity problem is the problem of finding solutionsw, z tow = q + Mz, w0,z0, andw^Tz=0, whereq is ann-dimensional constant column, andM is a given square matrix of dimensionn. In this paper, the author introduces a class of matrices such that for anyM in this class a solution to the above problem exists for all feasibleq, and such that Lemke's algorithm will yield a solution or demonstrate infeasibility. This class is a refinement of that introduced and characterized by Eaves. It is also shown that for someM in this class, there is an even number of solutions for all nondegenerateq, and that matrices for general quadratic programs and matrices for polymatrix games nicely relate to these matrices.Research partially supported by National Science Foundation Grant NSF-GP-15031.