AFTD Auto-Formalizing Theoretical Domains

op223_matrix_spectral_upper

theoremverified

If both tI minus A and tI plus A are positive semidefinite, the real spectral radius of A is at most t.

Statement

theorem op223_matrix_spectral_upper {n : Type*} [Fintype n] [DecidableEq n]
    (A : Matrix n n ℝ) (t : ℝ)
    (hminus : ((algebraMap ℝ (Matrix n n ℝ)) t - A).PosSemidef)
    (hplus : ((algebraMap ℝ (Matrix n n ℝ)) t + A).PosSemidef) :
    spectralRadius ℝ A ≤ ENNReal.ofReal t
Source
arXiv:2610.17078 Open Problem 6.1; experiments 22883 and 22914
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

The spectral radius of $A$ is the supremum of the absolute values of its real eigenvalues $z \in \operatorname{spectrum}_{\mathbb{R}}(A)$. Since $tI - A$ and $tI + A$ are positive semidefinite, their spectra consist entirely of non-negative reals. For any eigenvalue $z$ of $A$, the numbers $t - z$ and $t + z$ lie in the spectra of $tI - A$ and $tI + A$ respectively, giving $t - z \ge 0$ and $t + z \ge 0$. Together, these inequalities imply $-t \le z \le t$, or equivalently $|z| \le t$, bounding the spectral radius by $t$.

  1. To bound the spectral radius of $A$ by $t$, it suffices to show that $|z| \le t$ for every eigenvalue $z \in \operatorname{spectrum}_{\mathbb{R}}(A)$.

    The spectral radius is defined as the supremum of the absolute values of the eigenvalues in $\operatorname{spectrum}_{\mathbb{R}}(A)$. Applying `iSup_le` twice reduces bounding the supremum to bounding the magnitude of an arbitrary eigenvalue $z \in \operatorname{spectrum}_{\mathbb{R}}(A)$.

    lines 9–13

    uses iSup_le

      unfold spectralRadius
      apply iSup_le
      intro z
      apply iSup_le
      intro hz
  2. The eigenvalue $z$ satisfies $0 \le t - z$ (that is, $z \le t$).

    Since $tI - A$ is positive semidefinite (`hminus`), its spectrum contains only non-negative reals by `Matrix.posSemidef_iff_isHermitian_and_spectrum_nonneg.mp`. By the spectral shift formula `spectrum.singleton_sub_eq`, $\operatorname{spectrum}(tI - A) = \{t\} - \operatorname{spectrum}_{\mathbb{R}}(A)$. Because $t \in \{t\}$ and $z \in \operatorname{spectrum}_{\mathbb{R}}(A)$, their difference $t - z$ belongs to the spectrum of $tI - A$ by `Set.sub_mem_sub`, and is therefore non-negative.

    lines 14–17

    uses Matrix.posSemidef_iff_isHermitian_and_spectrum_nonneg.mp, spectrum.singleton_sub_eq, Set.sub_mem_sub

      have hm : 0 ≤ t - z := by
        apply (Matrix.posSemidef_iff_isHermitian_and_spectrum_nonneg.mp hminus).2
        rw [← spectrum.singleton_sub_eq]
        exact Set.sub_mem_sub (by simp) hz
  3. The eigenvalue $z$ satisfies $0 \le t + z$ (that is, $-t \le z$).

    Similarly, because $tI + A$ is positive semidefinite (`hplus`), its spectrum consists of non-negative reals. By `spectrum.singleton_add_eq`, the spectrum of $tI + A$ is $\{t\} + \operatorname{spectrum}_{\mathbb{R}}(A)$. Since $t \in \{t\}$ and $z \in \operatorname{spectrum}_{\mathbb{R}}(A)$, their sum $t + z$ belongs to $\{t\} + \operatorname{spectrum}_{\mathbb{R}}(A)$ by `Set.add_mem_add`, which implies $0 \le t + z$.

    lines 18–21

    uses Matrix.posSemidef_iff_isHermitian_and_spectrum_nonneg.mp, spectrum.singleton_add_eq, Set.add_mem_add

      have hp : 0 ≤ t + z := by
        apply (Matrix.posSemidef_iff_isHermitian_and_spectrum_nonneg.mp hplus).2
        rw [← spectrum.singleton_add_eq]
        exact Set.add_mem_add (by simp) hz
  4. The magnitude $|z|$ is at most $t$, which implies the eigenvalue magnitude bound.

    Translating the non-negative real norm to `ENNReal.ofReal` via `ENNReal.coe_nnreal_eq` and `ENNReal.ofReal_le_ofReal`, the goal simplifies to $|z| \le t$. By `abs_le.mpr`, this is equivalent to $-t \le z$ and $z \le t$, both of which follow by linear arithmetic (`linarith`) from $0 \le t + z$ and $0 \le t - z$.

    lines 22–25

    uses ENNReal.coe_nnreal_eq, ENNReal.ofReal_le_ofReal, abs_le.mpr

      rw [ENNReal.coe_nnreal_eq]
      apply ENNReal.ofReal_le_ofReal
      change |z| ≤ t
      exact abs_le.mpr ⟨by linarith, by linarith⟩
