# total unimodularity of a matrix

Let G be the node-arc incidence matrix of a given directed network (rows of $$G$$ correspond to nodes and its columns correspond to arcs). Let $$B_1,\dots, B_K$$ denote a partition of the nodes of the network. Suppose the network is such that a directed arc can go from a node in $$B_k$$ to another node in $$B_\ell$$ only if $$k<\ell$$. Let $$H$$ denote a matrix with $$K$$ rows and suppose that its columns are indexed by the arcs of the underlying network. We assume that $$H$$ is such that its $$(k,e)$$-th entry is equal to one if $$e\in B_k$$, and zero otherwise.

Is the matrix [H;G] (obtained by the concatenation of rows of $$H$$ and $$G$$) totally unimodular? If not, can you give a counter example?

I've explored a few examples numerically, and verified total unimodularity for these examples. I thought it may be possible the exploit the structure of $$H$$ (note the special row structure) to prove the result formally. I've tried leveraging the Ghouila-Houri condition (see https://en.wikipedia.org/wiki/Unimodular_matrix) which seems like a suitable candidate for exploiting the row structure. But I was not successful so far.

• X-posted: mathoverflow.net/q/346159/91764 – Rodrigo de Azevedo Nov 17 '19 at 7:59
• There is a C++ library for testing total unimodularity: matthiaswalter.org/TUtest – Aaron Dall Nov 19 '19 at 7:12
• What does it mean for an arc $e$ to be in $B_k$? The $B_i$ form a partition of the nodes of $G$, not of the arcs. So an arc $e$ cannot be a member of $B_i$. Moreover, no arc has both its its nodes in the same $B_i$ by the assumption in the third sentence. So the other obvious option also doesn't make sense. – Aaron Dall Nov 19 '19 at 7:21