standardized_laplacian_eigenvalue_gershgorin_disc
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
- standardized_laplacian_eigenvalue_re_nonnegEvery complex eigenvalue z of a standardized Laplacian matrix of order n has nonnegative real part.
- standardized_laplacian_order_four_im_le_three_quartersFor any standardized Laplacian matrix L of order 4, the imaginary part of every complex eigenvalue z satisfies |Im z| ≤ 3/4.
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.
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).
uses
Matrix.spectrum_toLin',Module.End.HasEigenvalue.of_mem_spectrumhave h1 : z ∈ spectrum ℂ (Matrix.toLin' (L.map (algebraMap ℝ ℂ))) := by rw [Matrix.spectrum_toLin'] exact hz have h2 := Module.End.HasEigenvalue.of_mem_spectrum h1
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.
uses
eigenvalue_mem_ballobtain ⟨k, hk⟩ := eigenvalue_mem_ball h2 use k
‖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.
uses
Metric.mem_closedBall,dist_eq_normhave 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'
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.
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_univhave 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
‖z - L k k‖ ≤ L k k.
Substituting the simplified radius L k k into the Gershgorin inequality concludes the proof.
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
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.
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'