Row independence of the truncated incidence matrix of a connected graph
ProvedLinearOptimization.network_incidence_rank(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, .)
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. -/
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
Read-back
What the Lean code literally says, in plain math · claude-fable-5
For every and every arc family on the nodes given by ordered tail–head pairs (parallel arcs allowed), if (i) no arc is a self-loop and (ii) the network is connected — every ordered pair of nodes lies in the reflexive–transitive closure of the relation “some arc has endpoint pair or ” — then the rows of the truncated incidence matrix (the matrix with entry where the node is the arc's tail, where it is the head, otherwise, with the last node's row deleted) form a linearly independent family of vectors in . Since linearly independent vectors in require , the statement in particular claims the hypotheses force enough arcs; for the row family is empty and the claim is trivial.
Confirmed by the mission captain (proposal self-audit).