Proof of Theorem 2.6, p. 9 — ‖F^{|C*|+1}‖_∞ ≤ α₃^{|C*|+1} − (α₃ − α₁)α₂^{|C*|} < 1
ProvedSubSuperStoch.SuperSpec.normInf_power_boundinfinity-normnonnegative-matrixp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1super-stochastic-matrix
Under the hypotheses of Theorem 2.6 — an super-stochastic matrix, and non-empty, a non-zero element chain from some for each , the largest number of elements of these chains, as in Theorem 2.6, and condition (2.5) —
This is the fourth step of the proof of Theorem 2.6: the row bounds for and together bound every row sum of the nonnegative matrix , hence its infinity norm.
Formalization Note The hypotheses are exactly those of the goal theorem theorem_2_6, with the chosen chains given by a length function and its greatest value over . The infinity norm is the maximal absolute row sum over the index type Fin n.
Preamble
import Mathlib import Definitions.Def_SubSuperStoch_SuperSpec_Setting
Formal statement
namespace SubSuperStoch.SuperSpec
theorem normInf_power_bound {n : ℕ} (F : Matrix (Fin n) (Fin n) ℝ) (hF : IsSuperStochastic F)
(hR₁ : ∃ s, SubSuperStoch.SubSpec.rowSum F s < 1) (hR₂ : ∃ s, 1 ≤ SubSuperStoch.SubSpec.rowSum F s)
(len : Fin n → ℕ)
(hchain : ∀ k, 1 ≤ SubSuperStoch.SubSpec.rowSum F k → ∃ i, SubSuperStoch.SubSpec.rowSum F i < 1 ∧
∃ c : ℕ → Fin n, c 0 = i ∧ c (len k) = k ∧ 1 ≤ len k ∧ SubSuperStoch.SubSpec.IsChain F c (len k))
(α₁ : ℝ) (hα₁ : IsGreatest {x | ∃ s, SubSuperStoch.SubSpec.rowSum F s < 1 ∧ x = SubSuperStoch.SubSpec.rowSum F s} α₁)
(α₂ : ℝ) (hα₂ : IsLeast {x | ∃ i j, 0 < F i j ∧ x = F i j} α₂)
(α₃ : ℝ) (hα₃ : IsGreatest {x | ∃ s, 1 ≤ SubSuperStoch.SubSpec.rowSum F s ∧ x = SubSuperStoch.SubSpec.rowSum F s} α₃)
(C : ℕ) (hC : IsGreatest {m | ∃ k, 1 ≤ SubSuperStoch.SubSpec.rowSum F k ∧ m = len k} C)
(h25 : (α₃ ^ (C + 1) - (α₃ - α₁) * α₂ ^ C) ^ (1 / (C : ℝ)) < 1) :
SubSuperStoch.SubSpec.normInf (F ^ (C + 1)) ≤ α₃ ^ (C + 1) - (α₃ - α₁) * α₂ ^ C ∧
α₃ ^ (C + 1) - (α₃ - α₁) * α₂ ^ C < 1 := by sorry
end SubSuperStoch.SuperSpec
Source
Shi, Zheng, Shao, Cheng, arXiv:2004.01867v2, p. 9, proof of Theorem 2.6, fourth display
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.