Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Variational definition of the nontrivial eigenvalues: ∣μ∣≤λ|\mu|\le\lambda∣μ∣≤λ iff ∣ftAf∣≤λ∥f∥2|f^tAf|\le\lambda\|f\|^2∣ftAf∣≤λ∥f∥2 on 1⊥\mathbf 1^\perp1⊥ (Section 2.4)

Proved
ExplicitExpanders.Attach.variational_characterization

by mikedeng1 · Oct 5, 2026 · Mathlib 0df444a (Lean v4.33.1)

linear-algebrap2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1rayleigh-quotientspectral-graph-theory

Let AAA be a real symmetric matrix indexed by a finite set ι\iotaι whose rows all sum to the same number kkk, so that A1=k1A\mathbf 1=k\mathbf 1A1=k1 for the all-ones vector 1\mathbf 11. Let λ≥0\lambda\ge 0λ≥0. Then the following are equivalent:

  1. every eigenvalue μ\muμ of AAA that has an eigenvector f≠0f\neq 0f=0 with ∑if(i)=0\sum_i f(i)=0∑i​f(i)=0 satisfies ∣μ∣≤λ|\mu|\le\lambda∣μ∣≤λ;
  2. for every real vector fff with ∑if(i)=0\sum_i f(i)=0∑i​f(i)=0,
∣ftAf∣≤λ ∥f∥22.|f^{t}Af|\le\lambda\,\|f\|_2^2 .∣ftAf∣≤λ∥f∥22​.

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 GGG, after establishing inequality (1) for all unit vectors orthogonal to 1\mathbf 11; and from 1 to 2 for the Ramanujan graph HHH, to bound ∣htAHh∣|h^tA_Hh|∣htAH​h∣ by 2p2\sqrt p2p​ for unit vectors hhh orthogonal to the constant vector.

Formalization Note The paper's normalisation ∥f∥22=1\|f\|_2^2=1∥f∥22​=1 is replaced by the homogeneous form ∣ftAf∣≤λ ftf|f^tAf|\le\lambda\, f^tf∣ftAf∣≤λftf, 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
  • Endorsed by Shuze Chen · Oct 5, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 5, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me