A short proof of Tutte's characterization of totally unimodular matrices (Q1122583): Difference between revisions

This paper contains a short and easy proof of the following well-known result of \textit{W. T. Tutte} [``Introduction to the theory of matroids'' (1971; Zbl 0231.05027)] (for references see paper under review here). Let \(\mathcal A\) be a \(\{\) 0,1\(\}\)-matrix. Then the following are equivalent: \begin{itemize} \item[(i)] It is possible to replace some of the 1's in \(\mathcal A\) by \(-1\)'s such that all the subdeterminants in the resulting matrix are 0,1, or \(-1\). \item[(ii)] \(\mathcal A\) cannot be transformed to \[ \left[\begin{matrix} 1 & 1 & 1 & 0\\ 1 & 1 & 0 & 1\\ 1 & 0 & 1 & 1\end{matrix} \right] \] by a series of the following operations: deleting or permuting rows or columns, taking the transposed matrix, and pivoting over GF(2) (i.e. replacing \[ \left[ \begin{array}{c|c} 1&x' \\ \hline y&D \end{array} \right] \quad\text{by}\quad \left[ \begin{array}{c|c} 1&x' \\ \hline y&D-yx' \end{array} \right] \] and deleting minus-signs). \end{itemize} Tutte formulated his result in terms of regular matroids (= regular chain groups): A binary matroid is regular if and only if it has neither the Fano matroid nor its dual as a minor. It is not hard to establish the equivalence of both formulations. Tutte's original proof is very complicated. Shorter and more transparent proofs have been given by \textit{P. D. Seymour} [J. Comb. Theory, Ser. B 26, 159-173 (1979; Zbl 0443.05029)] and \textit{K. Truemper} [``Alpha-balanced graphs and matrices and \(GF(3)\)-representability of matroids'', Working paper, Univ. Texas, Dallas 1978; J. Comb. Theory, Ser. B 32, 112-139 (1982; Zbl 0465.05022)].