# 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.

• – Rodrigo de Azevedo Nov 17 '19 at 7:59
• I’m a little confused what is [H;G]. Do you mean that you concatenate every row of H with every row of G? Or do you mean to use H transpose? – Josh Nov 18 '19 at 1:29