Principal Pivoting Method for Solving Column Sufficient Complementarity Problems
A. L. N. Murthy, G. S. R. Murthy · SIAM Journal on Matrix Analysis and Applications · 2000
The linear complementarity problem (q, A) is to find, for a given real square matrix A of order n and a real column vector q of order n, a nonnegative vector z such that A z + q \geq 0$ and z t (A z + q) =0. It is known that when A is a positive semidefinite matrix, one can use a principal pivoting method to compute a solution to (q, A) if it has one and to conclude that the problem has no solution otherwise. Cottle, Pang, and Venkateswaran [Linear Algebra Appl., 114/115 (1989), pp. 231--249] introduced the class of sufficient matrices and widened the scope of a principal pivoting algorithm to solve linear complementarity problems with row sufficient matrices. Our main result in this article is to show that this algorithm can be extended to solve even the problems with column sufficient matrices.