AFTD Auto-Formalizing Theoretical Domains

standardized_laplacian_order_four_im_le_re

theoremverified

For any standardized Laplacian matrix L of order 4, the imaginary part and real part of every complex eigenvalue z of L satisfy |Im(z)| ≤ Re(z).

Statement

theorem standardized_laplacian_order_four_im_le_re (L : Matrix (Fin 4) (Fin 4) ℝ)
    (hL : is_standardized_laplacian 4 L)
    (z : ℂ) (hz : z ∈ spectrum ℂ (L.map (algebraMap ℝ ℂ))) :
    |z.im| ≤ z.re
Source
step towards standardized_laplacian_order_four_polygon_conjecture
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8
Used by 1

The proof, explained

The proof proceeds by perturbation and reduction to a known sector bound for order 4 Laplacians with a strictly positive stationary vector. For a nonzero eigenvalue z, it suffices to establish |Im(z)| ≤ Re(z) + δ for every δ > 0. The argument introduces the centered perturbation K = L + δ I - (δ / 4) J, which retains zero row sums and non-positive off-diagonal entries while admitting a strictly positive stationary distribution. Using an eigenvector shift lemma, z + δ is shown to be an eigenvalue of K, so the stationary sector bound yields |Im(z + δ)| ≤ Re(z + δ), which simplifies directly to |Im(z)| ≤ Re(z) + δ.

  1. The real part of z is non-negative, and the theorem holds trivially when z = 0.

    Applying `standardized_laplacian_eigenvalue_re_nonneg` shows Re(z) ≥ 0. A case split on whether z = 0 disposes of the zero eigenvalue immediately, since |Im(0)| = 0 ≤ 0 = Re(0).

    lines 6–8

    uses standardized_laplacian_eigenvalue_re_nonneg

      have hzre := standardized_laplacian_eigenvalue_re_nonneg 4 L hL z hz
      by_cases hz0 : z = 0
      · simp [hz0]
  2. There exists a non-zero eigenvector v ≠ 0 such that L v = z v.

    Assuming z ≠ 0, transferring the spectrum of the matrix to that of the linear operator via `Matrix.spectrum_toLin'` and applying `Module.End.HasEigenvalue.of_mem_spectrum` and `Module.End.HasEigenvalue.exists_hasEigenvector` yields a non-zero eigenvector v. Translating eigenspace membership to matrix-vector multiplication with `Module.End.mem_eigenspace_iff.mp` gives L v = z v.

    lines 9–13

    uses Matrix.spectrum_toLin', Module.End.HasEigenvalue.of_mem_spectrum, Module.End.HasEigenvalue.exists_hasEigenvector, Module.End.mem_eigenspace_iff.mp

      have he : z ∈ spectrum ℂ (Matrix.toLin' (L.map (algebraMap ℝ ℂ))) := by
        rwa [Matrix.spectrum_toLin']
      obtain ⟨v, hve, hv0⟩ := (Module.End.HasEigenvalue.of_mem_spectrum he).exists_hasEigenvector
      have hv : (L.map (algebraMap ℝ ℂ)).mulVec v = z • v :=
        Module.End.mem_eigenspace_iff.mp hve
  3. It suffices to prove |Im(z)| ≤ Re(z) + δ for every δ > 0.

    By `le_of_forall_pos_le_add`, an inequality a ≤ b between real numbers holds if a ≤ b + δ for all δ > 0. We fix an arbitrary δ > 0.

    lines 14–15

    uses le_of_forall_pos_le_add

      apply le_of_forall_pos_le_add
      intro δ hδ
  4. The perturbed matrix K = L + δ I - (δ / 4) J has zero row sums, non-positive off-diagonal entries, and a strictly positive stationary vector π.

    The centered perturbation K is defined by shifting the diagonal of L by δ and subtracting δ/4 from each entry. By `matrix_order_four_centered_shift_row_sum`, row sums remain zero. For distinct indices i ≠ j, rewriting with `if_neg` leaves L i j - δ/4, which is non-positive by linear arithmetic since L i j ≤ 0 and δ > 0. Lemma `standardized_laplacian_order_four_perturbation_stationary` provides a strictly positive vector π with π^T K = 0.

    lines 16–23

    uses matrix_order_four_centered_shift_row_sum, if_neg, standardized_laplacian_order_four_perturbation_stationary

      let K := matrix_order_four_centered_shift L δ
      have hrK : ∀ i, ∑ j, K i j = 0 := matrix_order_four_centered_shift_row_sum L hL.1 δ
      have hoK : ∀ i j, i ≠ j → K i j ≤ 0 := by
        intro i j hij
        dsimp only [K, matrix_order_four_centered_shift]
        rw [if_neg hij]
        linarith [(hL.2 i j hij).2]
      obtain ⟨π, hπ, hstat⟩ := standardized_laplacian_order_four_perturbation_stationary L hL δ hδ
  5. The shifted eigenvalue candidate z + δ is non-zero.

    If z + δ = 0, taking the real part via `congrArg` and simplifying with `Complex.add_re`, `Complex.ofReal_re`, and `Complex.zero_re` yields Re(z) + δ = 0, which contradicts Re(z) ≥ 0 and δ > 0 by linear arithmetic.

    lines 24–28

    uses congrArg, Complex.add_re, Complex.ofReal_re, Complex.zero_re

      have hlam : z + (δ : ℂ) ≠ 0 := by
        intro hh
        have hre := congrArg Complex.re hh
        simp only [Complex.add_re, Complex.ofReal_re, Complex.zero_re] at hre
        linarith
  6. The matrix K maps v to (z + δ) v - (δ / 4) (∑_j v j) 1.

    Rewriting with `matrix_order_four_centered_shift_mulVec` and using L v = z v, the action of K on v is expanded. Applying `Pi.smul_apply` and `smul_eq_mul` to equate componentwise, the identity reduces by ring arithmetic.

    lines 29–34

    uses matrix_order_four_centered_shift_mulVec, Pi.smul_apply, smul_eq_mul

      have hKv : (K.map (algebraMap ℝ ℂ)).mulVec v =
          fun i => (z + (δ : ℂ)) * v i - (δ : ℂ) / 4 * ∑ j, v j := by
        rw [matrix_order_four_centered_shift_mulVec, hv]
        ext i
        simp only [Pi.smul_apply, smul_eq_mul]
        ring
  7. There exists a non-zero eigenvector w ≠ 0 of K with eigenvalue z + δ.

    Because L and K have zero row sums, z ≠ 0, z + δ ≠ 0, and K v = (z + δ) v + c 1 for the constant c = -(δ / 4) ∑_j v j, `matrix_row_sum_zero_shifted_eigenvector` produces a non-zero vector w such that K w = (z + δ) w.

    lines 35–39

    uses matrix_row_sum_zero_shifted_eigenvector

      obtain ⟨w, hw0, hw⟩ := matrix_row_sum_zero_shifted_eigenvector L K hL.1 hrK v hv0 z hz0 hv
        (z + (δ : ℂ)) (-(δ : ℂ) / 4 * ∑ j, v j) hlam (by
          rw [hKv]
          ext i
          ring)
  8. |Im(z)| ≤ Re(z) + δ holds, concluding the proof.

    Since K has zero row sums, non-positive off-diagonal entries, and a strictly positive stationary vector, `laplacian_order_four_stationary_eigenvalue_sector` implies that its eigenvalue z + δ satisfies |Im(z + δ)| ≤ Re(z + δ). Decomposing the real and imaginary parts using `Complex.add_re`, `Complex.add_im`, `Complex.ofReal_re`, `Complex.ofReal_im`, and `add_zero` simplifies this to |Im(z)| ≤ Re(z) + δ, which closes the goal.

    lines 40–43

    uses laplacian_order_four_stationary_eigenvalue_sector, Complex.add_re, Complex.add_im, Complex.ofReal_re, Complex.ofReal_im, add_zero

      have hb := laplacian_order_four_stationary_eigenvalue_sector K π hπ hrK hoK hstat w hw0
        (z + (δ : ℂ)) hw
      simpa only [Complex.add_re, Complex.add_im, Complex.ofReal_re,
        Complex.ofReal_im, add_zero] using hb
standardized_laplacian_eigenvalue_re_nonneg
For any standardized Laplacian matrix L of order n, every complex eigenvalue z has non-negative real part (0 ≤ Re(z)).
Matrix.spectrum_toLin'
The spectrum of a matrix A equals the spectrum of its associated linear transformation Matrix.toLin' A.
Module.End.HasEigenvalue.of_mem_spectrum
On a finite-dimensional module over a field, any element of the spectrum of an endomorphism is an eigenvalue.
Module.End.HasEigenvalue.exists_hasEigenvector
If an endomorphism has an eigenvalue μ, there exists a non-zero eigenvector for μ.
Module.End.mem_eigenspace_iff.mp
A vector v is in the eigenspace of an endomorphism f for eigenvalue μ if and only if f(v) = μ • v.
le_of_forall_pos_le_add
A real inequality a ≤ b holds if a ≤ b + ε for every positive ε > 0.
matrix_order_four_centered_shift_row_sum
For any 4 × 4 matrix L with zero row sums, the centered shift matrix K = L + b I - (b / 4) J also has zero row sums.
if_neg
If a condition c is false, then (if c then t else e) evaluates to e.
standardized_laplacian_order_four_perturbation_stationary
For any standardized Laplacian matrix L of order 4 and any δ > 0, the perturbed matrix admits a strictly positive stationary vector π (π i > 0 for all i and ∑_i π i * K i j = 0).
congrArg
If two terms are equal, applying any function to both sides yields equal terms (a₁ = a₂ → f a₁ = f a₂).
Complex.add_re
The real part of a sum of complex numbers is the sum of their real parts: Re(z + w) = Re(z) + Re(w).
Complex.ofReal_re
The real part of a real number coerced to the complex numbers is the number itself: Re(↑r) = r.
Complex.zero_re
The real part of 0 is 0.
matrix_order_four_centered_shift_mulVec
Matrix-vector multiplication by the centered shift matrix K satisfies (K v) i = (L v) i + b * v i - (b / 4) * ∑_j v j.
Pi.smul_apply
Evaluating a scalar multiple of a function at an argument gives the scalar multiple of the evaluated function: (a • f) i = a • f i.
smul_eq_mul
Scalar multiplication on numbers coincides with standard multiplication: a • b = a * b.
matrix_row_sum_zero_shifted_eigenvector
If L and K are 4 × 4 matrices with zero row sums, v ≠ 0 is an eigenvector of L with eigenvalue z ≠ 0, and K v = λ v + c 1 for some λ ≠ 0 and constant c, then K has an eigenvector w ≠ 0 with eigenvalue λ.
laplacian_order_four_stationary_eigenvalue_sector
For any 4 × 4 matrix K with zero row sums, non-positive off-diagonal entries, and a strictly positive stationary vector, every eigenvalue λ satisfies |Im(λ)| ≤ Re(λ).
Complex.add_im
The imaginary part of a sum of complex numbers is the sum of their imaginary parts: Im(z + w) = Im(z) + Im(w).
Complex.ofReal_im
The imaginary part of a real number coerced to the complex numbers is 0: Im(↑r) = 0.
add_zero
Adding zero to an element leaves it unchanged: a + 0 = 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

/-- For any standardized Laplacian matrix L of order 4, the imaginary and real parts of every eigenvalue z satisfy |Im(z)| ≤ Re(z). -/theorem standardized_laplacian_order_four_im_le_re (L : Matrix (Fin 4) (Fin 4) ℝ)    (hL : is_standardized_laplacian 4 L)    (z : ℂ) (hz : z ∈ spectrum ℂ (L.map (algebraMap ℝ ℂ))) :    |z.im| ≤ z.re := by  have hzre := standardized_laplacian_eigenvalue_re_nonneg 4 L hL z hz  by_cases hz0 : z = 0  · simp [hz0]  have he : z ∈ spectrum ℂ (Matrix.toLin' (L.map (algebraMap ℝ ℂ))) := by    rwa [Matrix.spectrum_toLin']  obtain ⟨v, hve, hv0⟩ := (Module.End.HasEigenvalue.of_mem_spectrum he).exists_hasEigenvector  have hv : (L.map (algebraMap ℝ ℂ)).mulVec v = z • v :=    Module.End.mem_eigenspace_iff.mp hve  apply le_of_forall_pos_le_add  intro δ hδ  let K := matrix_order_four_centered_shift L δ  have hrK : ∀ i, ∑ j, K i j = 0 := matrix_order_four_centered_shift_row_sum L hL.1 δ  have hoK : ∀ i j, i ≠ j → K i j ≤ 0 := by    intro i j hij    dsimp only [K, matrix_order_four_centered_shift]    rw [if_neg hij]    linarith [(hL.2 i j hij).2]  obtain ⟨π, hπ, hstat⟩ := standardized_laplacian_order_four_perturbation_stationary L hL δ hδ  have hlam : z + (δ : ℂ) ≠ 0 := by    intro hh    have hre := congrArg Complex.re hh    simp only [Complex.add_re, Complex.ofReal_re, Complex.zero_re] at hre    linarith  have hKv : (K.map (algebraMap ℝ ℂ)).mulVec v =      fun i => (z + (δ : ℂ)) * v i - (δ : ℂ) / 4 * ∑ j, v j := by    rw [matrix_order_four_centered_shift_mulVec, hv]    ext i    simp only [Pi.smul_apply, smul_eq_mul]    ring  obtain ⟨w, hw0, hw⟩ := matrix_row_sum_zero_shifted_eigenvector L K hL.1 hrK v hv0 z hz0 hv    (z + (δ : ℂ)) (-(δ : ℂ) / 4 * ∑ j, v j) hlam (by      rw [hKv]      ext i      ring)  have hb := laplacian_order_four_stationary_eigenvalue_sector K π hπ hrK hoK hstat w hw0    (z + (δ : ℂ)) hw  simpa only [Complex.add_re, Complex.add_im, Complex.ofReal_re,    Complex.ofReal_im, add_zero] using hb
See it in the graphDiscuss this resultChallenge it