This article was accepted into the corpus but its outbound wikilinks were never NER-processed — typical at the deepest BFS hop or when the run's entity cap was reached. No expansion funnel to show.
| Totally unimodular matrices | |
|---|---|
| Name | Totally unimodular matrices |
| Field | Linear algebra, Combinatorics, Optimization |
| Introduced | 1950s |
| Notable | Hassler Whitney, Paul Erdős, Jack Edmonds, Tibor Gallai, George Dantzig |
Totally unimodular matrices are integer matrices whose every square submatrix has determinant −1, 0, or 1. They form a fundamental class of matrices that links Linear algebra, Combinatorics, Graph theory, Integer programming, and Polyhedral combinatorics: coefficient matrices that are totally unimodular guarantee integral extreme points of associated polyhedra and thus connect to classical results involving George Dantzig, John von Neumann, Leonid Kantorovich, Jack Edmonds, and Tibor Gallai.
A matrix A with entries in {−1, 0, 1} is called totally unimodular if every square submatrix has determinant in {−1, 0, 1}. This property implies that every subdeterminant is bounded by 1 in absolute value, so any integral right-hand side b ensures that linear systems A x ≤ b, A x = b, or related polyhedra have integral vertices; this links to results by George Dantzig on the Simplex method, John Nash in equilibrium computation contexts, and algorithmic work associated with Jack Edmonds. Totally unimodular matrices are closed under transposition and signed permutation of rows or columns, and their submatrices inherit total unimodularity; these invariances parallel symmetries studied by Hassler Whitney and structural graph theorems of Paul Erdős.
Canonical examples include incidence matrices of bipartite graphs: the vertex-edge incidence matrix of a bipartite graph is totally unimodular, relating to work by Konrad Apt and classical graph theory results of Tibor Gallai and Claude Berge. Network flow node-arc incidence matrices for directed graphs without capacity lower bounds are totally unimodular, connecting to the Max flow–min cut theorem and contributions by L. R. Ford Jr. and D. R. Fulkerson. Totally unimodular matrices arise from unimodular matrices in lattice theory studied by Hassler Whitney and in totally unimodular matrices encountered in Matroid theory via Jack Edmonds and W. T. Tutte. Counterexamples include incidence matrices of non-bipartite graphs such as odd cycles (e.g., the triangle) and certain node-edge incidence structures that produce 2×2 minors with determinant 2, a phenomenon analyzed in combinatorial constructions by Paul Erdős and Endre Szemerédi.
Several equivalent criteria identify total unimodularity: Ghouila-Houri’s criterion gives a row-signing condition linking to combinatorial matrix theory; Seymour’s decomposition theorem characterizes totally unimodular matrices via 1-, 2-, and 3-sums of network matrices and a specific 10×10 excluded minor, reflecting deep connections to Paul Seymour’s work in Graph minors and Matroid theory. Other equivalent formulations use unimodularity of every basis submatrix, integrality of polyhedra described by A, and combinatorial descriptions via signed bipartitions that echo structural theorems by Hassler Whitney and W. T. Tutte. These characterizations are instrumental in the theoretical frameworks developed by Jack Edmonds and Paul Seymour.
Total unimodularity is preserved under transposition, multiplication by −1 of rows or columns, and deletion of rows or columns; these closure properties mirror operations studied in Matroid theory by H. Whitney and in matrix transformation theory associated with C. R. Rao. Row or column permutations preserve the property, and adding unit columns or rows under controlled sign patterns often yields new totally unimodular matrices. However, general matrix multiplication may destroy total unimodularity unless special structure (e.g., network matrices) is maintained, a limitation observed in algorithmic contexts involving George Dantzig’s polyhedral methods and Jack Edmonds’ combinatorial optimization frameworks.
Totally unimodular matrices underlie polynomial-time solvability of many integer programs by linear programming relaxation: if A is totally unimodular and b is integral, then linear programs like maximize c^T x subject to A x ≤ b have integral optimal solutions, a principle applied in Network flow theory (work of L. R. Ford Jr. and D. R. Fulkerson), in matching problems solved by Jack Edmonds, and in scheduling and assignment problems associated with the Hungarian algorithm developed by Harold Kuhn drawing on earlier ideas by Dénes Kőnig. Applications extend to combinatorial designs studied by Paul Erdős and to polyhedral studies by Günter M. Ziegler and Miklós Ajtai.
Recognition algorithms for total unimodularity leverage Seymour’s decomposition and graph-based reductions; deterministic polynomial-time procedures exist through decomposition into network matrices and testing for excluded minors, building on algorithmic graph theory by Paul Seymour and Neil Robertson. Practical testing often uses linear algebraic checks of minors or Ghouila-Houri type row-signing constructions; implementations in optimization software draw on techniques from George Dantzig’s linear programming literature and algorithmic advances by Jack Edmonds and Michael J. Todd. Complexity results relate to matrix minor testing adjacent to work on Graph minors by Neil Robertson and Paul Seymour.
The theory emerged in mid-20th-century developments linking Linear algebra and Combinatorics with optimization, with foundational contributions from researchers influenced by George Dantzig’s linear programming, Hassler Whitney’s matroid theory, and combinatorialists such as Paul Erdős and Jack Edmonds. Key milestones include Ghouila-Houri’s criterion, Seymour’s decomposition theorem for totally unimodular matrices, and the embedding of these ideas in integer programming theory by Jack Edmonds, Tibor Gallai, and others. Subsequent developments connected the subject to Graph minors theory by Neil Robertson and Paul Seymour, to polyhedral combinatorics articulated by Günter M. Ziegler, and to modern algorithmic implementations in network optimization influenced by L. R. Ford Jr. and D. R. Fulkerson.
Category:Linear algebra Category:Combinatorics Category:Integer programming