Claim 4.18 — the eigenvalues of
ProvedTSPSDPGap.claim_4_18integrality-gapp2o-gran-per-chapterp2o-plan-paperp2o-v1semidefinite-programmingtraveling-salesman
Throughout, is even, and (the standing assumptions of §4), , and is the solution (3). The set of eigenvalues of is
where and come from and also from every .
Positive semidefiniteness of (Proposition 4.14) follows by showing these values are nonnegative.
Differences from the source:
- reading: the eigenvalues of 2nY are the listed values → the real spectrum of 2nY equals the set of listed values; reason: the claim lists values, not multiplicities (0 is listed twice)
- encoding: standing assumptions of §4: g even, g groups of n/g vertices, a_i and b_i with denominators g, g − 1, n − g → hypotheses Even g, 2 ≤ g, g ∣ n, g < n; reason: the section's standing assumption (g even) plus the conditions under which (3) and a_i, b_i are defined; given g ∣ n they exclude only n/g ∉ ℕ, g ∈ {0, 1} and n − g = 0
- encoding: Y = 1/(2n)[(J_g − I_g) ⊗ J_{n/g} ⊗ B + I_g ⊗ J_{n/g} ⊗ A + I_g ⊗ I_{n/g} ⊗ (2I_n − A)] (3) → Ymat g n, entrywise: block (p, q) is (1/(2n))·2I_n if p = q, (1/(2n))A if p ≠ q lie in the same group ⌊p/(n/g)⌋, (1/(2n))B otherwise; reason: equal to (3) reindexed by Fin g × Fin (n/g) ≃ Fin n (proved: Solutions/verification/TSPSDPGap_sanity.lean, Ymat_eq_eq3); same matrix
Preamble
import Mathlib import Definitions.Def_TSPSDPGap_Ymat import Definitions.Def_TSPSDPGap_aHat
Formal statement
namespace TSPSDPGap
/-- **Claim 4.18: the eigenvalues of `2nY`.**
Gutekunst & Williamson, *SDP Relaxations of the TSP and Their Integrality Gaps*,
arXiv:1907.09054v1, Claim 4.18, p.23:
"The eigenvalues of 2nY are 0, 2(g/(g−1)) + 2((n−g)/(g−1)) a^(k), 2 − 2a^(k), over
k = 1, ..., n − 1 and 2n, 0, corresponding to k = 0."
**Standing hypotheses (§4, p.14).** `g` is even ("we thus assume that g is even throughout"),
`g ∣ n` ("g equally sized groups of n/g vertices"), `2 ≤ g` and `g < n` (the formulas for
`a_i, b_i` divide by `g − 1` and `n − g`; with `g ∣ n` they exclude only those undefined cases).
The statement: the set of eigenvalues of `2nY` is exactly
`{0, 2n} ∪ {2g/(g−1) + 2(n−g)/(g−1)·a^(k) : 1 ≤ k ≤ n−1} ∪ {2 − 2a^(k) : 1 ≤ k ≤ n−1}`.
**Formalization Note.** `Y = Ymat g n`; eigenvalues as a set (no multiplicities), i.e.
`spectrum ℝ`; `k : ℕ` with `1 ≤ k < n`. -/
theorem claim_4_18 (g n : ℕ) (hg : Even g) (hg2 : 2 ≤ g) (hgn : g ∣ n) (hlt : g < n) :
spectrum ℝ ((2 * (n : ℝ)) • Ymat g n) =
({0, 2 * (n : ℝ)} : Set ℝ) ∪
{x | ∃ k : ℕ, 1 ≤ k ∧ k < n ∧
x = 2 * ((g : ℝ) / ((g : ℝ) - 1)) + 2 * (((n : ℝ) - g) / ((g : ℝ) - 1)) * aHat g n k} ∪
{x | ∃ k : ℕ, 1 ≤ k ∧ k < n ∧ x = 2 - 2 * aHat g n k} := by sorry
end TSPSDPGap
Source
Gutekunst & Williamson, SDP Relaxations of the TSP and Their Integrality Gaps, arXiv:1907.09054v1, Claim 4.18, p.23
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.