AFTD Auto-Formalizing Theoretical Domains

positive_matrix_order_four_left_stationary

theoremverified

A strictly positive order-four real matrix with constant row sum has a strictly positive normalized left eigenvector with that eigenvalue.

Statement

theorem positive_matrix_order_four_left_stationary
    (M : Matrix (Fin 4) (Fin 4) ℝ) (hM : ∀ i j, 0 < M i j)
    (r : ℝ) (hr : ∀ i, ∑ j, M i j = r) :
    ∃ π : Fin 4 → ℝ, (∀ i, 0 < π i) ∧ (∑ i, π i) = 1 ∧
      ∀ j, ∑ i, π i * M i j = r * π j
Source
Sector-bound formalization for IN-166; arXiv:math/0508176, Theorem 5.
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • EconCSLib.LinearAlgebra.perron_frobeniusPerron-Frobenius for positive matrices [MFoGT, Section 2.8, Exercise 1(2)]. A square matrix with strictly positive entries has a…
  • wsumWeighted sum of f with weights from a simplex element x. Thin abbrev over Mathlib's finite dot product ⬝ᵥ: definitionally equal,…
Used by 2

The proof, explained

The proof applies the Perron-Frobenius theorem for strictly positive matrices to obtain a positive eigenvalue λ and a normalized strictly positive left eigenvector x. Summing the left eigenvector equation over all columns and interchanging the order of summation simplifies the double sum to the row sum r on one side and to λ on the other, proving λ = r. Consequently, x is the required strictly positive normalized left eigenvector with eigenvalue r.

  1. The Perron-Frobenius theorem gives a positive eigenvalue λ > 0 and a strictly positive normalized left eigenvector x on the standard simplex satisfying ∑ i, x i * M i j = λ * x j for all j.

    Applying the Perron-Frobenius theorem for strictly positive matrices (EconCSLib.LinearAlgebra.perron_frobenius) produces an eigenvalue λ > 0 and left and right eigenvectors x, y lying on the standard simplex. Since x is on the standard simplex, its components sum to 1 (hsum). Unfolding the weighted sum in the left eigenvector condition yields the column-wise identity ∑ i, x i * M i j = λ * x j for every j (hxM').

    lines 6–9

    uses EconCSLib.LinearAlgebra.perron_frobenius

      obtain ⟨x, y, lam, hlam, hx, hy, hxM, hMy⟩ :=
        EconCSLib.LinearAlgebra.perron_frobenius M hM
      have hsum : (∑ i, x.val i) = 1 := x.property.2
      have hxM' : ∀ j, ∑ i, x.val i * M i j = lam * x.val j := hxM
  2. The Perron eigenvalue λ equals the constant row sum r.

    Summing the left eigenvector equation ∑ i, x i * M i j = λ * x j over all columns j yields ∑ j, ∑ i, x i * M i j = ∑ j, λ * x j, using function extensionality (funext) and congruence (congrArg). On the left-hand side, interchanging the two sums (Finset.sum_comm) produces ∑ i, x i * (∑ j, M i j). Since every row sum ∑ j, M i j is r, factoring out r (Finset.mul_sum, Finset.sum_mul) and using the normalization ∑ i, x i = 1 (one_mul) simplifies the left-hand side to r. On the right-hand side, factoring out λ (Finset.mul_sum) gives λ * (∑ j, x j) = λ * 1 = λ (mul_one). Equating these two evaluations gives r = λ, hence λ = r.

    lines 10–20

    uses congrArg, funext, Finset.sum_comm, Finset.mul_sum, Finset.sum_mul, one_mul, mul_one

      have hlamr : lam = r := by
        have he := congrArg (fun f : Fin 4 → ℝ => ∑ j, f j) (funext hxM')
        have hleft : (∑ j, ∑ i, x.val i * M i j) = r := by
          rw [Finset.sum_comm]
          simp_rw [← Finset.mul_sum, hr]
          rw [← Finset.sum_mul, hsum, one_mul]
        have hright : (∑ j, lam * x.val j) = lam := by
          rw [← Finset.mul_sum, hsum, mul_one]
        change (∑ j, ∑ i, x.val i * M i j) = ∑ j, lam * x.val j at he
        rw [hleft, hright] at he
        exact he.symm
  3. The normalized vector x is the desired strictly positive stationary distribution with eigenvalue r.

    We supply x as the witness π. Its components are strictly positive and sum to 1. Substituting λ = r into the eigenvector relation ∑ i, x i * M i j = λ * x j gives ∑ i, x i * M i j = r * x j for every j, satisfying all conditions of the theorem.

    line 21

      exact ⟨x.val, hx, hsum, fun j => by simpa only [hlamr] using hxM' j⟩
EconCSLib.LinearAlgebra.perron_frobenius
For any strictly positive square real matrix, there exist a strictly positive eigenvalue λ and strictly positive normalized left and right eigenvectors in the standard simplex associated with λ.
congrArg
Applying a function to both sides of an equality preserves the equality.
funext
Two functions that agree on all arguments are equal (function extensionality).
Finset.sum_comm
The order of summation in a finite double sum can be interchanged: ∑ x, ∑ y, f x y = ∑ y, ∑ x, f x y.
Finset.mul_sum
Multiplication distributes over finite summation from the left: a * ∑ i, f i = ∑ i, a * f i.
Finset.sum_mul
Multiplication distributes over finite summation from the right: (∑ i, f i) * a = ∑ i, f i * a.
one_mul
Multiplying any element by 1 on the left leaves it unchanged: 1 * a = a.
mul_one
Multiplying any element by 1 on the right leaves it unchanged: a * 1 = 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 positive_matrix_order_four_left_stationary    (M : Matrix (Fin 4) (Fin 4) ℝ) (hM : ∀ i j, 0 < M i j)    (r : ℝ) (hr : ∀ i, ∑ j, M i j = r) :    ∃ π : Fin 4 → ℝ, (∀ i, 0 < π i) ∧ (∑ i, π i) = 1 ∧      ∀ j, ∑ i, π i * M i j = r * π j := by  obtain ⟨x, y, lam, hlam, hx, hy, hxM, hMy⟩ :=    EconCSLib.LinearAlgebra.perron_frobenius M hM  have hsum : (∑ i, x.val i) = 1 := x.property.2  have hxM' : ∀ j, ∑ i, x.val i * M i j = lam * x.val j := hxM  have hlamr : lam = r := by    have he := congrArg (fun f : Fin 4 → ℝ => ∑ j, f j) (funext hxM')    have hleft : (∑ j, ∑ i, x.val i * M i j) = r := by      rw [Finset.sum_comm]      simp_rw [← Finset.mul_sum, hr]      rw [← Finset.sum_mul, hsum, one_mul]    have hright : (∑ j, lam * x.val j) = lam := by      rw [← Finset.mul_sum, hsum, mul_one]    change (∑ j, ∑ i, x.val i * M i j) = ∑ j, lam * x.val j at he    rw [hleft, hright] at he    exact he.symm  exact ⟨x.val, hx, hsum, fun j => by simpa only [hlamr] using hxM' j⟩
See it in the graphDiscuss this resultChallenge it