A decomposition of strongly unimodular matrices into incidence matrices of digraphs
type: Item
instance of: scholarly article
title: A decomposition of strongly unimodular matrices into incidence matrices of digraphs
zbMATH Open document ID: 0776.05071
DOI: 10.1016/0012-365X(92)90048-K
author: Svatopluk Poljak
author: Yves Crama
author: Martin Loebl
published in: Discrete Mathematics
publication date: 1992-09-27T00:00:00Z
review text: 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.
reviewed by: H. P. Yap
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 15A15
Mathematics Subject Classification ID: 05B20
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 65059
zbMATH Keywords: decomposition
zbMATH Keywords: matrix
zbMATH Keywords: totally unimodular
zbMATH Keywords: strongly unimodular
zbMATH Keywords: digraphs
zbMATH Keywords: incidence matrix
MaRDI profile type: Publication
cites work: Structural properties and recognition of restricted and strongly unimodular matrices
cites work: Strong unimodularity for matrices and hypergraphs
cites work: Q5722271
cites work: Q3236253
cites work: A hierarchy of totally unimodular matrices
cites work: On a Class of Totally Unimodular Matrices
full work available at URL: 0012-365x(92)90048-k
OpenAlex ID: W2025293173
Recommended article: Strong unimodularity for matrices and hypergraphs
Recommended article: Q4031884
Recommended article: \(k\)-sum decomposition of strongly unimodular matrices
Recommended article: A decomposition theory for matroids. V: Testing of matrix total unimodularity
Recommended article: The mod \(p\) rank of incidence matrices for connected uniform hypergraphs
Recommended article: Q5752609
Recommended article: A unified view of graph regularity via matrix decompositions
Recommended article: Q5193056
Recommended article: A decomposition for strongly perfect graphs
description: scientific article; zbMATH DE number 65059