Row independence of the truncated incidence matrix of a connected graph
ProvedLinearOptimization.network_incidence_rankincidence-matrixnetwork-flowsrank
(Bertsimas & Tsitsiklis, Corollary 7.1, p. 282) If the graph is connected, then the matrix has linearly independent rows.
(Here is the truncated node-arc incidence matrix of dimensions , consisting of the first rows of — i.e., the redundant row of flow conservation at the last node is deleted, p. 280. Equivalently, .)
Preamble
import Mathlib.LinearAlgebra.LinearIndependent.Defs import Definitions.Def_LinearOptimization_NetworkFlowProblem open Matrix /-- **Bertsimas & Tsitsiklis, Corollary 7.1 (p. 282).** For a connected graph on `n + 1` nodes, the truncated node-arc incidence matrix `Ã` (last row deleted) has linearly independent rows. -/
Formal statement
theorem LinearOptimization.network_incidence_rank {n m : ℕ}
(arcs : Fin m → Fin (n + 1) × Fin (n + 1))
(hloop : HasNoSelfLoops arcs) (hconn : IsConnectedNetwork arcs) :
LinearIndependent ℝ (fun i => truncatedIncidence arcs i) := by
sorry
Source
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Corollary 7.1, p. 282