Existence and uniqueness of the tree solution
ProvedLinearOptimization.network_tree_solution_unique(Bertsimas & Tsitsiklis, Theorem 7.3, p. 281) Let be a set of arcs that form a tree when their direction is ignored. Then, the system of linear equations , and for all , has a unique solution.
(The book's proof: the matrix of the -columns of can be reordered to lower-triangular form with nonzero diagonal, hence is nonsingular — so the columns of associated with the tree arcs form a basis.)
import Definitions.Def_LinearOptimization_TreeSolution open Matrix /-- **Bertsimas & Tsitsiklis, Theorem 7.3 (p. 281).** For a set `T` of arcs forming a tree when direction is ignored (on `n + 1` nodes, so `T` has `n` arcs), the system `Ãf = b̃` together with `f_k = 0` for all `k ∉ T` has a unique solution. -/
theorem LinearOptimization.network_tree_solution_unique {n m : ℕ}
(arcs : Fin m → Fin (n + 1) × Fin (n + 1)) (bsupply : Fin (n + 1) → ℝ)
(hloop : HasNoSelfLoops arcs)
(T : Finset (Fin m)) (hT : IsTreeArcSet arcs T) :
∃! f : Fin m → ℝ,
(truncatedIncidence arcs).mulVec f = truncatedSupply bsupply ∧
∀ k, k ∉ T → f k = 0 := by
sorry
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Setting: a directed multigraph on the nodes with arcs indexed by (each arc an ordered tail–head pair), a supply vector , the hypothesis that no arc is a self-loop, and a finite arc set satisfying the bundle's tree condition on the -node set: (i.e. ) and every pair of nodes is related by the reflexive–transitive closure of either-direction adjacency using only arcs of . Conclusion: there exists a unique () such that (a) the truncated incidence matrix (incidence with the last node's row deleted, an matrix) applied to equals the truncated supply (the first coordinates of ), and (b) for every arc . Neither a balance condition at the last node nor the condition appears anywhere, is not required to be nonnegative, and uniqueness ranges over all real vectors satisfying (a) and (b). The connectivity of the full network is not assumed — only connectivity through .
Confirmed by the mission captain (proposal self-audit).