Combinatorial characterizations of K-matrices

e present a number of combinatorial characterizations of K-matrices. This extends a theorem of Fiedler and Pták on linear-algebraic characterizations of K-matrices to the setting of oriented matroids. Our proof is elementary and simplifies the original proof substantially by exploiting the duality of oriented matroids. As an application, we show that any simple principal pivot method applied to the linear complementarity problems with K-matrices converges very quickly, by a purely combinatorial argument.