LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck passjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

An irreducible row-substochastic matrix with a strict row has a weighted contraction

Statement

Let $n \geq 1$ and let $C = (c_{i j}) \in M_{n} (R)$ have nonnegative entries and row sums at most $1$ . Form the directed graph with vertices ${1, \dots, n}$ and an edge $i \to j$ exactly when $c_{i j} > 0$ ; assume this graph is strongly connected, with paths of length $0$ allowed. Assume one row $r$ has sum strictly less than $1$ . Then, with $1 = (1, \dots, 1)^{T}$ ,

$C^{n} 1 < 1$

coordinatewise, and the series $v = \sum_{k = 0}^{\infty} C^{k} 1$ converges coordinatewise to a vector satisfying $v > 0$ and $C v < v$ coordinatewise.

Facts & Assumptions

Given: A nonnegative $n \times n$ matrix $C$ with row sums at most $1$ , strongly connected directed support graph, and at least one strict row $r$ .

[A1]

$C 1 \leq 1$ and $d : = 1 - C 1 \geq 0$ coordinatewise, with $d_{r} > 0$ for a strict row $r$ .

[A2]

For every vertex $i$ , strong connectivity supplies a directed path from $i$ to $r$ ; a shortest path has length at most $n - 1$ .

Proof

1.1givenA1algebra

Put $d = 1 - C 1$ . Telescoping gives $1 - C^{n} 1 = \sum_{k = 0}^{n - 1} C^{k} d$ , since $(I - C) \sum_{k = 0}^{n - 1} C^{k} = I - C^{n}$ . Each summand is coordinatewise nonnegative by [A1].

2.1A1A2step 1.1algebra

For each $i$ , choose by [A2] a path of length $s_{i} \leq n - 1$ from $i$ to $r$ . The product of the positive edge weights along it is a positive term of $(C^{s_{i}})_{i r}$ ; for $s_{i} = 0$ this entry is $1$ . Hence $(C^{s_{i}} d)_{i} \geq (C^{s_{i}})_{i r} d_{r} > 0$ . Step 1.1 then gives $(C^{n} 1)_{i} < 1$ for every $i$ .

3.1A1step 2.1algebra

Let $q : = \max_{i} (C^{n} 1)_{i} < 1$ . Since $C^{s} 1 \leq 1$ for $0 \leq s < n$ , nonnegativity gives $C^{k n + s} 1 \leq q^{k} 1$ for all $k \geq 0$ and $0 \leq s < n$ . Therefore $\sum_{j = 0}^{\infty} C^{j} 1$ converges coordinatewise and its sum $v$ satisfies $v \geq 1 > 0$ .

4.1step 3.1algebra∎

Multiplying the convergent series by $C$ shifts its terms, so $C v = v - 1 < v$ coordinatewise.

Used by

Irreducibly weak row diagonal dominance with a strict row guarantees Jacobi and Gauss–Seidel convergence Theorem

Dependency tree · 0 levels

Nothing. This result depends on no other item in the library.

Sources

Yousef Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., §4.2.3 (standard reference, not scraped)