Integer inverse of a network basis matrix
ProvedLinearOptimization.network_basis_inverse_integerintegralitylinear-programmingnetwork-flow
Let a directed network have vertices and arcs. Delete one row from its node–arc incidence matrix, and select any linearly independent columns to form a square basis matrix . Then every entry of the inverse is integral:
This is the algebraic integrality property behind integer primal and dual basic solutions in network-flow linear programs.
Formalization Note The selected columns are represented by an embedding and linear independence is expressed by IsStdBasis.
Preamble
import Definitions.Def_LinearOptimization_NetworkFlowProblem import Definitions.Def_BasicSolution import Mathlib.LinearAlgebra.Matrix.NonsingularInverse open Matrix open LinearOptimization
Formal statement
theorem LinearOptimization.network_basis_inverse_integer {n m : ℕ}
(arcs : Fin m → Fin (n + 1) × Fin (n + 1))
(B : Fin n ↪ Fin m)
(hB : IsStdBasis (truncatedIncidence arcs) B) :
∀ i j, ∃ z : ℤ,
(basisMatrix (truncatedIncidence arcs) B)⁻¹ i j = (z : ℝ) := by sorrySource
Dimitris Bertsimas and John N. Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, p. 289, Theorem 7.5(a). https://pdfcoffee.com/introduction-to-linear-optimization-by-dimitris-john-n-tsitsiklis-pdf-free.html