The only known sufficient condition is rather strong and requires the existence and uniqueness of solutions for the underlying linear complementarity problem (LCP) which, for a fixed matrix M and a given vector q, asks whether there exists a pair of vectors (w,z) satisfying w - M z = q, w,z >= 0, and w.z = 0.  M is said to be a Q-matrix when a solution exists for all q. We start by exposing the inherent difficulty of characterizing Q-matrices by reformulating the problem as a covering problem of R^n. We then investigate the regions where no solution exists (so called holes) and show that they only occur in specific locations.

This property is exploited to fully characterize planar and spatial Q-matrices via a local reduction around the vectors defining the problem.

This is a joint work with Christelle Kozaily.

I was previously a postdoc at Carnegie Mellon University (Pittsburgh, PA, USA), School of Computer Science, Logical Systems Lab and before that at NEC Labs America, System Analysis and Verification Group (Princeton, NJ, USA).