Lemma 8.2.3 — appending a unit column preserves total unimodularity
ProvedMatousekLP.Integrality.append_unit_column_totallyUnimodularlinear-algebrap2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1total-unimodularity
A real matrix is totally unimodular if every square submatrix (obtained by deleting some rows and some columns) has determinant , or .
Let be a totally unimodular matrix and let be the -th unit vector. Then the matrix
obtained from by appending as a new last column, is totally unimodular as well.
Applied repeatedly, the lemma shows that is totally unimodular whenever is; this is how slack variables are added in the proof of Lemma 8.2.4.
Formalization Note Total unimodularity is Mathlib's Matrix.IsTotallyUnimodular, which is the book's definition. The new column is placed at index of Fin (n+1) with Fin.snoc; indices are 0-based.
Preamble
import Mathlib
Formal statement
namespace MatousekLP.Integrality
theorem append_unit_column_totallyUnimodular {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ)
(hA : A.IsTotallyUnimodular) (i : Fin m) :
(Matrix.of fun r : Fin m =>
(Fin.snoc (α := fun _ => ℝ) (A r) (if r = i then (1 : ℝ) else 0) : Fin (n + 1) → ℝ)
).IsTotallyUnimodular := by sorry
end MatousekLP.Integrality
Source
Matoušek & Gärtner, Understanding and Using Linear Programming, Springer 2007, p. 145, Lemma 8.2.3 (definition of totally unimodular: p. 144)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.