INTEGRAL SOLUTIONS OF LINEAR COMPLEMENTARITY-PROBLEMS

We characterize the class of integral square matrices M having the pro perty that for every integral vector q the linear complementarity prob lem with data M, q has only integral basic solutions. These matrices, called principally unimodular matrices, are those for which every prin cipal nonsingular submatrix is unimodular. As a consequence, we show t hat if M iis rank-symmetric and principally unimodular, and q is integ ral, then the problem has an integral solution if it has a solution. P rincipal unimodularity can be regarded as an extension of total unimod ularity, and our results can be regarded as extensions of well-known r esults on integral solutions to linear programs. We summarize what is known about principally unimodular symmetric and skew-symmetric matric es.