Theorem 2.6, p. 9 — chains into every row of sum ≥ 1 of a super-stochastic F and condition (2.5) give ρ(F) < 1

Let $F$ be an $n\times n$ super-stochastic matrix, and let

be non-empty. Suppose that for each $k\in\mathcal R_2$ there is a non-zero element chain

with $i\in\mathcal R_1$, $i_r\neq k,\dots,i_1\neq i_2,\ i\neq i_1$ (all listed entries non-zero), and let $|\mathcal C^*|$ be the largest number of elements among these chains. Put

If the inequality

holds, then

that is, every eigenvalue of $F$ has modulus less than one.

A super-stochastic matrix may have rows of sum larger than one and hence spectral radius larger than one in general; the theorem gives a checkable condition — chains feeding every row of sum at least one from a row of sum less than one, plus the scalar inequality (2.5) — under which $F$ is nevertheless Schur stable. The paper uses such bounds to analyse discrete-time positive and signed-network iterations whose update matrices are not sub-stochastic.

Formalization Note The chosen chains are given by a length function $\mathrm{len}$ on rows: for each $k\in\mathcal R_2$ there are $i\in\mathcal R_1$ and a chain from $i$ to $k$ of $\mathrm{len}(k)\ge1$ elements; $|\mathcal C^*|=C$ is the greatest value of $\mathrm{len}$ on $\mathcal R_2$ ("defined in Theorem 2.2" with $\mathcal S_1,\mathcal S_2$ read as $\mathcal R_1,\mathcal R_2$). The extrema $\alpha_1,\alpha_2,\alpha_3,C$ are values with hypotheses that they are the greatest/least elements of exactly the printed sets. The root in (2.5) is the real power $x^{1/C}$; the radicand is nonnegative under the hypotheses and $C\ge1$, so (2.5) is equivalent to $\alpha_3^{C+1}-(\alpha_3-\alpha_1)\alpha_2^{C}<1$. Eigenvalues are the spectrum of $F$ as a complex matrix. The proof on the page ends with $\rho(F)\le\sqrt[|\mathcal C^*|]{\cdots}$; the theorem itself claims only $\rho(F)<1$, which is what is stated here.