iSup_le
An indexed supremum is bounded above by a constant if and only if each term in the family is bounded by that constant.
Matrix.posSemidef_iff_isHermitian_and_spectrum_nonneg.mp
If a matrix is positive semidefinite, then it is Hermitian and its spectrum contains only non-negative real numbers.
spectrum.singleton_sub_eq
For an element $a$ in an algebra and a scalar $r$, the spectrum of $rI - a$ equals the set difference $\{r\} - \operatorname{spectrum}(a)$.
Set.sub_mem_sub
If $a \in s$ and $b \in t$, then $a - b \in s - t$.
spectrum.singleton_add_eq
For an element $a$ in an algebra and a scalar $r$, the spectrum of $rI + a$ equals the set sum $\{r\} + \operatorname{spectrum}(a)$.
Set.add_mem_add
If $a \in s$ and $b \in t$, then $a + b \in s + t$.
ENNReal.coe_nnreal_eq
The coercion of a non-negative real $r$ into the extended non-negative reals equals $\operatorname{ofReal}(r)$.
ENNReal.ofReal_le_ofReal
If $p \le q$ in $\mathbb{R}$, then $\operatorname{ofReal}(p) \le \operatorname{ofReal}(q)$ in the extended non-negative reals.
abs_le.mpr
If $-t \le z$ and $z \le t$, then $|z| \le t$.

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_upper {n : Type*} [Fintype n] [DecidableEq n]    (A : Matrix n n ℝ) (t : ℝ)    (hminus : ((algebraMap ℝ (Matrix n n ℝ)) t - A).PosSemidef)    (hplus : ((algebraMap ℝ (Matrix n n ℝ)) t + A).PosSemidef) :    spectralRadius ℝ A ≤ ENNReal.ofReal t := by  unfold spectralRadius  apply iSup_le  intro z  apply iSup_le  intro hz  have hm : 0 ≤ t - z := by    apply (Matrix.posSemidef_iff_isHermitian_and_spectrum_nonneg.mp hminus).2    rw [← spectrum.singleton_sub_eq]    exact Set.sub_mem_sub (by simp) hz  have hp : 0 ≤ t + z := by    apply (Matrix.posSemidef_iff_isHermitian_and_spectrum_nonneg.mp hplus).2    rw [← spectrum.singleton_add_eq]    exact Set.add_mem_add (by simp) hz  rw [ENNReal.coe_nnreal_eq]  apply ENNReal.ofReal_le_ofReal  change |z| ≤ t  exact abs_le.mpr ⟨by linarith, by linarith⟩
See it in the graphDiscuss this resultChallenge it