A square matrix M is a Q-matrix if every linear complementarity problem xT (Mx + q) = 0, Mx + q ≥ 0, x ≥ 0 has a solution. We explain how one can use the polyhedral structure of the set of all triangulations of a finite point set to determine if an n × n matrix M is a Q-matrix. Our implementation of the algorithm is practical for deciding the Q-nature for all M with n ≤ 8.
