AFTD Auto-Formalizing Theoretical Domains

laplacian_order_four_stationary_eigenvalue_one_side

theoremverified

For a real order-four matrix with zero row sums, nonpositive off-diagonal entries, and a strictly positive left null vector, every complex eigenvalue has nonnegative real part plus imaginary part.

Statement

theorem laplacian_order_four_stationary_eigenvalue_one_side
    (L : Matrix (Fin 4) (Fin 4) ℝ) (π : Fin 4 → ℝ)
    (hπ : ∀ i, 0 < π i)
    (hr : ∀ i, ∑ j, L i j = 0)
    (ho : ∀ i j, i ≠ j → L i j ≤ 0)
    (hs : ∀ j, ∑ i, π i * L i j = 0)
    (v : Fin 4 → ℂ) (hv0 : v ≠ 0) (z : ℂ)
    (hv : (L.map (algebraMap ℝ ℂ)).mulVec v = z • v) :
    0 ≤ z.re + z.im
Source
Sector-bound formalization for IN-166; arXiv:math/0508176, Theorem 5.
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
Used by 1

The proof, explained

The theorem shows that any complex eigenvalue z of an order-four Laplacian-like matrix L with zero row sums, nonpositive off-diagonal entries, and a positive stationary vector π satisfies 0 ≤ Re(z) + Im(z). The proof defines balanced edge weights w_{ij} = -π_i L_{ij} and applies a four-vertex cycle-cost theorem to establish that the total sector cost is nonnegative. Using the eigenvalue relation L v = z v, this total cost is shown algebraically to equal (Re(z) + Im(z)) ∑_i π_i |v_i|^2. Since the eigenvector v is nonzero and π is strictly positive, the weighted sum of squared norms is strictly positive, forcing Re(z) + Im(z) to be nonnegative.

  1. Define weights w_{ij} = -π_i L_{ij} and show they are nonnegative off the diagonal: 0 ≤ w_{ij} for all i ≠ j.

    Since π_i > 0, -π_i ≤ 0. The off-diagonal entries of L satisfy L_{ij} ≤ 0 for i ≠ j. The product of two nonpositive real numbers is nonnegative.

    lines 10–13

    uses mul_nonneg_of_nonpos_of_nonpos, neg_nonpos.mpr

      let w : Fin 4 → Fin 4 → ℝ := fun i j => -π i * L i j
      have hw : ∀ i j, i ≠ j → 0 ≤ w i j := by
        intro i j hij
        exact mul_nonneg_of_nonpos_of_nonpos (neg_nonpos.mpr (hπ i).le) (ho i j hij)
  2. The weights w are balanced: for every vertex i, the row sum equals the column sum: ∑_j w_{ij} = ∑_j w_{ji} = 0.

    The row sum is -π_i ∑_j L_{ij} = -π_i · 0 = 0 using the zero row-sum property of L. The column sum is -∑_j π_j L_{ji} = -0 = 0 using the left null vector property π L = 0. Thus both sums are zero and therefore equal.

    lines 14–21

    uses Finset.mul_sum, mul_zero, neg_zero, neg_mul, Finset.sum_neg_distrib

      have hb : ∀ i, ∑ j, w i j = ∑ j, w j i := by
        intro i
        change (∑ j, -π i * L i j) = ∑ j, -π j * L j i
        calc
          (∑ j, -π i * L i j) = -π i * ∑ j, L i j := (Finset.mul_sum _ _ _).symm
          _ = 0 := by rw [hr i, mul_zero]
          _ = -(∑ j, π j * L j i) := by rw [hs i, neg_zero]
          _ = ∑ j, -π j * L j i := by simp only [neg_mul, Finset.sum_neg_distrib]
  3. The total weighted sector cost over all pairs is nonnegative: 0 ≤ ∑_{i, j} w_{ij} c(v_i, v_j).

    By four_vertex_balanced_cost_nonneg, any balanced nonnegative off-diagonal weight matrix on 4 vertices paired with a cost function c satisfying c(u, u) = 0 and nonnegativity along all 4-cycles produces a nonnegative total cost ∑_{i,j} w_{ij} c(v_i, v_j) ≥ 0.

    lines 22–24

    uses four_vertex_balanced_cost_nonneg, complex_laplacian_sector_cost_self, complex_cycle_four_laplacian_sector_cost_nonneg

      have hnn := four_vertex_balanced_cost_nonneg w (fun i j => complex_laplacian_sector_cost (v i) (v j)) hw hb
        (fun i => complex_laplacian_sector_cost_self (v i))
        (fun i j k l => complex_cycle_four_laplacian_sector_cost_nonneg (v i) (v j) (v k) (v l))
  4. For each vertex i, the row sum of weighted costs equals (Re(z) + Im(z)) * π_i * (|v_i|^2). automation

    Taking real and imaginary parts of the eigenvalue equation (L v)_i = z v_i yields formulas for ∑_j L_{ij} Re(v_j) and ∑_j L_{ij} Im(v_j). Expanding the sums over Fin 4 and substituting the definition of w and the sector cost c, a linear combination of the row sum ∑_j L_{ij} = 0 and these real and imaginary eigenvalue identities algebraically verifies that the row cost reduces to (Re(z) + Im(z)) * π_i * (Re(v_i)^2 + Im(v_i)^2).

    lines 25–39

    uses congrArg, congrFun, Complex.mul_re, Complex.mul_im, Fin.sum_univ_succ

      have hrow : ∀ i, (∑ j, w i j * complex_laplacian_sector_cost (v i) (v j)) =
          (z.re + z.im) * (π i * ((v i).re ^ 2 + (v i).im ^ 2)) := by
        intro i
        have hre : (∑ j, L i j * (v j).re) = z.re * (v i).re - z.im * (v i).im := by
          simpa [Matrix.mulVec, dotProduct, Complex.mul_re] using
            congrArg Complex.re (congrFun hv i)
        have him : (∑ j, L i j * (v j).im) = z.re * (v i).im + z.im * (v i).re := by
          simpa [Matrix.mulVec, dotProduct, Complex.mul_im] using
            congrArg Complex.im (congrFun hv i)
        have hr0 := hr i
        simp [Fin.sum_univ_succ] at hre him hr0 ⊢
        dsimp [w, complex_laplacian_sector_cost] at hre him hr0 ⊢
        linear_combination -π i * ((v i).re ^ 2 + (v i).im ^ 2) * hr0 +
          π i * ((v i).re - (v i).im) * hre +
          π i * ((v i).re + (v i).im) * him
  5. The total cost inequality simplifies to 0 ≤ (Re(z) + Im(z)) * ∑_i π_i * (Re(v_i)^2 + Im(v_i)^2).

    Substituting the row-sum identity into the total cost inequality and factoring out the scalar (Re(z) + Im(z)) from the sum over i gives the result.

    line 40

    uses Finset.mul_sum

      simp_rw [hrow, ← Finset.mul_sum] at hnn
  6. For every vertex i, the weighted squared norm π_i * (Re(v_i)^2 + Im(v_i)^2) is nonnegative.

    This follows directly because π_i > 0 and squares of real numbers are always nonnegative, so their sum and product are nonnegative.

    lines 41–43

    uses mul_nonneg, add_nonneg, sq_nonneg

      have hn : ∀ i, 0 ≤ π i * ((v i).re ^ 2 + (v i).im ^ 2) := by
        intro i
        exact mul_nonneg (hπ i).le (add_nonneg (sq_nonneg _) (sq_nonneg _))
  7. There is at least one vertex i where Re(v_i)^2 + Im(v_i)^2 > 0.

    Since the eigenvector v is nonzero, there exists an index i such that v_i ≠ 0. If Re(v_i)^2 + Im(v_i)^2 ≤ 0, then both Re(v_i) and Im(v_i) must be zero, forcing v_i = 0, a contradiction.

    lines 44–52

    uses funext, sq_nonneg, Complex.ext

      obtain ⟨i, hi⟩ : ∃ i, v i ≠ 0 := by
        by_contra h
        push_neg at h
        exact hv0 (funext h)
      have hn_i : 0 < (v i).re ^ 2 + (v i).im ^ 2 := by
        by_contra hh
        have hx : (v i).re = 0 := by nlinarith [sq_nonneg (v i).im]
        have hy : (v i).im = 0 := by nlinarith [sq_nonneg (v i).re]
        exact hi (Complex.ext hx hy)
  8. The sum ∑_i π_i * (Re(v_i)^2 + Im(v_i)^2) is strictly positive.

    At vertex i, the term π_i * (Re(v_i)^2 + Im(v_i)^2) is the product of two strictly positive reals and hence strictly positive. Since every other term in the sum is nonnegative, the sum is at least this positive term, hence strictly positive.

    lines 53–55

    uses lt_of_lt_of_le, mul_pos, Finset.single_le_sum, Finset.mem_univ

      have hpos : 0 < ∑ i, π i * ((v i).re ^ 2 + (v i).im ^ 2) := by
        exact lt_of_lt_of_le (mul_pos (hπ i) hn_i)
          (Finset.single_le_sum (fun j _ => hn j) (Finset.mem_univ i))
  9. 0 ≤ Re(z) + Im(z). automation

    We have 0 ≤ (Re(z) + Im(z)) * S with S = ∑_i π_i * |v_i|^2 > 0. Dividing both sides by the positive quantity S (via nonlinear arithmetic) yields 0 ≤ Re(z) + Im(z).

    line 56

      nlinarith only [hnn, hpos]
