On Some Classes of Linear Complementarity Problems with Matrices of Order n and Rank (n − 1)

In this paper we generalize a fundamental result observed by B. C. Eaves on the nature of solutions constructed by Lemke's algorithm applied to solve the linear complementarity problem (q, M) initiating it with the positive vector d ∈ Rⁿ. We use this generalization and identify two subclasses of the class of n × n matrices M of rank (n − 1) for which the set of q ∈ Rⁿ such that the LCP (q, M) has a solution is convex. We also present algorithms to compute a solution to (q, M) if one exists, for these classes of matrices.