Abstract
A characterisation of totally unimodular matrices is derived from a result of Hoffman and Kruskal. It is similar in spirit to a result of Baum and Trotter. Its relation with some other known characterisations is discussed and in the particular case where the matrices have (0, 1) entries, we derive some properties of the associated unimodular hypergraphs. Similar results for balanced and perfect matrices are also reviewed.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Z. Baranyai, “The edge-coloring of complete hypergraphs, I”,Journal of Combinatorial Theory B26 (1979) 276–294.
S. Baum and L.E. Trotter, “Integer rounding and polyhedral decomposition for totally unimodular systems”, in: R. Henn, B. Korte and W. Oettli, eds.,Arbeitstagung über Operations Research und Optimierung (Springer, Berlin, 1978) pp. 15–23.
S. Baum and L.E. Trotter, “Integer rounding for polymatroid and branching optimization problems, Bonn Univ. O.R./Econ. Inst. Techn. Report no. 78120-OR.
C. Berge,Graphs and hypergraphs (North-Holland, Amsterdam, 1973).
C. Berge, “Balanced matrices”,Mathematical Programming 2 (1972) 19–31.
C. Berge, “Notes sur les bonnes colorations d'un hypergraphe”,Cahiers du Centre d'Etudes de Recherche Opérationnelle 15 (1973) 219–223.
A. Ghouila-Houri, “Caractérisation des matrices totalement unimodulaires”,Comptes rendus de l'Academie des Sciences, Paris 254 (1962) 1192.
M. Gondran, “Matrices totalement unimodulaires”,Bulletin EDF, Série C, 1 (1973) 55–74.
A.J. Hoffman and J.B. Kruskal, “Integral boundary points of convex polyhedra”, in: H.W. Kuhn and A.W. Tucker, eds.,Linear inequalities and related systems (Princeton Univ. Press, Princeton, NJ, 1956) pp. 223–246.
L. Lovasz, “Minimax theorems for hypergraphs”, in: C. Berge and D. Ray-Chaudhuri, eds.,Hypergraph Seminar (Springer, Berlin, 1974) pp. 111–126.
M.W. Padberg, “Characterisations of totally unimodular, balanced and perfect matrices”, in: B. Roy, ed.,Combinatorial programming: Methods and applications (D. Reidel Publ., Dordrecht, Holland, 1975) pp. 275–284.
M.W. Padberg, “A note on the total unimodularity of matrices”,Discrete Mathematics 14 (1976) 273–278.
A. Tamir, “On totally unimodular matrices”,Networks 6 (1976) 373–382.
D. de Werra, “Equitable colorations of graphs”,Revue Française d'Informatique et de Recherche Opérationnelle R-3 (1971) 3–8.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
de Werra, D. On some characterisations of totally unimodular matrices. Mathematical Programming 20, 14–21 (1981). https://doi.org/10.1007/BF01589329
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01589329