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.

  • $\begingroup$ X-posted: mathoverflow.net/q/346159/91764 $\endgroup$ – Rodrigo de Azevedo Nov 17 '19 at 7:59
  • $\begingroup$ There is a C++ library for testing total unimodularity: matthiaswalter.org/TUtest $\endgroup$ – Aaron Dall Nov 19 '19 at 7:12
  • $\begingroup$ 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. $\endgroup$ – Aaron Dall Nov 19 '19 at 7:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.