Proof of Proposition 3.4, p. 407 — for P ≥ 0 the edges of G(P) correspond to the nonzero entries of P
ProvedCompOT.Vertices.prop_3_4_edges_eq_nonzerobipartite-graphoptimal-transportp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1transportation-polytope
Let have nonnegative entries (for instance ). Then the number of edges of the support graph equals the number of nonzero entries of :
Together with the forest edge bound this converts " has no cycles" into " has at most nonzero entries".
Formalization Note Edges of are undirected pairs of the simple graph on Fin n ⊕ Fin m; the nonnegativity hypothesis is what makes and the same condition.
Preamble
import Mathlib import Definitions.Def_CompOT_Vertices_Defs
Formal statement
namespace CompOT.Vertices
/-- End of the proof of Proposition 3.4, p. 407: for a matrix `P` with nonnegative entries
(in particular for `P ∈ U(a, b)`), the edges of the support graph `G(P)` are in bijection
with the nonzero entries of `P`, so `|S(P)|` equals the number of nonzero entries. -/
theorem prop_3_4_edges_eq_nonzero {n m : ℕ} (P : Matrix (Fin n) (Fin m) ℝ)
(hP : ∀ i j, 0 ≤ P i j) :
Nat.card (supportGraph P).edgeSet = (nonzeroEntries P).card := by sorry
end CompOT.Vertices
Source
Peyré & Cuturi, Computational Optimal Transport (FnT ML 2019), §3.4.1, end of the proof of Proposition 3.4, p. 407
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.