AFTD Auto-Formalizing Theoretical Domains

op223_matrix_spectral_lower

theoremverified

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
Used by 1

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.

  1. 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.

    lines 9–10

    uses op223_matrix_spectrum_abs_le, le_of_not_gt

      by_contra hn
      have hs := op223_matrix_spectrum_abs_le A t ht (le_of_not_gt hn)
  2. 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.

    lines 11–13

    uses Matrix.posSemidef_iff_isHermitian_and_spectrum_nonneg.mpr

      have hPSD : ((algebraMap ℝ (Matrix n n ℝ)) t - A).PosSemidef := by
        apply Matrix.posSemidef_iff_isHermitian_and_spectrum_nonneg.mpr
        constructor
  3. 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.

    lines 14–15

    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
  4. 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.

    lines 16–23

    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]
  5. 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.

    line 24

      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.

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

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]
See it in the graphDiscuss this resultChallenge it