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: math.stackexchange.com/q/3437674/339790 $\endgroup$ – Rodrigo de Azevedo Nov 17 '19 at 7:59
  • $\begingroup$ 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? $\endgroup$ – Josh Nov 18 '19 at 1:29

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.