Lemma 1, p. 25 — a subinvariant vector with strict slack reachable from every node forces ρ(P) < 1
ProvedSaturatedNet.Uniqueness.lemma_1digraphnonnegative-matrixp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1spectral-radius
Let be a nonnegative square matrix and its digraph (link when ). Suppose that
- there is a nonnegative vector with (entrywise), and
- for every node there is a path in from to some node with .
Then
The lemma is the tool of the appendix proof of Proposition 3: a positive subinvariant vector that is strictly subinvariant somewhere downstream of every node certifies a spectral radius below one.
Formalization Note. The same serves both conditions. Paths may have length zero (the node itself may be the node ), as in the paper's proof, where is allowed.
Preamble
import Mathlib import Definitions.Def_SaturatedNet_Uniqueness_Model open Matrix
Formal statement
namespace SaturatedNet.Uniqueness
theorem lemma_1 {n : Type*} [Fintype n] [DecidableEq n]
(P : Matrix n n ℝ) (hP : ∀ i j, 0 ≤ P i j) (v : n → ℝ) (hv0 : 0 ≤ v) (hv : v ≠ 0)
(hPv : P *ᵥ v ≤ v) (hpath : ∀ i, ∃ j, Reaches P i j ∧ (P *ᵥ v) j < v j) :
specRad P < 1 := by sorry
end SaturatedNet.Uniqueness
Source
Massai, Como & Fagnani, Equilibria and Systemic Risk in Saturated Networks, arXiv:1912.04815v2, p. 25, Appendix, Lemma 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.