Lemma 8.4.7 — Delsarte's matrix is positive semidefinite
ProvedMatousekLP.Codes.delsarte_psdcoding-theoryp2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1semidefinite
Let be a code, let be the matrices with if and otherwise, and let
Then the matrix
is positive semidefinite.
This is Delsarte's original insight; diagonalizing in the Hadamard basis turns it into the Krawtchouk inequalities of the linear program, and replacing it by a semidefinite condition is the starting point of Schrijver's stronger bounds.
Formalization Note Positive semidefiniteness is Mathlib's Matrix.PosSemidef for real matrices: symmetric, with for every real vector indexed by the words.
Preamble
import Mathlib import Definitions.Def_MatousekLP_Codes_Basic import Definitions.Def_MatousekLP_Codes_BoseMesner open Finset
Formal statement
namespace MatousekLP.Codes
/-- Lemma 8.4.7, p. 165: for every code `C ⊆ {0,1}^n`, the `2^n × 2^n` matrix
`M̃ = ∑_{i=0}^n ỹ_i M_i` is positive semidefinite. -/
theorem delsarte_psd {n : ℕ} (C : Finset (Word n)) : (Mtilde C).PosSemidef := by sorry
end MatousekLP.Codes
Source
Matoušek & Gärtner, Understanding and Using Linear Programming, Springer 2007, p. 165, Lemma 8.4.7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.