Proof of Proposition 2.2, pp. 377–378 — if a ≠ b, every coupling in U(a, b) has a nonzero off-diagonal entry
ProvedCompOT.Metric.prop_2_2_offdiag_massoptimal-transportp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1transportation-polytope
Let with , and let . Then has a nonzero element outside the diagonal:
This is the combinatorial half of the positivity of for : a coupling supported on the diagonal has equal row and column sums, so it only couples a histogram with itself.
Formalization Note Indices are Fin n.
Preamble
import Mathlib import Definitions.Def_CompOT_Metric_Defs
Formal statement
namespace CompOT.Metric
open Matrix
/-- Proof of Proposition 2.2, pp. 377–378: if `a ≠ b`, an admissible coupling
`P ∈ U(a, b)` necessarily has a nonzero element outside the diagonal. -/
theorem prop_2_2_offdiag_mass {n : ℕ} (a b : Fin n → ℝ)
(ha : a ∈ stdSimplex ℝ (Fin n)) (hb : b ∈ stdSimplex ℝ (Fin n)) (hab : a ≠ b)
(P : Matrix (Fin n) (Fin n) ℝ) (hP : P ∈ CompOT.Assignment.couplings a b) :
∃ i j, i ≠ j ∧ P i j ≠ 0 := by sorry
end CompOT.Metric
Source
Peyré & Cuturi, Computational Optimal Transport (FnT ML 2019), proof of Proposition 2.2, pp. 377–378
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.