Proof of Corollary 3.5, duality step — no PSD A satisfies all J_{i,j} iff a PSD Q and a nonnegative combination of the J_{i,j} give a contradiction
ProvedGeometryOfGraphs.EuclidDist.duality_alternativeLet be a finite semi-metric space and . For consider the pair of inequalities in the unknown matrix
Then no real positive semidefinite matrix satisfies every if and only if there exist a real positive semidefinite matrix and nonnegative multipliers such that, for every matrix ,
and the constant on the right is negative:
This is the theorem of alternatives invoked on pp. 224–225 in the proof of Corollary 3.5: "the conclusion of the Corollary is incorrect, i.e., no such matrix exists, iff there is a matrix such that the inequality contradicts some nonnegative combination of the inequalities ." The identity says that adding to times the left part and times the right part of each eliminates every -term, and the negative constant is the contradiction .
Formalization Note "Contradicts some nonnegative combination" is made precise as the exact cancellation identity above (holding for all matrices , an identity of linear forms) together with a negative constant term; and are written lam and mu. Pairs are ordered and include . The number multiplying loses no generality, since can be rescaled.
import Mathlib import Definitions.Def_GeometryOfGraphs_EuclidDist_EuclideanDistortion
namespace GeometryOfGraphs.EuclidDist
/-- Proof of Corollary 3.5, duality step (pp. 224–225): no positive semidefinite `A` satisfies the
inequalities `J_ij : c^2 d_ij^2 ≥ a_ii + a_jj - 2 a_ij ≥ d_ij^2` iff there are a positive
semidefinite `Q` and nonnegative multipliers `lam, mu` such that adding
`∑ a_ij q_ij ≥ 0` to the combination `∑ lam_ij (upper J_ij) + mu_ij (lower J_ij)` cancels every
`a`-term and leaves a negative constant on the right, i.e. a contradiction. -/
theorem duality_alternative {X : Type*} [Fintype X] [DecidableEq X]
(d : X → X → ℝ) (hd : GeometryOfGraphs.FlowCut.IsPseudometric d) (c : ℝ) (hc : 1 ≤ c) :
(¬ ∃ A : Matrix X X ℝ, A.PosSemidef ∧
∀ i j, d i j ^ 2 ≤ A i i + A j j - 2 * A i j ∧
A i i + A j j - 2 * A i j ≤ c ^ 2 * d i j ^ 2) ↔
∃ Q : Matrix X X ℝ, Q.PosSemidef ∧
∃ lam mu : X → X → ℝ, (∀ i j, 0 ≤ lam i j) ∧ (∀ i j, 0 ≤ mu i j) ∧
(∀ A : Matrix X X ℝ,
(∑ i, ∑ j, Q i j * A i j) +
∑ i, ∑ j, (lam i j * (c ^ 2 * d i j ^ 2 - (A i i + A j j - 2 * A i j)) +
mu i j * ((A i i + A j j - 2 * A i j) - d i j ^ 2)) =
∑ i, ∑ j, (lam i j * (c ^ 2 * d i j ^ 2) - mu i j * d i j ^ 2)) ∧
∑ i, ∑ j, (lam i j * (c ^ 2 * d i j ^ 2) - mu i j * d i j ^ 2) < 0 := by sorry
end GeometryOfGraphs.EuclidDist
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.