Linear complementarity and oriented matroids

A combinatorial abstraction of the linear complementarity theory in the setting of oriented matroids was first considered by M.J. Todd. In this paper, the authors take a fresh look at this abstraction, and attempt to give a simple treatment of the combinatorial theory of linear complementarity. They obtain new theorems, proofs and algorithms in oriented matroids whose specializations to the linear case are also new. For this, the notion of sufficiency of square matrices, introduced by Cottle, Pang and Venkateswaran, is extended to oriented matroids. Then, the authors prove a sort of duality theorem for oriented matroids, which roughly states: exactly one of the primal and the dual system has a complementary solution if the associated oriented matroid satisfies ‘weak’ sufficiency. They give two different proofs for this theorem, an elementary inductive proof and an algorithmic proof using the criss-cross method which solves one of the primal or dual problems by using surprisingly simple pivot rules (without any perturbation of the original problem).