Integral solutions of linear complementarity problems

We characterize the class of integral square matrices M having the property that for every integral vector q the linear compelementarity problem with data M, q has only integral basic solutions. These matrices, called principally unimodular matrices, are those for which every principal nonsingular submatrix is unimodular. As a consequence, we show that if M is rank-symmetric and principally unimodular, and q is integral, then the problem has an integral solution if it has solution. Principal unimodularity can be regarded as an extension of total unimodularity, and our results can be regarded as extensions of well-known results on integral solutions to linear programs. We summarize what is known about principally unimodular symmetric and skew-symmetric matrices.