AFTD Auto-Formalizing Theoretical Domains

standardized_laplacian_order_four_perturbation_stationary

theoremverified

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
Used by 1

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.

  1. 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.

    lines 6–7

      let M : Matrix (Fin 4) (Fin 4) ℝ :=
        fun i j => (if i = j then 1 else 0) - L i j + δ / 4
  2. 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.

    lines 8–17

    uses if_pos, standardized_laplacian_order_four_diagonal_lt_one, if_neg

      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]
  3. 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 + δ.

    lines 18–21

    uses Finset.sum_add_distrib, Finset.sum_sub_distrib

      have hrow : ∀ i, ∑ j, M i j = 1 + δ := by
        intro i
        simp [M, Finset.sum_add_distrib, Finset.sum_sub_distrib, hL.1]
        <;> ring
  4. 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.

    lines 22–23

    uses positive_matrix_order_four_left_stationary

      obtain ⟨π, hπ, hsum, hstat⟩ := positive_matrix_order_four_left_stationary M hM (1 + δ) hrow
      refine ⟨π, hπ, ?_⟩
  5. 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.

    lines 24–30

    uses mul_add, mul_sub, mul_ite, Finset.sum_add_distrib, Finset.sum_sub_distrib, Finset.sum_mul

      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
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

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
See it in the graphDiscuss this resultChallenge it