Proof of Corollary 3.5, first display — distortion ≤ c iff a PSD A has d²ᵢⱼ ≤ aᵢᵢ + aⱼⱼ − 2aᵢⱼ ≤ c²d²ᵢⱼ
ProvedGeometryOfGraphs.EuclidDist.gram_reformulationLet be a finite semi-metric space, with points indexed by , and let . Then embeds in a Euclidean space with distortion at most if and only if there is a real positive semidefinite matrix such that
Here . The quantity is the squared distance between the -th and -th points when is the Gram matrix of a point configuration. The statement is the first display of the proof of Corollary 3.5 (p. 224), which recalls the observation made in the proof of Theorem 3.2, Claim 2 (p. 221): there for the matrix whose rows are the images of a distortion- embedding, and ; the two forms differ by the scaling .
The reformulation turns the existence of an embedding into the feasibility of a semidefinite system, linear in , which is what the duality argument of Corollary 3.5 analyses.
Formalization Note is a Matrix X X ℝ with Matrix.PosSemidef (which includes symmetry). The inequalities are required for all ordered pairs , including , where they read . The distortion notion is the contractive one of the definition EuclideanDistortion.
import Mathlib import Definitions.Def_GeometryOfGraphs_EuclidDist_EuclideanDistortion
namespace GeometryOfGraphs.EuclidDist
/-- Proof of Corollary 3.5, first display (p. 224), cf. proof of Theorem 3.2, Claim 2 (p. 221):
a finite metric space embeds in Euclidean space with distortion at most `c` iff some positive
semidefinite matrix `A` satisfies `d i j ^ 2 ≤ a_ii + a_jj - 2 a_ij ≤ c ^ 2 * d i j ^ 2`. -/
theorem gram_reformulation {X : Type*} [Fintype X] [DecidableEq X]
(d : X → X → ℝ) (hd : GeometryOfGraphs.FlowCut.IsPseudometric d) (c : ℝ) (hc : 1 ≤ c) :
EmbedsEuclidean d 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 := by sorry
end GeometryOfGraphs.EuclidDist
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.