Q-matrix recognition via secondary and universal polytopes

A square matrix M is a Q - matrix if every linear complementarity problem x (T)(Mx + q) = 0, Mx + q greater than or equal to 0, x greater than or equal to 0 has a solution. We explain how one can use the polyhedral structure o f the set of all triangulations of a finite point set to determine if an n x n matrix M is a Q-matrix. Our implementation of the algorithm is practica l for deciding the Q-nature for all M with n less than or equal to 8.