A generalization of Tutte's characterization of totally unimodular matrices
type: Item
instance of: scholarly article
title: A generalization of Tutte's characterization of totally unimodular matrices
zbMATH Open document ID: 0885.05041
published in: Journal of Combinatorial Theory. Series B
publication date: 1998-04-20T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05B20
Mathematics Subject Classification ID: 05B35
Mathematics Subject Classification ID: 05C50
zbMATH DE Number: 1076873
zbMATH Keywords: minors
zbMATH Keywords: matroid
author: James F. Geelen
reviewed by: Brigitte Servatius
MaRDI profile type: Publication
OpenAlex ID: W2071547261
cites work: Greedy algorithm and symmetric matroids
cites work: Unimodularity and circle graphs
cites work: Q3490007
cites work: A characterization of unimodular orientations of simple graphs
cites work: Principally unimodular skew-symmetric matrices
cites work: Representability of \(\bigtriangleup\)-matroids over \(GF(2)\)
cites work: Q5737094
cites work: Q4003375
cites work: A short proof of Tutte's characterization of totally unimodular matrices
cites work: Alpha-balanced graphs and matrices and GF(3)-representability of matroids
cites work: Q3249424
cites work: Lectures on matroids
DOI: 10.1006/JCTB.1997.1751
description: scientific article; zbMATH DE number 1076873