Given a square matrix M of order n and a vector q∈ℝn, the linear complementarity problem is the problem of either finding a w∈ℝn and a z∈ℝn such that w-Mz=q, w∈0, z∈0 and wTz=0 or showing that no such (w,z) exists. This problem is denoted as LCP(q,M). The paper says that a solution (w,z) to LCP(q,M) is degenerate if the number of positive coordinates in (w,z) is less than n. As in linear programming, degeneracy may cause cycling in an adjacent vertex following methods like Lemke’s algorithm. Moreover, if LCP(0,M) has a nontrivial solution, a condition related to degeneracy, then unless certain other conditions are satisfied, the algorithm may not be able to decide about the solvability of the given LCP(q,M). This paper reviews the literature on the implications of degeneracy to the linear complementarity theory.
