Lemma C.2, p.27 — block Cauchy–Schwarz inequalities (C.4), (C.5)
ProvedMatrixSpencer.lemma_C_2gaussian-measurematrix-discrepancymatrix-spencerp2o-gran-per-chapterp2o-plan-paperp2o-v1partial-coloringrandom-matrices
Let be symmetric matrices and . Then
and
These estimate the terms in the curvature identity.
Differences from the source:
- encoding: ℝ^{d×d}) (a misprinted parenthesis) and ℝᵈ ⊗ ℝʳ → Matrix (Fin d) (Fin d) ℝ and Fin d × Fin r → ℝ; reason: the evident meaning; ⊗ is the Kronecker product
- encoding: (·)^{1/2} of the double sums → √ of the double sums; reason: the sums are nonnegative, as squared Euclidean norms
Preamble
import Mathlib open Matrix open scoped Kronecker
Formal statement
namespace MatrixSpencer
/-- **Lemma C.2.**
Akbas, Sra, *A Proof of the Matrix Spencer Conjecture*, arXiv:2608.28816 (held file sha256 3e56f6a1…), Lemma C.2, p.27 (PDF p.29): "Let C₁, …, Cₙ, D₁, …, Dₙ ∈ ℝ^{d×d}) be symmetric matrices and let z₁, …, zₙ ∈
ℝᵈ ⊗ ℝʳ. Then, we have that |Σⁿᵢ,ⱼ₌₁ ⟨zᵢ, (CⱼCᵢ ⊗ I)zⱼ⟩| ≤ Σⁿᵢ,ⱼ₌₁ Tr(CᵢCⱼ) ⟨zᵢ, zⱼ⟩, (C.4) and
|Σⁿᵢ,ⱼ₌₁ ⟨zᵢ, (CⱼDᵢ ⊗ I)zⱼ⟩| ≤ (Σⁿᵢ,ⱼ₌₁ Tr(CᵢCⱼ) ⟨zᵢ, zⱼ⟩)^{1/2} (Σⁿᵢ,ⱼ₌₁ Tr(DᵢDⱼ) ⟨zᵢ, zⱼ⟩)^{1/2}. (C.5)"
**Formalization Note.** `ℝᵈ ⊗ ℝʳ` is `Fin d × Fin r → ℝ` and `⊗` the Kronecker product. The two double sums
under the square roots in (C.5) are nonnegative (each is a squared Euclidean norm, as the page's proof
shows), so `√` is the page's `^{1/2}`. -/
theorem lemma_C_2 {n d r : ℕ} (C D : Fin n → Matrix (Fin d) (Fin d) ℝ)
(hC : ∀ i, (C i).IsSymm) (hD : ∀ i, (D i).IsSymm) (z : Fin n → (Fin d × Fin r → ℝ)) :
|∑ i, ∑ j, z i ⬝ᵥ ((C j * C i) ⊗ₖ (1 : Matrix (Fin r) (Fin r) ℝ)) *ᵥ z j| ≤
∑ i, ∑ j, (C i * C j).trace * (z i ⬝ᵥ z j) ∧
|∑ i, ∑ j, z i ⬝ᵥ ((C j * D i) ⊗ₖ (1 : Matrix (Fin r) (Fin r) ℝ)) *ᵥ z j| ≤
√(∑ i, ∑ j, (C i * C j).trace * (z i ⬝ᵥ z j)) *
√(∑ i, ∑ j, (D i * D j).trace * (z i ⬝ᵥ z j)) := by sorry
end MatrixSpencer
Source
E. Akbas, S. Sra, A Proof of the Matrix Spencer Conjecture, arXiv:2608.28816 (held file sha256 3e56f6a1…), Lemma C.2, p.27 (PDF p.29)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.