standardized_laplacian_order_four_perturbation_stationary
Every positive centered scalar shift of an order-four standardized Laplacian has a strictly positive left null vector.
Statement
theorem standardized_laplacian_order_four_perturbation_stationary
(L : Matrix (Fin 4) (Fin 4) ℝ) (hL : is_standardized_laplacian 4 L)
(δ : ℝ) (hδ : 0 < δ) :
∃ π : Fin 4 → ℝ, (∀ i, 0 < π i) ∧
∀ j, ∑ i, π i * matrix_order_four_centered_shift L δ i j = 0- Source
- Sector-bound formalization for IN-166; arXiv:math/0508176, Theorem 5.
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- positive_matrix_order_four_left_stationaryA strictly positive order-four real matrix with constant row sum has a strictly positive normalized left eigenvector with that eigenvalue.
- standardized_laplacian_order_four_diagonal_lt_oneEvery diagonal entry of an order-four standardized Laplacian is less than one.
- matrix_order_four_centered_shiftAdd a scalar multiple of the identity minus the averaging matrix to an order-four real matrix.
- 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].
- Used by 1
- standardized_laplacian_order_four_im_le_reFor any standardized Laplacian matrix L of order 4, the imaginary part and real part of every complex eigenvalue z of L satisfy |Im(z)| ≤…
The proof, explained
The proof constructs an auxiliary positive matrix M = I - L + (δ / 4) J, whose row sums all equal 1 + δ. By the Perron-Frobenius theorem for order-4 matrices, M possesses a strictly positive left eigenvector π with eigenvalue 1 + δ normalized to sum to 1. Algebraic expansion then reveals that the eigenvector equation πᵀ M = (1 + δ) πᵀ is equivalent to π being a left null vector of the centered scalar shift of L.
Define an auxiliary matrix M by M_{i, j} = I_{i, j} - L_{i, j} + δ / 4.
We introduce the matrix M = I - L + (δ / 4) J, where I is the 4×4 identity matrix and every entry of (δ / 4) J is δ / 4.
let M : Matrix (Fin 4) (Fin 4) ℝ := fun i j => (if i = j then 1 else 0) - L i j + δ / 4
Every entry of M is strictly positive (M_{i, j} > 0 for all i, j).
We split into cases based on whether the indices are on the diagonal: - If i = j, M_{i, i} = 1 - L_{i, i} + δ / 4. By `standardized_laplacian_order_four_diagonal_lt_one`, L_{i, i} < 1, so 1 - L_{i, i} > 0. Since δ > 0, the sum is strictly positive. - If i ≠ j, M_{i, j} = -L_{i, j} + δ / 4. By the definition of a standardized Laplacian, off-diagonal entries satisfy L_{i, j} ≤ 0, so -L_{i, j} ≥ 0. Adding δ / 4 > 0 makes the entry strictly positive.
uses
if_pos,standardized_laplacian_order_four_diagonal_lt_one,if_neghave hM : ∀ i j, 0 < M i j := by intro i j by_cases hij : i = j · subst j dsimp only [M] rw [if_pos rfl] linarith [standardized_laplacian_order_four_diagonal_lt_one L hL i] · dsimp only [M] rw [if_neg hij] linarith [(hL.2 i j hij).2]
Every row of M sums to 1 + δ.
For any row i, summing M_{i, j} over all columns j yields ∑_j I_{i, j} - ∑_j L_{i, j} + 4 * (δ / 4). The identity matrix row sum is 1, the row sum of the standardized Laplacian L is 0 by definition, and 4 * (δ / 4) = δ. Thus the row sum is 1 - 0 + δ = 1 + δ.
uses
Finset.sum_add_distrib,Finset.sum_sub_distribhave hrow : ∀ i, ∑ j, M i j = 1 + δ := by intro i simp [M, Finset.sum_add_distrib, Finset.sum_sub_distrib, hL.1] <;> ring
There exists a strictly positive probability vector π that is a left eigenvector of M with eigenvalue 1 + δ.
Because M has strictly positive entries and constant row sum 1 + δ, the Perron-Frobenius theorem for order-4 matrices (`positive_matrix_order_four_left_stationary`) provides a strictly positive probability vector π (with ∑_i π_i = 1) such that ∑_i π_i M_{i, j} = (1 + δ) π_j for every column j. We select π as the candidate vector.
uses
positive_matrix_order_four_left_stationaryobtain ⟨π, hπ, hsum, hstat⟩ := positive_matrix_order_four_left_stationary M hM (1 + δ) hrow refine ⟨π, hπ, ?_⟩
The vector π is a left null vector of the centered shift matrix of L.
Fix a column j. Expanding the stationarity relation for M gives π_j - ∑_i π_i L_{i, j} + δ / 4 = (1 + δ) π_j, which simplifies to ∑_i π_i L_{i, j} + δ π_j - δ / 4 = 0. On the other hand, multiplying π by the j-th column of the centered shift matrix L + δ I - δ / 4 also expands to ∑_i π_i L_{i, j} + δ π_j - δ / 4 (using ∑_i π_i = 1). Since this expression equals 0 by stationarity, π is indeed a left null vector.
uses
mul_add,mul_sub,mul_ite,Finset.sum_add_distrib,Finset.sum_sub_distrib,Finset.sum_mulintro j have hsj := hstat j simp [M, mul_add, mul_sub, mul_ite, Finset.sum_add_distrib, Finset.sum_sub_distrib, ← Finset.sum_mul, hsum] at hsj simp [matrix_order_four_centered_shift, mul_add, mul_sub, mul_ite, Finset.sum_add_distrib, Finset.sum_sub_distrib, ← Finset.sum_mul, hsum] linarith
if_pos- If a condition holds, the if-then-else expression evaluates to the \"then\" branch.
if_neg- If a condition does not hold, the if-then-else expression evaluates to the \"else\" branch.
standardized_laplacian_order_four_diagonal_lt_one- Every diagonal entry of an order-four standardized Laplacian is strictly less than 1.
Finset.sum_add_distrib- The sum of a sum over a finite set equals the sum of the two individual sums.
Finset.sum_sub_distrib- The sum of a difference over a finite set equals the difference of the two individual sums.
positive_matrix_order_four_left_stationary- Every strictly positive 4×4 real matrix with constant row sum r has a strictly positive probability vector π satisfying πᵀ M = r πᵀ.
mul_add- Multiplication distributes over addition on the left: a * (b + c) = a * b + a * c.
mul_sub- Multiplication distributes over subtraction on the left: a * (b - c) = a * b - a * c.
mul_ite- Multiplication distributes over an if-then-else expression: a * (if P then b else c) = if P then a * b else a * c.
Finset.sum_mul- Multiplication distributes over a finite sum on the right: (∑ i, f i) * a = ∑ i, (f i * 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_perturbation_stationary (L : Matrix (Fin 4) (Fin 4) ℝ) (hL : is_standardized_laplacian 4 L) (δ : ℝ) (hδ : 0 < δ) : ∃ π : Fin 4 → ℝ, (∀ i, 0 < π i) ∧ ∀ j, ∑ i, π i * matrix_order_four_centered_shift L δ i j = 0 := by let M : Matrix (Fin 4) (Fin 4) ℝ := fun i j => (if i = j then 1 else 0) - L i j + δ / 4 have hM : ∀ i j, 0 < M i j := by intro i j by_cases hij : i = j · subst j dsimp only [M] rw [if_pos rfl] linarith [standardized_laplacian_order_four_diagonal_lt_one L hL i] · dsimp only [M] rw [if_neg hij] linarith [(hL.2 i j hij).2] have hrow : ∀ i, ∑ j, M i j = 1 + δ := by intro i simp [M, Finset.sum_add_distrib, Finset.sum_sub_distrib, hL.1] <;> ring obtain ⟨π, hπ, hsum, hstat⟩ := positive_matrix_order_four_left_stationary M hM (1 + δ) hrow refine ⟨π, hπ, ?_⟩ intro j have hsj := hstat j simp [M, mul_add, mul_sub, mul_ite, Finset.sum_add_distrib, Finset.sum_sub_distrib, ← Finset.sum_mul, hsum] at hsj simp [matrix_order_four_centered_shift, mul_add, mul_sub, mul_ite, Finset.sum_add_distrib, Finset.sum_sub_distrib, ← Finset.sum_mul, hsum] linarith