AFTD Auto-Formalizing Theoretical Domains

standardized_laplacian_eigenvalue_gershgorin_disc

theoremverified

For a standardized Laplacian matrix L of order n, every complex eigenvalue z is contained in some Gershgorin disc centred at a diagonal entry: there is a row index k with ‖z − L k k‖ ≤ L k k.

Statement

theorem standardized_laplacian_eigenvalue_gershgorin_disc (n : ℕ) (L : Matrix (Fin n) (Fin n) ℝ)
    (hL : is_standardized_laplacian n L) (z : ℂ)
    (hz : z ∈ spectrum ℂ (L.map (algebraMap ℝ ℂ))) :
    ∃ k : Fin n, ‖z - (L k k : ℂ)‖ ≤ L k k
Source
step towards op_465_standardized_laplacian_order_four_polygon_conjecture
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • is_standardized_laplacianA standardized Laplacian matrix of order n is a real n x n matrix with zero row sums and off-diagonal entries in [-1/n, 0].
Used by 2

The proof, explained

The proof applies the Gershgorin circle theorem to the complex matrix L, which ensures that any eigenvalue z lies in some disc centred at L k k with radius equal to the sum of the off-diagonal norms ∑_{j ≠ k} ‖L k j‖. Because L is a standardized Laplacian, all off-diagonal entries are nonpositive (so ‖L k j‖ = -L k j) and every row sums to zero (L k k + ∑_{j ≠ k} L k j = 0). Consequently, the Gershgorin radius -∑_{j ≠ k} L k j is precisely L k k, which establishes ‖z - L k k‖ ≤ L k k.

  1. The complex number z is an eigenvalue of the linear endomorphism induced by L.

    The spectrum of a matrix coincides with the spectrum of its induced linear map (Matrix.spectrum_toLin'), and on a finite-dimensional space every value in the spectrum of an endomorphism is an eigenvalue (Module.End.HasEigenvalue.of_mem_spectrum).

    lines 5–8

    uses Matrix.spectrum_toLin', Module.End.HasEigenvalue.of_mem_spectrum

      have h1 : z ∈ spectrum ℂ (Matrix.toLin' (L.map (algebraMap ℝ ℂ))) := by
        rw [Matrix.spectrum_toLin']
        exact hz
      have h2 := Module.End.HasEigenvalue.of_mem_spectrum h1
  2. There is an index k such that z lies in the Gershgorin disc associated with row k.

    By Gershgorin's circle theorem (eigenvalue_mem_ball), any eigenvalue of a matrix belongs to the closed ball around some diagonal entry with radius equal to the sum of the norms of the off-diagonal entries in that row. We choose this row index k.

    lines 9–10

    uses eigenvalue_mem_ball

      obtain ⟨k, hk⟩ := eigenvalue_mem_ball h2
      use k
  3. ‖z - L k k‖ ≤ ∑ j ≠ k, ‖L k j‖.

    Rewriting membership in the closed ball (Metric.mem_closedBall) via the metric distance formula in normed spaces (dist_eq_norm) yields the Gershgorin inequality, and the complex diagonal entry is identified with the real entry L k k.

    lines 11–15

    uses Metric.mem_closedBall, dist_eq_norm

      have hk' : ‖z - (L.map (algebraMap ℝ ℂ) k k)‖ ≤ ∑ j ∈ Finset.univ.erase k, ‖(L.map (algebraMap ℝ ℂ)) k j‖ := by
        rw [Metric.mem_closedBall, dist_eq_norm] at hk
        exact hk
      have h_diag : (L.map (algebraMap ℝ ℂ)) k k = (L k k : ℂ) := rfl
      rw [h_diag] at hk'
  4. The Gershgorin radius ∑ j ≠ k, ‖L k j‖ equals L k k.

    Because L is a standardized Laplacian, off-diagonal entries satisfy L k j ≤ 0 for j ≠ k, so their complex norms equal -L k j (Complex.norm_real, Real.norm_of_nonpos). Summing these terms yields -∑ j ≠ k, L k j (Finset.sum_congr, Finset.sum_neg_distrib). Furthermore, row k sums to zero, and decomposing the row sum into the diagonal entry and off-diagonal entries (Finset.add_sum_erase, Finset.mem_univ) shows that L k k + ∑ j ≠ k, L k j = 0, from which linear arithmetic yields -∑ j ≠ k, L k j = L k k.

    lines 16–29

    uses Finset.ne_of_mem_erase, Complex.norm_real, Real.norm_of_nonpos, Finset.sum_congr, Finset.sum_neg_distrib, Finset.add_sum_erase, Finset.mem_univ

      have h_rad : ∑ j ∈ Finset.univ.erase k, ‖(L.map (algebraMap ℝ ℂ)) k j‖ = L k k := by
        have h_row := hL.1 k
        have h_off := hL.2
        have h_norm : ∀ j ∈ Finset.univ.erase k, ‖(L.map (algebraMap ℝ ℂ)) k j‖ = - L k j := by
          intro j hj
          have h_ne : k ≠ j := (Finset.ne_of_mem_erase hj).symm
          have h_le : L k j ≤ 0 := (h_off k j h_ne).2
          have : (L.map (algebraMap ℝ ℂ)) k j = (L k j : ℂ) := rfl
          rw [this, Complex.norm_real, Real.norm_of_nonpos h_le]
        rw [Finset.sum_congr rfl h_norm]
        rw [Finset.sum_neg_distrib]
        have h_split : L k k + ∑ j ∈ Finset.univ.erase k, L k j = ∑ j, L k j :=
          Finset.add_sum_erase Finset.univ (fun j => L k j) (Finset.mem_univ k)
        linarith
  5. ‖z - L k k‖ ≤ L k k.

    Substituting the simplified radius L k k into the Gershgorin inequality concludes the proof.

    lines 30–31

      rw [h_rad] at hk'
      exact hk'
Matrix.spectrum_toLin'
The spectrum of an endomorphism represented by a matrix equals the spectrum of the matrix itself.
Module.End.HasEigenvalue.of_mem_spectrum
In a finite-dimensional space over a field, any element in the spectrum of an endomorphism is an eigenvalue.
eigenvalue_mem_ball
(Gershgorin circle theorem) Every eigenvalue of a matrix lies in the closed ball centred at some diagonal entry with radius equal to the sum of the norms of the other entries in that row.
Metric.mem_closedBall
A point lies in a closed ball of radius ε around a centre if and only if the distance to the centre is at most ε.
dist_eq_norm
The metric distance between two points in a normed space equals the norm of their difference.
Finset.ne_of_mem_erase
An element belonging to a set with a removed is not equal to a.
Complex.norm_real
The complex norm of a real number embedded into the complex numbers equals its real absolute value.
Real.norm_of_nonpos
The absolute value (norm) of a nonpositive real number r is -r.
Finset.sum_congr
Two finite sums are equal if the index sets are equal and the summands agree on every element.
Finset.sum_neg_distrib
The sum of the negations of terms equals the negation of the sum of the terms.
Finset.add_sum_erase
A term can be factored out of a finite sum: the value at a plus the sum over the remaining elements equals the total sum.
Finset.mem_univ
Every element of a finite type belongs to its universal set Finset.univ.

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

theorem standardized_laplacian_eigenvalue_gershgorin_disc (n : ℕ) (L : Matrix (Fin n) (Fin n) ℝ)    (hL : is_standardized_laplacian n L) (z : ℂ)    (hz : z ∈ spectrum ℂ (L.map (algebraMap ℝ ℂ))) :    ∃ k : Fin n, ‖z - (L k k : ℂ)‖ ≤ L k k := by  have h1 : z ∈ spectrum ℂ (Matrix.toLin' (L.map (algebraMap ℝ ℂ))) := by    rw [Matrix.spectrum_toLin']    exact hz  have h2 := Module.End.HasEigenvalue.of_mem_spectrum h1  obtain ⟨k, hk⟩ := eigenvalue_mem_ball h2  use k  have hk' : ‖z - (L.map (algebraMap ℝ ℂ) k k)‖ ≤ ∑ j ∈ Finset.univ.erase k, ‖(L.map (algebraMap ℝ ℂ)) k j‖ := by    rw [Metric.mem_closedBall, dist_eq_norm] at hk    exact hk  have h_diag : (L.map (algebraMap ℝ ℂ)) k k = (L k k : ℂ) := rfl  rw [h_diag] at hk'  have h_rad : ∑ j ∈ Finset.univ.erase k, ‖(L.map (algebraMap ℝ ℂ)) k j‖ = L k k := by    have h_row := hL.1 k    have h_off := hL.2    have h_norm : ∀ j ∈ Finset.univ.erase k, ‖(L.map (algebraMap ℝ ℂ)) k j‖ = - L k j := by      intro j hj      have h_ne : k ≠ j := (Finset.ne_of_mem_erase hj).symm      have h_le : L k j ≤ 0 := (h_off k j h_ne).2      have : (L.map (algebraMap ℝ ℂ)) k j = (L k j : ℂ) := rfl      rw [this, Complex.norm_real, Real.norm_of_nonpos h_le]    rw [Finset.sum_congr rfl h_norm]    rw [Finset.sum_neg_distrib]    have h_split : L k k + ∑ j ∈ Finset.univ.erase k, L k j = ∑ j, L k j :=      Finset.add_sum_erase Finset.univ (fun j => L k j) (Finset.mem_univ k)    linarith  rw [h_rad] at hk'  exact hk'
See it in the graphDiscuss this resultChallenge it