A Homological Characterization of Q-Matrices

A real square matrix M is said to be a Q-matrix if the linear complementarity problem (q, M) has a solution for every vector q. There is, as yet, no characterization of Q-matrices which makes it easy to determine whether or not a given matrix is Q. Ideas from topology, in particular degree theory, have previously been used to obtain sufficient conditions for when a matrix is Q. In this paper we will apply some other ideas from topology to give a homological characterization of Q-matrices. Continuing to borrow from topology, we define the nerve of a matrix which, along with our characterization, leads to an algorithm for checking whether or not a matrix is Q. This algorithm has smaller bounds on its worst-case time complexity than previous methods.