laplacian_order_four_stationary_eigenvalue_one_side
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
- complex_laplacian_sector_costThe sum of the real and imaginary parts of the complex Laplacian edge form.
- complex_laplacian_sector_cost_selfThe Laplacian sector cost of a loop is zero.
- complex_cycle_four_laplacian_sector_cost_nonnegThe sum of the Laplacian sector costs around any closed four-step complex cycle is nonnegative, including repeated vertices.
- four_vertex_balanced_cost_nonnegOn four vertices, a balanced edge weighting, nonnegative away from the diagonal, assigns nonnegative total cost whenever every closed…
- Used by 1
- laplacian_order_four_stationary_eigenvalue_sectorFor a real order-four matrix with zero row sums, nonpositive off-diagonal entries, and a strictly positive left null vector, every complex…
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.
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.
uses
mul_nonneg_of_nonpos_of_nonpos,neg_nonpos.mprlet 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)
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.
uses
Finset.mul_sum,mul_zero,neg_zero,neg_mul,Finset.sum_neg_distribhave 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]
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.
uses
four_vertex_balanced_cost_nonneg,complex_laplacian_sector_cost_self,complex_cycle_four_laplacian_sector_cost_nonneghave 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))
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).
uses
congrArg,congrFun,Complex.mul_re,Complex.mul_im,Fin.sum_univ_succhave 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
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.
uses
Finset.mul_sumsimp_rw [hrow, ← Finset.mul_sum] at hnnFor 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.
uses
mul_nonneg,add_nonneg,sq_nonneghave 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 _))
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.
uses
funext,sq_nonneg,Complex.extobtain ⟨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)
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.
uses
lt_of_lt_of_le,mul_pos,Finset.single_le_sum,Finset.mem_univhave 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))
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).
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.
- The nonnegativity of the total cost (line 22) relies on `four_vertex_balanced_cost_nonneg`, a cycle decomposition theorem for balanced 4-vertex graphs proved elsewhere in the library.
- The algebraic identity on lines 35–39 relating the row cost to the eigenvalue equation and row-sum zero condition is verified automatically using `linear_combination`.
- The final deduction on line 56 is closed by nonlinear arithmetic automation (`nlinarith`).
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 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]