Proof of Theorem 2.2, p. 5 — ‖F^{|C*|+1}‖_∞ ≤ 1 − (1 − α₁)α₂^{|C*|} < 1
ProvedSubSuperStoch.SubSpec.normInf_power_boundinfinity-normmatrix-powernonnegative-matrixp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1sub-stochastic-matrix
Under the hypotheses of Theorem 2.2 — an sub-stochastic matrix with and non-empty, a non-zero element chain from some given for each , and as defined there — the infinite norm of the power satisfies
This collects the row bounds for and into one norm bound, which is then turned into the spectral bound (2.1).
Formalization Note normInf is the largest absolute row sum; since is nonnegative it equals the largest row sum. The chain data are passed exactly as in the goal theorem.
Preamble
import Mathlib import Definitions.Def_SubSuperStoch_SubSpec_Setting
Formal statement
namespace SubSuperStoch.SubSpec
theorem normInf_power_bound {n : ℕ} (F : Matrix (Fin n) (Fin n) ℝ) (hF : IsSubStochastic F)
(hS₁ : ∃ s, rowSum F s < 1) (hS₂ : ∃ s, rowSum F s = 1)
(len : Fin n → ℕ)
(hchain : ∀ k, rowSum F k = 1 → ∃ i, rowSum F i < 1 ∧
∃ c : ℕ → Fin n, c 0 = i ∧ c (len k) = k ∧ 1 ≤ len k ∧ IsChain F c (len k))
(α₁ : ℝ) (hα₁ : IsGreatest {x | ∃ s, rowSum F s < 1 ∧ x = rowSum F s} α₁)
(α₂ : ℝ) (hα₂ : IsLeast {x | ∃ i j, 0 < F i j ∧ x = F i j} α₂)
(C : ℕ) (hC : IsGreatest {m | ∃ k, rowSum F k = 1 ∧ m = len k} C) :
normInf (F ^ (C + 1)) ≤ 1 - (1 - α₁) * α₂ ^ C ∧ 1 - (1 - α₁) * α₂ ^ C < 1 := by sorry
end SubSuperStoch.SubSpec
Source
Shi, Zheng, Shao, Cheng, arXiv:2004.01867v2, p. 5, proof of Theorem 2.2 (display ‖F^{|C*|+1}‖_∞ ≤ 1 − (1 − α₁)α₂^{|C*|} < 1)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.