A direct constructive proof of a known result on total unimodularity, and a characterisation of related partitions (Q1892519)

The present investigation is restricted to matrices, each of whose columns contains no more than two nonzero elements, 1 or \(- 1\). This restriction is necessary for a matrix \(A \in \mathbb{R}^{m \times n}\) to be totally unimodular, i.e., each square submatrix of \(A\) has a determinant equal to \(0,1\) or \(- 1\). The problem is tested for total unimodularity for a class of matrices with the property Q.1: If \(i \in I\), \(i' \in I\) \((I\) is the set of rows of \(A\), \(I = I_ 1 + I_ 2\), \(I_ i \cap I_ 2 = \emptyset)\) and there is a \(j \in J\) (the set of columns of \(A)\) such that \(a_{ij} = a_{i'j} \neq 0\), or \(a_{ij} = - a_{i'j} \neq 0\), then \(i \in I_ 1\), \(i' \in I_ 2\) or \(i \in I_ 2\), \(i' \in I_ 1\). A direct constructive proof of results is given in the main theorem, giving a complete characterization of the total set of all partitions which satisfy Q.1 when \(A\) is totally unimodular. Thus it is shown for a given class of matrices, how total unimodularity may be determined, affirmatively or negatively, and how a characterization of total unimodularity may be determined in terms of its permissible requisite partitions.