Strong unimodularity for matrices and hypergraphs

A 0–1 matrix A is called strongly unimodular if all the bases of (A, I) are triangular. We develop equivalent conditions for strong unimodularity, first in algebraic, then in graph theoretic terms. This provides a link with the theory of unimodular and balanced hypergraphs, and allows us to produce a polynomial-time recognition algorithm for strongly unimodular matrices. We consider next the constraint matrix of the problem obtained by linearizing a general, unconstrained optimization problem in 0–1 variables. Because that matrix has 0, 1 and −1 entries, we are led to introduce the concept of signed hypergraph in which every edge is affected of a positive or negative sign. Our results on strong unimodularity are extended to the class of signed hypergraphs.