op223_matrix_spectral_lower
A negative quadratic form for tI minus a Hermitian real matrix certifies that its real spectral radius exceeds t.
Statement
theorem op223_matrix_spectral_lower {n : Type*} [Fintype n] [DecidableEq n] (A : Matrix n n ℝ) (hA : A.IsHermitian) (t : ℝ) (ht : 0 ≤ t) (v : n → ℝ) (hv : star v ⬝ᵥ (((algebraMap ℝ (Matrix n n ℝ)) t - A) *ᵥ v) < 0) : ENNReal.ofReal t < spectralRadius ℝ A
- Source
- arXiv:2610.17078 Open Problem 6.1; experiments 22883 and 22914
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- op223_matrix_spectrum_abs_leA real matrix whose spectral radius is at most a nonnegative threshold has every real spectral value bounded in absolute value by that…
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearPMap.IsSelfAdjoint.smulLinearPMap.IsSelfAdjoint.smul
- Used by 1
- op223_first_replacement_spectral_lowerReplacing edge 0-1 with 4-2 in the example tree yields a graph whose spectral radius is greater than 209/100.
The proof, explained
The proof proceeds by contradiction. If the spectral radius of the Hermitian matrix A were at most t, then every eigenvalue b of A would satisfy |b| ≤ t. Consequently, all eigenvalues of tI - A would be of the form t - b ≥ 0, which implies that tI - A is positive semidefinite. But a positive semidefinite matrix cannot evaluate to a strictly negative quadratic form on any vector, contradicting the existence of the witness v.
Assuming for contradiction that the spectral radius of A is at most t, every eigenvalue of A has absolute value at most t.
We proceed by contradiction (by_contra). If the spectral radius of A is not strictly greater than t, then by linearity of the order (le_of_not_gt) it is at most t. Because t ≥ 0, op223_matrix_spectrum_abs_le implies that every eigenvalue b in the spectrum of A satisfies |b| ≤ t.
uses
op223_matrix_spectrum_abs_le,le_of_not_gtby_contra hn have hs := op223_matrix_spectrum_abs_le A t ht (le_of_not_gt hn)
To show that tI - A is positive semidefinite, it suffices to show that tI - A is Hermitian and that all of its eigenvalues are non-negative.
By Matrix.posSemidef_iff_isHermitian_and_spectrum_nonneg.mpr, a matrix is positive semidefinite if and only if it is Hermitian and its spectrum is contained in [0, ∞). We split the goal into these two independent conditions.
uses
Matrix.posSemidef_iff_isHermitian_and_spectrum_nonneg.mprhave hPSD : ((algebraMap ℝ (Matrix n n ℝ)) t - A).PosSemidef := by apply Matrix.posSemidef_iff_isHermitian_and_spectrum_nonneg.mpr constructor
The matrix tI - A is Hermitian.
The scalar matrix tI is the scalar multiplication of the identity matrix by t (Algebra.algebraMap_eq_smul_one). Since t ∈ ℝ is self-adjoint (isSelfAdjoint_iff), tI is Hermitian (Matrix.isHermitian_one.smul). The difference of two Hermitian matrices is Hermitian, and A is Hermitian by assumption, so tI - A is Hermitian.
uses
Algebra.algebraMap_eq_smul_one,Matrix.isHermitian_one.smul,isSelfAdjoint_iff· rw [Algebra.algebraMap_eq_smul_one] exact (Matrix.isHermitian_one.smul (by simp [isSelfAdjoint_iff] : IsSelfAdjoint t)).sub hA
Every eigenvalue of tI - A is non-negative, which establishes that tI - A is positive semidefinite.
Let z be an eigenvalue of tI - A. By spectral translation (spectrum.singleton_sub_eq), z = t - b for some eigenvalue b of A (Set.mem_singleton_iff). Since |b| ≤ t, we have b ≤ t by abs_le.mp, so z = t - b ≥ 0. Having satisfied both conditions, tI - A is positive semidefinite.
uses
spectrum.singleton_sub_eq,Set.mem_singleton_iff,abs_le.mp· intro z hz rw [← spectrum.singleton_sub_eq] at hz obtain ⟨a, ha, b, hb, rfl⟩ := hz simp only [Set.mem_singleton_iff] at ha subst a have := hs b hb change 0 ≤ t - b linarith [abs_le.mp this]
The quadratic form v* (tI - A) v must be non-negative, contradicting the hypothesis that it is strictly negative.
Because tI - A is positive semidefinite, the quadratic form v* (tI - A) v is non-negative for any vector v. This directly contradicts the assumption hv that v* (tI - A) v < 0, closing the proof.
linarith [hPSD.dotProduct_mulVec_nonneg v]
abs_le.mp- The inequality |a| ≤ b implies -b ≤ a ≤ b.
Algebra.algebraMap_eq_smul_one- The canonical algebra map embeds a scalar r as the scalar multiple r • 1.
isSelfAdjoint_iff- An element x is self-adjoint if and only if star x = x.
le_of_not_gt- In a linear order, if b is not strictly greater than a, then a ≤ b.
Matrix.isHermitian_one.smul- Multiplying the identity matrix by a self-adjoint scalar produces a Hermitian matrix.
Matrix.posSemidef_iff_isHermitian_and_spectrum_nonneg.mpr- A matrix is positive semidefinite if it is Hermitian and its spectrum is a subset of [0, ∞).
op223_matrix_spectrum_abs_le- For a matrix A and a non-negative real t, if the spectral radius of A is at most t, then every eigenvalue in the spectrum of A has absolute value at most t.
Set.mem_singleton_iff- An element a belongs to {b} if and only if a = b.
spectrum.singleton_sub_eq- The spectrum of rI - a is the set difference {r} - spectrum a, consisting of all numbers r - λ for λ in the spectrum of a.
- In Lean, the spectral radius takes values in ENNReal (the extended non-negative real numbers [0, ∞]), so the real parameter t is embedded via ENNReal.ofReal.
- The self-adjointness of the real scalar t in line 15 is dispatched by simp [isSelfAdjoint_iff], since the star operation on ℝ is the identity map.
- The final contradiction on line 24 is discharged by linarith, which combines the non-negativity of the quadratic form for a positive semidefinite matrix with the strict negativity assumed in hv.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open Matrixopen scoped ENNRealtheorem op223_matrix_spectral_lower {n : Type*} [Fintype n] [DecidableEq n] (A : Matrix n n ℝ) (hA : A.IsHermitian) (t : ℝ) (ht : 0 ≤ t) (v : n → ℝ) (hv : star v ⬝ᵥ (((algebraMap ℝ (Matrix n n ℝ)) t - A) *ᵥ v) < 0) : ENNReal.ofReal t < spectralRadius ℝ A := by by_contra hn have hs := op223_matrix_spectrum_abs_le A t ht (le_of_not_gt hn) have hPSD : ((algebraMap ℝ (Matrix n n ℝ)) t - A).PosSemidef := by apply Matrix.posSemidef_iff_isHermitian_and_spectrum_nonneg.mpr constructor · rw [Algebra.algebraMap_eq_smul_one] exact (Matrix.isHermitian_one.smul (by simp [isSelfAdjoint_iff] : IsSelfAdjoint t)).sub hA · intro z hz rw [← spectrum.singleton_sub_eq] at hz obtain ⟨a, ha, b, hb, rfl⟩ := hz simp only [Set.mem_singleton_iff] at ha subst a have := hs b hb change 0 ≤ t - b linarith [abs_le.mp this] linarith [hPSD.dotProduct_mulVec_nonneg v]