add_nonneg
The sum of two nonnegative elements is nonnegative: 0 ≤ a and 0 ≤ b imply 0 ≤ a + b.
Complex.ext
Two complex numbers with equal real parts and equal imaginary parts are equal.
Complex.mul_im
The imaginary part of a product of complex numbers: Im(z * w) = Re(z) * Im(w) + Im(z) * Re(w).
Complex.mul_re
The real part of a product of complex numbers: Re(z * w) = Re(z) * Re(w) - Im(z) * Im(w).
complex_cycle_four_laplacian_sector_cost_nonneg
The sum of sector costs along any directed 4-cycle of complex numbers is nonnegative.
complex_laplacian_sector_cost_self
The sector cost between any complex number and itself is zero.
congrArg
Congruence for arguments: if a = b, then f(a) = f(b).
congrFun
Congruence for functions: if f = g, then f(a) = g(a).
Finset.mem_univ
Every element of a finite type belongs to its universal finset.
Finset.mul_sum
Multiplication distributes over a finite sum: a * ∑ x, f(x) = ∑ x, a * f(x).
Finset.single_le_sum
A single nonnegative term in a finite sum is bounded by the sum of all terms.
Finset.sum_neg_distrib
The sum of negated terms equals the negation of the sum: ∑ x, -f(x) = -∑ x, f(x).
Fin.sum_univ_succ
Splits a sum over Fin (n + 1) into the first term at index 0 and the sum of remaining terms over successors.
four_vertex_balanced_cost_nonneg
For any balanced, nonnegative off-diagonal edge weights on 4 vertices and a cost function that is zero on self-loops and nonnegative on 4-cycles, the total weighted cost is nonnegative.
funext
Two functions that agree on all arguments are equal (function extensionality).
lt_of_lt_of_le
Strict inequality combined with non-strict inequality is transitive: a < b and b ≤ c imply a < c.
mul_nonneg
The product of two nonnegative elements is nonnegative: 0 ≤ a and 0 ≤ b imply 0 ≤ a * b.
mul_nonneg_of_nonpos_of_nonpos
The product of two nonpositive elements in an ordered semiring is nonnegative: a ≤ 0 and b ≤ 0 imply 0 ≤ a * b.
mul_pos
The product of two strictly positive elements is strictly positive: 0 < a and 0 < b imply 0 < a * b.
mul_zero
Any element multiplied by zero is zero: a * 0 = 0.
neg_mul
Negation commutes with multiplication: (-a) * b = -(a * b).
neg_nonpos.mpr
If an element is nonnegative, its negation is nonpositive: 0 ≤ a implies -a ≤ 0.
neg_zero
The negation of zero is zero: -0 = 0.
sq_nonneg
The square of any real number is nonnegative: 0 ≤ a ^ 2.

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 laplacian_order_four_stationary_eigenvalue_one_side    (L : Matrix (Fin 4) (Fin 4) ℝ) (π : Fin 4 → ℝ)    (hπ : ∀ i, 0 < π i)    (hr : ∀ i, ∑ j, L i j = 0)    (ho : ∀ i j, i ≠ j → L i j ≤ 0)    (hs : ∀ j, ∑ i, π i * L i j = 0)    (v : Fin 4 → ℂ) (hv0 : v ≠ 0) (z : ℂ)    (hv : (L.map (algebraMap ℝ ℂ)).mulVec v = z • v) :    0 ≤ z.re + z.im := by  let w : Fin 4 → Fin 4 → ℝ := fun i j => -π i * L i j  have hw : ∀ i j, i ≠ j → 0 ≤ w i j := by    intro i j hij    exact mul_nonneg_of_nonpos_of_nonpos (neg_nonpos.mpr (hπ i).le) (ho i j hij)  have hb : ∀ i, ∑ j, w i j = ∑ j, w j i := by    intro i    change (∑ j, -π i * L i j) = ∑ j, -π j * L j i    calc      (∑ j, -π i * L i j) = -π i * ∑ j, L i j := (Finset.mul_sum _ _ _).symm      _ = 0 := by rw [hr i, mul_zero]      _ = -(∑ j, π j * L j i) := by rw [hs i, neg_zero]      _ = ∑ j, -π j * L j i := by simp only [neg_mul, Finset.sum_neg_distrib]  have hnn := four_vertex_balanced_cost_nonneg w (fun i j => complex_laplacian_sector_cost (v i) (v j)) hw hb    (fun i => complex_laplacian_sector_cost_self (v i))    (fun i j k l => complex_cycle_four_laplacian_sector_cost_nonneg (v i) (v j) (v k) (v l))  have hrow : ∀ i, (∑ j, w i j * complex_laplacian_sector_cost (v i) (v j)) =      (z.re + z.im) * (π i * ((v i).re ^ 2 + (v i).im ^ 2)) := by    intro i    have hre : (∑ j, L i j * (v j).re) = z.re * (v i).re - z.im * (v i).im := by      simpa [Matrix.mulVec, dotProduct, Complex.mul_re] using        congrArg Complex.re (congrFun hv i)    have him : (∑ j, L i j * (v j).im) = z.re * (v i).im + z.im * (v i).re := by      simpa [Matrix.mulVec, dotProduct, Complex.mul_im] using        congrArg Complex.im (congrFun hv i)    have hr0 := hr i    simp [Fin.sum_univ_succ] at hre him hr0 ⊢    dsimp [w, complex_laplacian_sector_cost] at hre him hr0 ⊢    linear_combination -π i * ((v i).re ^ 2 + (v i).im ^ 2) * hr0 +      π i * ((v i).re - (v i).im) * hre +      π i * ((v i).re + (v i).im) * him  simp_rw [hrow, ← Finset.mul_sum] at hnn  have hn : ∀ i, 0 ≤ π i * ((v i).re ^ 2 + (v i).im ^ 2) := by    intro i    exact mul_nonneg (hπ i).le (add_nonneg (sq_nonneg _) (sq_nonneg _))  obtain ⟨i, hi⟩ : ∃ i, v i ≠ 0 := by    by_contra h    push_neg at h    exact hv0 (funext h)  have hn_i : 0 < (v i).re ^ 2 + (v i).im ^ 2 := by    by_contra hh    have hx : (v i).re = 0 := by nlinarith [sq_nonneg (v i).im]    have hy : (v i).im = 0 := by nlinarith [sq_nonneg (v i).re]    exact hi (Complex.ext hx hy)  have hpos : 0 < ∑ i, π i * ((v i).re ^ 2 + (v i).im ^ 2) := by    exact lt_of_lt_of_le (mul_pos (hπ i) hn_i)      (Finset.single_le_sum (fun j _ => hn j) (Finset.mem_univ i))  nlinarith only [hnn, hpos]
See it in the graphDiscuss this resultChallenge it