positive_matrix_order_four_left_stationary
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
fwith weights from a simplex elementx. Thinabbrevover Mathlib's finite dot product⬝ᵥ: definitionally equal,…
- Used by 2
- binary_rank_zeroThe all-zero binary matrix of dimensions n × m with entries in Fin 2 has binary rank 0.
- standardized_laplacian_order_four_perturbation_stationaryEvery positive centered scalar shift of an order-four standardized Laplacian has a strictly positive left null vector.
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.
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').
uses
EconCSLib.LinearAlgebra.perron_frobeniusobtain ⟨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
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.
uses
congrArg,funext,Finset.sum_comm,Finset.mul_sum,Finset.sum_mul,one_mul,mul_onehave 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
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.
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
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 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⟩