A generalization of Tutte's characterization of totally unimodular matrices (Q1369653): Difference between revisions

Symmetric \((0, 1)\)-matrices that can be signed symmetrically so that every principle submatrix has determinant \(0\), \(1\) or \(-1\) (PU-matrices) are characterized via 5 excluded minors under reduction. This theorem is a generalization of Tutte's characterization of totally unimodular matrices (see \textit{W. T. Tutte} [Introduction to the theory of matroids (1971; Zbl 0231.05027)]) and the proof essentially generalizes Gerards' short proof of Tutte's result (see \textit{A. M. H. Gerards} [Linear Algebra Appl. 114/115, 207-212 (1989; Zbl 0676.05028)]). The techniques are mainly graphical and a result of \textit{K. Trümper} [J. Comb. Theory, Ser. B 32, 112-139 (1982; Zbl 0465.05022)] is used to streamline the case analysis. Tutte originally formulated his result in terms of regular matroids (chain groups): A binary matroid is regular if and only if it does not contain the Fano matroid or its dual as a minor. The matroid analog of the above result is the following: A delta matroid can be represented over every field by a symmetric matrix if and only if it can be represented by a symmetric PU-matrix.