Proposition 3.6 — a symmetric P is PSD iff Σᵢⱼ pᵢⱼ yᵢⱼ ≥ 0 for every PSD Y
ProvedGeometryOfGraphs.EuclidDist.proposition_3_6Let be a finite index set and let be a real symmetric matrix. Then is positive semidefinite if and only if
In other words, the cone of real symmetric positive semidefinite matrices is self-dual under the trace pairing . The paper uses it as the complete list of linear inequalities defining , which is what the duality step in the proof of Corollary 3.5 needs.
Formalization Note The page says "a matrix belongs to ", and is defined on the same page as a cone of symmetric matrices. The hypothesis that is symmetric (P.IsSymm) is therefore made explicit: without it the "if" direction would be false, since a nonzero antisymmetric pairs to with every symmetric . Matrices are indexed by an arbitrary finite type rather than .
import Mathlib
namespace GeometryOfGraphs.EuclidDist
/-- Proposition 3.6 (p. 224): a real symmetric matrix `P` is positive semidefinite iff
`∑_{i,j} p_ij * y_ij ≥ 0` for every positive semidefinite `Y`. -/
theorem proposition_3_6 {X : Type*} [Fintype X] [DecidableEq X]
(P : Matrix X X ℝ) (hP : P.IsSymm) :
P.PosSemidef ↔
∀ Y : Matrix X X ℝ, Y.PosSemidef → 0 ≤ ∑ i, ∑ j, P i j * Y i j := by sorry
end GeometryOfGraphs.EuclidDist
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.