A decomposition of strongly unimodular matrices into incidence matrices of digraphs (Q1193711): Difference between revisions

A matrix \(A\) is said to be totally unimodular if the determinant of each of its square submatrices is 0, 1 or \(-1\). A totally unimodular matrix \(A\) is said to be strongly unimodular if every matrix obtained from \(A\) by replacing a zero entry with 1 or \(-1\) is again a totally unimodular matrix. In this paper it is proved that if \(A\) is a strongly unimodular matrix then there exists a partition \((S_ 1,\dots,S_ k)\) of the rows of \(A\) such that (i) every column of \(A\) has 0, 1 or 2 nonzero entries in each \(S_ i\), \(i=1,2,\dots,k\); (ii) if a column of \(A\) has exactly one nonzero entry in some \(S_ i\), then all its entries in \(S_{i+1},\dots,S_ k\) are zero. The authors further prove that every strongly unimodular matrix is ``on- line balanced''. However, they do not give any properties of the digraphs whose incidence matrix is a strongly unimodular matrix.