A hierarchy of totally unimodular matrices

✍ Scribed by Martin Loebl; Svatopluk Poljak

• Publisher: Elsevier Science
• Year: 1989
• Tongue: English
• Weight: 556 KB
• Volume: 76
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(89)90322-1

✦ Synopsis

We say that a totally unimodular matrix is k-totally unimodular (k-TU), if every matrix obtained from it by setting to zero a subset of at most k entries is still totally unimodular. We present the following results.

(i) A matrix is restricted unimodular if and only if it is 3-TU, (ii) for a 2-TU matrix, the blocks of some associated graph are either complete bipartite graphs or restricted unimodular, (iii) we give a simple direct proof to a theorem by Crama, Hammer and Ibaraki: 'A matrix is I-TU if and only if all its nonsingular submatrices are triangular'.