Solution of Linear Complementarity Problems by Linear Programming

Abstract

The linear complementarity problem is that of finding an n x 1 vector z such that, Mz + q 2 0, z 2 0, z (Mz+q) = 0 where M is a given n x n real matrix and q is a given n x 1 vector. In this paper the class of matrices M for which this problem is solvable by a single linear program is enlarged to include matrices other than those that are Z-matrices or those that have an inverse which is a Z-matrix. (A Z-matrix is real square matrix with nonpositive offdiagonal elements.) Included in this class are other matrices such as nonnegative matrices with a strictly dominant diagonal and matrices that are the sum of a Z-matrix having a nonnegative inverse and the tensor product of any two positive vectors in R~.