Variational definition of the nontrivial eigenvalues: iff on (Section 2.4)
ProvedExplicitExpanders.Attach.variational_characterizationlinear-algebrap2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1rayleigh-quotientspectral-graph-theory
Let be a real symmetric matrix indexed by a finite set whose rows all sum to the same number , so that for the all-ones vector . Let . Then the following are equivalent:
- every eigenvalue of that has an eigenvector with satisfies ;
- for every real vector with ,
This is the variational definition of the nontrivial eigenvalues that the paper invokes twice in the proof of Theorem 1.2: from 2 to 1 for the constructed graph , after establishing inequality (1) for all unit vectors orthogonal to ; and from 1 to 2 for the Ramanujan graph , to bound by for unit vectors orthogonal to the constant vector.
Formalization Note The paper's normalisation is replaced by the homogeneous form , which is equivalent by scaling.
Preamble
import Mathlib
Formal statement
namespace ExplicitExpanders.Attach
open Matrix
/-- Variational definition of the nontrivial eigenvalues (arXiv:2003.11673v1, §2.4, p. 8):
for a real symmetric matrix `A` whose rows all sum to `k` and every `λ ≥ 0`, every eigenvalue of
`A` with an eigenvector orthogonal to the constant vector has absolute value at most `λ` if and
only if `|fᵗ A f| ≤ λ ‖f‖²` for every real vector `f` with `∑ f = 0`. -/
theorem variational_characterization {ι : Type*} [Fintype ι] (A : Matrix ι ι ℝ) (hA : A.IsSymm)
(k : ℝ) (hrow : A *ᵥ 1 = k • 1) (lam : ℝ) (hlam : 0 ≤ lam) :
(∀ (μ : ℝ) (f : ι → ℝ), f ≠ 0 → ∑ i, f i = 0 → A *ᵥ f = μ • f → |μ| ≤ lam) ↔
(∀ f : ι → ℝ, ∑ i, f i = 0 → |f ⬝ᵥ (A *ᵥ f)| ≤ lam * (f ⬝ᵥ f)) := by sorry
end ExplicitExpanders.Attach
Source
N. Alon, Explicit expanders of every degree and size, arXiv:2003.11673v1, p. 8, Section 2.4, sentence before (1) (variational definition of the nontrivial eigenvalues); used again on p. 9 for H
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.