AFTD Auto-Formalizing Theoretical Domains

standardized_laplacian_eigenvalue_re_nonneg

theoremverified

Every complex eigenvalue z of a standardized Laplacian matrix of order n has nonnegative real part.

Statement

theorem standardized_laplacian_eigenvalue_re_nonneg (n : ℕ) (L : Matrix (Fin n) (Fin n) ℝ)
    (hL : is_standardized_laplacian n L) (z : ℂ)
    (hz : z ∈ spectrum ℂ (L.map (algebraMap ℝ ℂ))) :
    0 ≤ z.re
Source
step towards op_465_standardized_laplacian_order_four_polygon_conjecture
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 2

The proof, explained

By the Gershgorin disc theorem for standardized Laplacians, any eigenvalue z lies in a disc centered at some diagonal entry L k k with radius L k k, so ‖z - L k k‖ ≤ L k k. Since the real part of z - L k k is z.re - L k k, its negation L k k - z.re is bounded above by |z.re - L k k| ≤ ‖z - L k k‖ ≤ L k k. Cancelling L k k yields 0 ≤ z.re.

  1. The eigenvalue z lies in the Gershgorin disc centered at L k k with radius L k k for some row index k.

    By the Gershgorin circle theorem specialized to standardized Laplacians (standardized_laplacian_eigenvalue_gershgorin_disc), every eigenvalue z of L belongs to the disc centered at some diagonal entry L k k with radius L k k, meaning ‖z - (L k k : ℂ)‖ ≤ L k k.

    line 5

    uses standardized_laplacian_eigenvalue_gershgorin_disc

      obtain ⟨k, hk⟩ := standardized_laplacian_eigenvalue_gershgorin_disc n L hL z hz
  2. The difference L k k - z.re is bounded above by ‖z - (L k k : ℂ)‖.

    By Complex.abs_re_le_norm, |(z - (L k k : ℂ)).re| ≤ ‖z - (L k k : ℂ)‖. Since L k k is real, (z - (L k k : ℂ)).re simplifies to z.re - L k k. Finally, neg_le_abs gives -(z.re - L k k) ≤ |z.re - L k k|, so L k k - z.re ≤ ‖z - (L k k : ℂ)‖.

    lines 6–8

    uses Complex.abs_re_le_norm, neg_le_abs

      have h1 : |(z - (L k k : ℂ)).re| ≤ ‖z - (L k k : ℂ)‖ := Complex.abs_re_le_norm _
      have h2 : (z - (L k k : ℂ)).re = z.re - L k k := by simp
      have h3 : - (z - (L k k : ℂ)).re ≤ |(z - (L k k : ℂ)).re| := neg_le_abs _
  3. 0 ≤ z.re

    Combining L k k - z.re ≤ ‖z - (L k k : ℂ)‖ with the Gershgorin bound ‖z - (L k k : ℂ)‖ ≤ L k k gives L k k - z.re ≤ L k k. Linear arithmetic (linarith) cancels L k k to deduce 0 ≤ z.re.

    line 9

      linarith
standardized_laplacian_eigenvalue_gershgorin_disc
For any complex eigenvalue z of a standardized Laplacian matrix L, there exists an index k such that ‖z - L k k‖ ≤ L k k.
Complex.abs_re_le_norm
For every complex number z, the absolute value of its real part is bounded by its complex norm: |z.re| ≤ ‖z‖.
neg_le_abs
For any element a of a lattice ordered additive group, -a ≤ |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

theorem standardized_laplacian_eigenvalue_re_nonneg (n : ℕ) (L : Matrix (Fin n) (Fin n) ℝ)    (hL : is_standardized_laplacian n L) (z : ℂ)    (hz : z ∈ spectrum ℂ (L.map (algebraMap ℝ ℂ))) :    0 ≤ z.re := by  obtain ⟨k, hk⟩ := standardized_laplacian_eigenvalue_gershgorin_disc n L hL z hz  have h1 : |(z - (L k k : ℂ)).re| ≤ ‖z - (L k k : ℂ)‖ := Complex.abs_re_le_norm _  have h2 : (z - (L k k : ℂ)).re = z.re - L k k := by simp  have h3 : - (z - (L k k : ℂ)).re ≤ |(z - (L k k : ℂ)).re| := neg_le_abs _  linarith
See it in the graphDiscuss this resultChallenge it