standardized_laplacian_order_four_im_le_three_quarters
For any standardized Laplacian matrix L of order 4, the imaginary part of every complex eigenvalue z satisfies |Im z| ≤ 3/4.
Statement
theorem standardized_laplacian_order_four_im_le_three_quarters (L : Matrix (Fin 4) (Fin 4) ℝ)
(hL : is_standardized_laplacian 4 L) (z : ℂ)
(hz : z ∈ spectrum ℂ (L.map (algebraMap ℝ ℂ))) :
|z.im| ≤ (3 : ℝ) / 4- Source
- step towards op_465_standardized_laplacian_order_four_polygon_conjecture
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- standardized_laplacian_eigenvalue_gershgorin_discFor a standardized Laplacian matrix L of order n, every complex eigenvalue z is contained in some Gershgorin disc centred at a diagonal…
- 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].
The proof, explained
The proof uses Gershgorin's disc theorem for standardized Laplacians to place the eigenvalue z in a disc centered at a diagonal entry L k k with radius L k k, meaning ‖z - L k k‖ ≤ L k k. Since L k k is real, the imaginary part is preserved under centering, giving |z.im| ≤ ‖z - L k k‖. Because row sums are zero and each off-diagonal entry satisfies -1/4 ≤ L k j ≤ 0, the diagonal entry L k k equals the sum of 3 negated off-diagonal entries, each bounded by 1/4, so L k k ≤ 3/4. Chaining these bounds yields |z.im| ≤ 3/4.
There exists a row index k such that the eigenvalue z lies in the k-th Gershgorin disc: ‖z - L k k‖ ≤ L k k.
By Gershgorin's disc theorem adapted for standardized Laplacians (standardized_laplacian_eigenvalue_gershgorin_disc), every eigenvalue z of L is contained in the Gershgorin disc centered at some diagonal entry L k k with radius L k k.
uses
standardized_laplacian_eigenvalue_gershgorin_discobtain ⟨k, hk⟩ := standardized_laplacian_eigenvalue_gershgorin_disc 4 L hL z hz|z.im| ≤ ‖z - L k k‖
Because the matrix entry L k k is a real number, its imaginary part is zero (Complex.ofReal_im), so (z - L k k).im = z.im (Complex.sub_im). The absolute value of the imaginary part of any complex number is bounded by its complex modulus (Complex.abs_im_le_norm).
uses
Complex.sub_im,Complex.ofReal_im,Complex.abs_im_le_normhave h_im_le : |z.im| ≤ ‖z - (L k k : ℂ)‖ := by have h_im_eq : z.im = (z - (L k k : ℂ)).im := by simp [Complex.sub_im, Complex.ofReal_im] rw [h_im_eq] exact Complex.abs_im_le_norm (z - (L k k : ℂ))
The diagonal entry L k k equals the sum of the negated off-diagonal entries in its row: L k k = ∑ j ≠ k, -L k j.
In a standardized Laplacian, every row sums to zero (hL.1 k). Separating the diagonal entry L k k from the off-diagonal sum over Finset.univ.erase k (Finset.add_sum_erase, Finset.mem_univ) gives L k k + ∑ j ≠ k, L k j = 0. Factoring out negation (Finset.sum_neg_distrib) and rearranging by linear arithmetic gives L k k = ∑ j ≠ k, -L k j. Substituting this expression reduces bounding L k k to bounding the sum of negated off-diagonal entries.
uses
Finset.add_sum_erase,Finset.mem_univ,Finset.sum_neg_distribhave h_diag_le : L k k ≤ (3 : ℝ) / 4 := by have h_row := hL.1 k have h_off := hL.2 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) rw [h_row] at h_split have h_diag : L k k = ∑ j ∈ Finset.univ.erase k, -L k j := by rw [Finset.sum_neg_distrib] linarith rw [h_diag]
For each off-diagonal index j ≠ k, -L k j ≤ 1 / 4.
For any j distinct from k (Finset.ne_of_mem_erase), the definition of a standardized Laplacian of order 4 (hL.2) ensures that -1 / 4 ≤ L k j. Negating this inequality yields -L k j ≤ 1 / 4.
uses
Finset.ne_of_mem_erasehave h_le : ∀ j ∈ Finset.univ.erase k, -L k j ≤ (1 : ℝ) / 4 := by intro j hj have h_ne : k ≠ j := (Finset.ne_of_mem_erase hj).symm have := (h_off k j h_ne).1 linarith
L k k ≤ 3 / 4
Summing the termwise inequality -L k j ≤ 1 / 4 over all j ≠ k (Finset.sum_le_sum) bounds the off-diagonal sum by the sum of 1 / 4 over the 3 remaining indices (Finset.card_erase_of_mem, Finset.mem_univ). The constant sum evaluates to 3 * (1 / 4) = 3 / 4 (Finset.sum_const, nsmul_eq_mul), from which linear arithmetic establishes L k k ≤ 3 / 4.
uses
Finset.sum_le_sum,Finset.card_erase_of_mem,Finset.mem_univ,Finset.sum_const,nsmul_eq_mulhave h_sum_le := Finset.sum_le_sum h_le have h_card : (Finset.univ.erase k).card = 3 := by rw [Finset.card_erase_of_mem (Finset.mem_univ k)] simp have h_const : ∑ j ∈ Finset.univ.erase k, ((1 : ℝ) / 4) = (3 : ℝ) / 4 := by rw [Finset.sum_const, h_card, nsmul_eq_mul] ring linarith
|z.im| ≤ 3 / 4
Linear arithmetic combines the three inequalities |z.im| ≤ ‖z - L k k‖, ‖z - L k k‖ ≤ L k k, and L k k ≤ 3 / 4 to conclude that |z.im| ≤ 3 / 4.
linarith
standardized_laplacian_eigenvalue_gershgorin_disc- For any complex eigenvalue z of a standardized Laplacian matrix of order n, there exists a row index k such that ‖z - L k k‖ ≤ L k k.
Complex.abs_im_le_norm- The absolute value of the imaginary part of a complex number is at most its complex norm: |z.im| ≤ ‖z‖.
Complex.sub_im- The imaginary part of a difference of complex numbers is the difference of their imaginary parts: (z - w).im = z.im - w.im.
Complex.ofReal_im- The imaginary part of a real number regarded as a complex number is zero: (r : ℂ).im = 0.
Finset.add_sum_erase- A sum over a finite set s can be split into the value at a chosen element a ∈ s and the sum over s \ {a}.
Finset.mem_univ- Every element of a finite type belongs to its universal Finset univ.
Finset.sum_neg_distrib- Negation distributes over a finite sum: ∑ x ∈ s, -f x = -∑ x ∈ s, f x.
Finset.ne_of_mem_erase- If an element b belongs to s \ {a}, then b ≠ a.
Finset.sum_le_sum- If f i ≤ g i for every element i in a finite set s, then ∑ i ∈ s, f i ≤ ∑ i ∈ s, g i.
Finset.card_erase_of_mem- Removing an element a from a finite set s decreases its cardinality by one: (s \ {a}).card = s.card - 1.
Finset.sum_const- Summing a constant value b over a finite set s equals s.card • b.
nsmul_eq_mul- Scalar multiplication by a natural number n coincides with multiplication by n in a semiring: n • a = n * 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
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_order_four_im_le_three_quarters (L : Matrix (Fin 4) (Fin 4) ℝ) (hL : is_standardized_laplacian 4 L) (z : ℂ) (hz : z ∈ spectrum ℂ (L.map (algebraMap ℝ ℂ))) : |z.im| ≤ (3 : ℝ) / 4 := by obtain ⟨k, hk⟩ := standardized_laplacian_eigenvalue_gershgorin_disc 4 L hL z hz have h_im_le : |z.im| ≤ ‖z - (L k k : ℂ)‖ := by have h_im_eq : z.im = (z - (L k k : ℂ)).im := by simp [Complex.sub_im, Complex.ofReal_im] rw [h_im_eq] exact Complex.abs_im_le_norm (z - (L k k : ℂ)) have h_diag_le : L k k ≤ (3 : ℝ) / 4 := by have h_row := hL.1 k have h_off := hL.2 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) rw [h_row] at h_split have h_diag : L k k = ∑ j ∈ Finset.univ.erase k, -L k j := by rw [Finset.sum_neg_distrib] linarith rw [h_diag] have h_le : ∀ j ∈ Finset.univ.erase k, -L k j ≤ (1 : ℝ) / 4 := by intro j hj have h_ne : k ≠ j := (Finset.ne_of_mem_erase hj).symm have := (h_off k j h_ne).1 linarith have h_sum_le := Finset.sum_le_sum h_le have h_card : (Finset.univ.erase k).card = 3 := by rw [Finset.card_erase_of_mem (Finset.mem_univ k)] simp have h_const : ∑ j ∈ Finset.univ.erase k, ((1 : ℝ) / 4) = (3 : ℝ) / 4 := by rw [Finset.sum_const, h_card, nsmul_eq_mul] ring linarith linarith