Mixed dominating matrices (Q1377507)

The authors characterize matrices for which the set of supports of nonnegative vectors in the null space can be determined by the signs of the matrix. This characterization is in terms of mixed dominating matrices, which are defined by the nonexistence of square submatrices that have nonzeros of opposite sign in each row. The class of mixed dominating matrices is contained in the class of L-matrices from the theory of sign-solvability, and generalizes the class of S-matrices. The authors give a polynomial-time algorithm to decide if a matrix is mixed dominating. They derive combinatorial conditions on the face lattice of a Gale transform of a matrix in this class. Theorem 2.9 is the key to a polynomial-time for recognizing mixed dominating matrices.