EP theorems and linear complementarity problems Original Research Article

Let A be a rational n × n square matrix and b be a rational n-vector for some positive integer n. The linear complementarity problem (abbreviated by LCP) is to find a vector (x, y)ϵR2n satisfying y = Ax + b (x, y) ⩾ 0 and the complementarity condition: xi · yi = 0 for all i = 1, …, n. The LCP is known to be NP-complete, but there are some known classes of matrices A for which the LCP is polynomially solvable, for example the class of positive semi-definite (PSD-) matrices.