Proof of Proposition 3.4, p. 407 — a cycle in G(P) yields a nonzero perturbation E with zero row and column sums, supported on S(P)
ProvedCompOT.Vertices.prop_3_4_cycle_perturbationbipartite-graphcycleoptimal-transportp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1transportation-polytope
Let be an real matrix and let be its support graph on , in which is joined to exactly when . If contains a cycle, then there is a matrix with
This is the combinatorial half of the proof that extremal couplings have acyclic support: a cycle in the support yields a direction along which can be moved in both senses without changing its marginals.
Formalization Note The book scales the entries to ; here the scale is left to the companion statement on feasibility. No assumption on is needed.
Preamble
import Mathlib import Definitions.Def_CompOT_Vertices_Defs
Formal statement
namespace CompOT.Vertices
/-- Proof of Proposition 3.4, p. 407: if the support graph `G(P)` contains a cycle, then
there is a nonzero perturbation matrix `E` whose row sums and column sums all vanish and which is supported on the support of `P`. No hypothesis on `P` is needed. -/
theorem prop_3_4_cycle_perturbation {n m : ℕ} (P : Matrix (Fin n) (Fin m) ℝ)
(hcyc : ¬ (supportGraph P).IsAcyclic) :
∃ E : Matrix (Fin n) (Fin m) ℝ, E ≠ 0 ∧
(∀ i, ∑ j, E i j = 0) ∧ (∀ j, ∑ i, E i j = 0) ∧
(∀ i j, E i j ≠ 0 → 0 < P i j) := by sorry
end CompOT.Vertices
Source
Peyré & Cuturi, Computational Optimal Transport (FnT ML 2019), §3.4.1, proof of Proposition 3.4, p. 407 (construction of the perturbation matrix E)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.