A fast and stable test to check if a weakly diagonally dominant matrix is a nonsingular M-matrix

By Parsiad Azimzadeh

Abstract

We present a test for determining if a substochastic matrix is convergent. By establishing a duality between weakly chained diagonally dominant (w.c.d.d.) L-matrices and convergent substochastic matrices, we show that this test can be trivially extended to determine whether a weakly diagonally dominant (w.d.d.) matrix is a nonsingular M-matrix. The test’s runtime is linear in the order of the input matrix if it is sparse, and quadratic if it is dense. This is a partial strengthening of the cubic test in [J. M. Peña., A stable test to check if a matrix is a nonsingular M-matrix, Math. Comp., 247, 1385–1392, 2004]. As a by-product of our analysis, we prove that a nonsingular w.d.d. M-matrix is a w.c.d.d. L-matrix, a fact whose converse has been known since at least 1964.

1. Introduction

The substochastic matrices are real matrices with nonnegative entries and whose row-sums are at most one. We establish two results relating to this family:

(i): To each substochastic matrix $B$ we associate a possibly infinite index of contraction $\widehat{\operatorname {con}}B$ and show that for each nonnegative integer $k$, $B^{k}$ is a contraction in the infinity norm (i.e., $\Vert B^{k}\Vert _{\infty }<1$) if and only if $k>\widehat{\operatorname {con}}B$.
(ii): We show that the index of contraction of a sparse (resp., dense) square substochastic matrix is computable in time linear (resp., quadratic) in the order of the input matrix.

It follows immediately from (i) that a square substochastic matrix is convergent if and only if its index of contraction is finite.

By establishing a duality between weakly chained diagonally dominant (w.c.d.d.) L-matrices and convergent substochastic matrices, we use point (ii) to obtain a test to determine whether a weakly diagonally dominant (w.d.d.) matrix is a nonsingular M-matrix. Previous work in this regard is the test in Reference 15 to determine if an arbitrary matrix (not necessarily w.d.d.) is a nonsingular M-matrix, which has a cost asymptotically equivalent to Gaussian elimination (i.e., cubic in the order of the input matrix).

W.d.d. M-matrices arise naturally from discretizations of differential operators and appear in the Bellman equation for optimal decision making on a controlled Markov chain Reference 3. As such, these matrices have attracted a significant amount of attention from the scientific computing and numerical analysis communities.

W.c.d.d. matrices were first studied in a wonderful work by P. N. Shivakumar and K. H. Chew Reference 18 in which they were proven to be nonsingular (see also Reference 1 for a short proof). Various authors have recently studied the family of w.c.d.d. M-matrices, obtaining bounds on the infinity norm of their inverses (i.e., $\Vert A^{-1}\Vert _{\infty }$) Reference 5Reference 10Reference 14Reference 19Reference 23. While a w.c.d.d. matrix is w.d.d. by definition, the converse is not necessarily true in general (e.g., $\left( \begin{smallmatrix} +1&-1\\ -1&+1 \end{smallmatrix} \right)$ is w.d.d. but not w.c.d.d.).

It has long been known (possibly as early as 1964; see the work of J. H. Bramble and B. E. Hubbard Reference 4) that a w.c.d.d. L-matrix⁠Footnote¹ is a nonsingular w.d.d. M-matrix. We obtain a proof of the converse as a by-product of our analysis. In particular, we establish that⁠Footnote²

In Reference 4, the authors refer to w.c.d.d. L-matrices as matrices of positive type.

✖

Equation 1.1 remains true if we replace “L-matrix” by “Z-matrix with nonnegative diagonal entries”.

✖

$$\begin{align} A\text{ is a nonsingular w.d.d. M-matrix} & \iff A\text{ is a nonsingular w.d.d. L-matrix}\\ & \iff A\text{ is a w.c.d.d. L-matrix}. \cssId{texmlid1}{\tag{1.1}} \end{align}$$

Equation 1.1 is also useful in that it gives a graph-theoretic characterization of nonsingular w.d.d. M-matrices by means of w.c.d.d. matrices. This characterization is often easier to use than the usual characterizations involving, say, inverse-positivity or positive principal minors Reference 16.

We list a few other interesting recent results concerning w.c.d.d. matrices and M-matrices here: Reference 11Reference 12Reference 13Reference 20Reference 22Reference 24Reference 25Reference 26.

Section 2 introduces and establishes results on substochastic matrices, M-matrices, and w.c.d.d. matrices. Section 3 gives the procedure to compute the index of contraction. Section 4 presents numerical experiments testing the efficacy of the procedure on randomly sampled matrices.

2. Matrix families

2.1. Substochastic matrices

Definition 2.1.

A substochastic matrix is a real matrix $B\coloneq (b_{ij})$ with nonnegative entries (i.e., $b_{ij}\geq 0$) and row-sums at most one (i.e., $\sum _{j}b_{ij}\leq 1$). A stochastic (a.k.a. Markov) matrix is a substochastic matrix whose row-sums are exactly one.

Note that in our definition above, we do not require $B$ to be square.

Definition 2.2.

Let $A\coloneq (a_{ij})$ be an $m\times n$ complex matrix.

(i)

The digraph of $A$, denoted $\operatorname {graph}A$, is defined as follows:

(a): If $A$ is square, $\operatorname {graph}A$ is a tuple $(V,E)$ consisting of the vertex set $V\coloneq \{1,\ldots ,m\}$ and edge set $E\subset V\times V$ satisfying $(i,j)\in E$ if and only if $a_{ij}\neq 0$.
(b): If $A$ is not square, $\operatorname {graph}A\coloneq \operatorname {graph}A^{\prime }$, where $A^{\prime }$ is the smallest square matrix obtained by appending rows or columns of zeros to $A$.

(ii)

A walk in $\operatorname {graph}A\equiv (V,E)$ is a nonempty finite sequence of edges $(i_{1},i_{2})$, $(i_{2},i_{3})$, $\ldots$, $(i_{\ell -1},i_{\ell })$ in $E$. The set of all walks in $\operatorname {graph}A$ is denoted $\operatorname {walks}A$.

(iii)

Let $p\in \operatorname {walks}A$. The length of $p$, denoted $|p|$, is the total number of edges in $p$. $\operatorname {head}p$ (resp., $\operatorname {last}p$) is the first (resp., last) vertex in $p$.

To simplify matters, hereafter we denote edges by $i\rightarrow j$ instead of $(i,j)$ and walks by $i_{1}\rightarrow i_{2}\rightarrow \cdots \rightarrow i_{\ell }$ instead of $(i_{1},i_{2})$, $(i_{2},i_{3})$, $\ldots$, $(i_{\ell -1},i_{\ell })$. We use the terms “row” and “vertex” interchangeably.

Let $B\coloneq (b_{ij})$ be an $m\times n$ substochastic matrix. We define the sets

$$\begin{align*} \hat{J}(B) & \coloneq \left\{ 1\leq i\leq m\colon {\textstyle \sum _{j}}b_{ij}<1\right\}, \\ \hat{P}_{i}(B) & \coloneq \Bigl \{ p\in \operatorname {walks}B\colon \operatorname {head}p=i\text{ and }\operatorname {last}p\in \hat{J}(B)\Bigr \}. \end{align*}$$

It is understood that when we write $i\notin \hat{J}(B)$, we mean $i\in \hat{J}(B)^{\complement }\coloneq \{1,\ldots ,m\}\setminus \hat{J}(B)$. Note that if $\hat{J}(B)$ is empty, so too is $\hat{P}_{i}(B)$ for each $i$. We define the index of contraction associated with $B$ by

$$\begin{equation} \widehat{\operatorname {con}}B\coloneq \max \left(0,\sup _{i\notin \hat{J}(B)}\left\{ \operatorname *{inf}_{p\in \hat{P}_{i}(B)}\left|p\right|\right\} \right) \cssId{texmlid5}{\tag{2.1}} \end{equation}$$

subject to the conventions $\inf \emptyset =\infty$ and $\sup \emptyset =-\infty$. We will see shortly that the matrix $B$ is convergent if and only if $\widehat{\operatorname {con}}B$ is finite.

Example 2.3.

The $n\times n$ matrix $B$ in Figure 2.1 satisfies $\hat{J}(B)=\{1\}$ and

$$\begin{equation*} \min _{p\in \hat{P}_{i}(B)}\left|p\right|=i-1\text{ for }i\notin \hat{J}(B). \end{equation*}$$

It follows that $\widehat{\operatorname {con}}B=n-1$.

An immediate consequence of the definition of the index of contraction follows.

Lemma 2.4.

Let $B$ be an $m\times n$ substochastic matrix. If $m\leq n$ (resp., $m>n$) $\widehat{\operatorname {con}}B$ is either infinite or strictly less than $m$ (resp., $n+1$).

Proof.

Suppose $m\leq n$. Let $i_{1}\notin \hat{J}(B)$ and $p\coloneq i_{1}\rightarrow \cdots \rightarrow i_{\ell }$ be a walk in $\hat{P}_{i_{1}}(B)$. Since $i_{\ell }\in \hat{J}(B)$, it follows that $1\leq i_{\ell }\leq m$. This implies that $1\leq i_{k}\leq m$ for all $k$ since by definition, $\operatorname {graph}B$ has no edges of the form $i\rightarrow j$, where $i>m$. Now, suppose $|p|\geq m$. By the pigeonhole principle, we can find integers $u$ and $v$ such that $1\leq u<v\leq \ell$ and $i_{u}=i_{v}$. That is, the walk $p$ contains a cycle (i.e., a subwalk starting and ending at the same vertex). “Removing” the cycle yields the new walk

$$\begin{equation*} p^{\prime }\coloneq i_{1}\rightarrow i_{2}\rightarrow \cdots \rightarrow i_{u}\rightarrow i_{v+1}\rightarrow i_{v+2}\rightarrow \cdots \rightarrow i_{\ell } \end{equation*}$$

in $\hat{P}_{i_{1}}(B)$ satisfying $|p^{\prime }|<|p|$. If $|p^{\prime }|\geq m$, we can continue removing cycles until we arrive at a walk $p^{\prime \prime }\in \hat{P}_{i_{1}}(B)$ satisfying $|p^{\prime \prime }|<m$. The case of $m>n$ is handled similarly.

■

We are now ready to present our main result related to substochastic matrices. In the statement below, it is understood that if $B$ is a square matrix, $B^{0}=I$.

Theorem 2.5.

Let $B$ be a square substochastic matrix. If $\alpha \coloneq \widehat{\operatorname {con}}B$ is finite,

$$\begin{equation*} 1=\Vert B^{0}\Vert _{\infty }=\cdots =\Vert B^{\alpha }\Vert _{\infty }>\Vert B^{\alpha +1}\Vert _{\infty }\geq \Vert B^{\alpha +2}\Vert _{\infty }\geq \cdots . \end{equation*}$$

Otherwise,

$$\begin{equation*} 1=\Vert B^{1}\Vert _{\infty }=\Vert B^{2}\Vert _{\infty }=\cdots . \end{equation*}$$

Before giving a proof, it is useful to record some consequences of the above.

Corollary 2.6.

Let $B$ be a square substochastic matrix. Then, its spectral radius is no larger than one. Moreover, the following statements are equivalent:

(i): $\widehat{\operatorname {con}}B$ is finite.
(ii): $B$ is convergent.
(iii): $I-B$ is nonsingular.

The above can be considered a generalization of the well-known result that a square stochastic (a.k.a. Markov) matrix has spectral radius no larger than one and at least one eigenvalue equal exactly to one (recall that for any matrix $M$, $I-M$ is singular if and only if $\lambda =1$ is an eigenvalue of $M$).

Proof.

The claim that the spectral radius of $B$ is no larger than one in magnitude is a direct consequence of the fact that $\Vert B\Vert _{\infty }\leq 1$.

(i) $\implies$ (ii) follows immediately from Theorem 2.5, while (ii) $\implies$ (iii) is true for any matrix. We prove below, by contrapositive, the claim (iii) $\implies$ (i).

Suppose $\widehat{\operatorname {con}}B$ is infinite. Let $R$ be the set of rows $i\notin \hat{J}(B)$ for which $\hat{P}_{i}(B)$ is empty. Due to our assumptions, there is at least one such row and hence $R$ is nonempty. Without loss of generality, we may assume $R=\{1,\ldots ,r\}$ for some $1\leq r\leq n$, where $n$ is the order of $B$ (otherwise, replace $B$ by $PBP^{\intercal }$, where $P$ is an appropriately chosen permutation matrix). Let $e\in \mathbb{R}^{r}$ be the column vector whose entries are all one. If $r=n$, each row-sum of $B$ is one (i.e., $Be=e$ so that $(I-B)e=0$). Otherwise, $B$ has the block structure

$$\begin{equation*} B = \left( \begin{array}{c|c} B_1 & 0 \\\hline B_2 & B_3 \end{array} \right), \text{ where } B_1 \in \mathbb{R}^{r\times r}. \end{equation*}$$

The partition above ensures that for each row $i\notin R$, $i\in \hat{J}(B)$ or $\hat{P}_{i}(B)$ is nonempty. Therefore, $\widehat{\operatorname {con}}B_{3}$ is finite, and hence the linear system $(I-B_{3})x=B_{2}e$ has a unique solution $x$. Moreover, since the row-sums of $B_{1}$ are one, $B_{1}e=e$. Therefore,

$$\begin{equation*} (I-B)\begin{pmatrix} e\\ x \end{pmatrix}=\begin{pmatrix} e\\ x \end{pmatrix}-\begin{pmatrix} B_{1}e\\ B_{2}e+B_{3}x \end{pmatrix}=\begin{pmatrix} e\\ x \end{pmatrix}-\begin{pmatrix} e\\ x \end{pmatrix}=0. \end{equation*}$$■

Corollary 2.7.

A square irreducible substochastic matrix $B$ is convergent if and only if $\hat{J}(B)$ is nonempty.

The above result is well known. It can be obtained, for example, by Reference 21, Corollary 1.19 and Lemma 2.8. We give a short alternate proof using Corollary 2.6:

Proof.

Since a square matrix is irreducible if and only if its digraph is strongly connected Reference 21, $\widehat{\operatorname {con}}B$ is finite if and only if $\hat{J}(B)$ is nonempty. The result now follows from Corollary 2.6.

■

If $B$ is a square substochastic matrix, we can always find a permutation matrix $P$ and an integer $r\geq 1$ such that $PBP^{\intercal }$ has the block triangular structure

$$\begin{equation} PBP^{\intercal }=\begin{pmatrix} B_{11} & B_{12} & \cdots & B_{1r}\\ & B_{22} & \cdots & B_{2r}\\ & & \ddots & \vdots \\ & & & B_{rr} \end{pmatrix}, \cssId{texmlid2}{\tag{2.2}} \end{equation}$$

where each $B_{ii}$ is a square substochastic matrix that is either irreducible or a $1\times 1$ zero matrix (it is understood that if $r=1$, then $B=B_{11}$). Following Reference 7Reference 21, we refer to this as the normal form of $B$ (it is shown in Reference 7, p. 90 that the normal form of a matrix is unique up to permutations by blocks). Since $\det (PBP^{\intercal }-\lambda I)=\prod _{i}\det (B_{ii}-\lambda I)$, the spectrum of $B$ satisfies

$$\begin{equation} \sigma (B)=\sigma (B_{11})\cup \cdots \cup \sigma (B_{rr}). \cssId{texmlid3}{\tag{2.3}} \end{equation}$$

This observation motivates the next result.

Theorem 2.8.

Let $B$ be a square substochastic matrix with normal form Equation 2.2. $B$ is convergent if and only if $\hat{J}(B_{ii})$ is nonempty for each $i$. Moreover, if $B$ is convergent,

$$\begin{equation} \max _{i}\left\{ \widehat{\operatorname {con}}B_{ii}\right\} \leq \widehat{\operatorname {con}}B\leq N+\widehat{\operatorname {con}}B_{rr}, \cssId{texmlid4}{\tag{2.4}} \end{equation}$$

where $N\coloneq \sum _{i=1}^{r-1}n_{i}$ and $n_{i}$ is the order of the matrix $B_{ii}$ (it is understood that if $r=1$, then $N=0$).

Proof.

The first claim is a consequence of Corollary 2.7 and Equation 2.3.

We prove now the leftmost inequality in Equation 2.4. First, note that $\Vert B^{k}\Vert _{\infty }=\Vert PB^{k}P^{\intercal }\Vert _{\infty }=\Vert (PBP^{\intercal })^{k}\Vert _{\infty }$. Moreover, the block diagonal entries of $(PBP^{\intercal })^{k}$ are the matrices $B_{11}^{k},\ldots ,B_{rr}^{k}$. Therefore, for each $i$, $\Vert B_{ii}^{k}\Vert _{\infty }\leq \Vert B^{k}\Vert _{\infty }$ and hence $\widehat{\operatorname {con}}B_{ii}\leq \widehat{\operatorname {con}}B$ by Theorem 2.5.

We prove now the rightmost inequality in Equation 2.4. If $\widehat{\operatorname {con}}B\leq N$, the inequality is trivial. As such, we proceed assuming that $N<\widehat{\operatorname {con}}B<\infty$. First, note that $\widehat{\operatorname {con}}B=\widehat{\operatorname {con}}(PBP^{\intercal })$. Therefore, $\widehat{\operatorname {con}}B=|p|$, where $p \in \operatorname {walks}(PBP^\intercal )$. Due to the block triangular structure of $PBP^{\intercal }$, we can write $p$ as

$$\begin{equation*} p=i_{1}\rightarrow \cdots \rightarrow i_{u}\rightarrow j_{1}\rightarrow \cdots \rightarrow j_{v}, \end{equation*}$$

where $u\leq N$ and $j_{k}>N$ for all $k$. Defining $j_{k}^{\prime }\coloneq j_{k}-N$, it follows that $p^{\prime }\coloneq j_{1}^{\prime }\rightarrow \cdots \rightarrow j_{v}^{\prime }$ is a walk whose length is no larger than any walk in $\hat{P}_{j_{1}^{\prime }}(B_{rr})$, from which we obtain $|p^{\prime }|\leq \widehat{\operatorname {con}}B_{rr}$. Therefore,

$$\begin{equation*} \widehat{\operatorname {con}}B=\left|p\right|\leq u+\left|p^{\prime }\right|\leq N+\widehat{\operatorname {con}}B_{rr}. \end{equation*}$$■

Returning to our goal of proving Theorem 2.5, we first establish some lemmata related to substochastic matrices. The first lemma is a consequence of definitions and requires no proof.

Lemma 2.9.

Let $B$ be an $m\times n$ substochastic matrix. Then, $\Vert B\Vert _{\infty }<1$ if and only if $\hat{J}(B)=\{1,\ldots ,m\}$.

Lemma 2.10.

Let $B\coloneq (b_{ij})$ and $C\coloneq (c_{ij})$ be compatible (i.e., the product $BC$ is well-defined) substochastic matrices. Then,

(i): $BC$ is a substochastic matrix.
(ii): If $i\in \hat{J}(B)$, then $i\in \hat{J}(BC)$.
(iii): If $i\notin \hat{J}(B)$, then $i\in \hat{J}(BC)$ if and only if there exists $h\in \hat{J}(C)$ such that $i\rightarrow h$ is an edge in $\operatorname {graph}B$.
(iv): $i\rightarrow j$ is an edge in $\operatorname {graph}(BC)$ if and only if there exist edges $i\rightarrow h$ and $h\rightarrow j$ in $\operatorname {graph}B$ and $\operatorname {graph}C$, respectively.

Proof.

(i): $BC$ has nonnegative entries and $\Vert BCe\Vert _{\infty }\leq \Vert BC\Vert _{\infty }\leq \Vert B\Vert _{\infty }\Vert C\Vert _{\infty }\leq 1$.
(ii): Note first that $\sum _{j}[BC]_{ij}=\sum _{j}\sum _{k}b_{ik}c_{kj}=\sum _{k}b_{ik}\sum _{j}c_{kj}\leq \sum _{k}b_{ik}$. If $i\in \hat{J}(B)$, then $\sum _{k}b_{ik}<1$ and the desired result follows.
(iii): Suppose $i\notin \hat{J}(B)$. If there exists $h\in \hat{J}(C)$ such that $i\rightarrow h$ is an edge in $\operatorname {graph}B$, then $\sum _{j}c_{hj}<1$ and $\sum _{j}[BC]_{ij}=b_{ih}\sum _{j}c_{hj}+\sum _{k\neq h}b_{ik}\sum _{j}c_{kj}<\sum _{k}b_{ik}\leq 1$. Otherwise, $\sum _{j}c_{kj}=1$ for all $k$ with $b_{ik}\neq 0$ and hence $\sum _{j}[BC]_{ij}=\sum _{k}b_{ik}\sum _{j}c_{kj}=\sum _{k}b_{ik}=1$.
(iv): Suppose $i\rightarrow h$ and $h\rightarrow j$ are edges in $\operatorname {graph}B$ and $\operatorname {graph}C$, respectively. Then, $[BC]_{ij}=\sum _{k}b_{ik}c_{kj}\geq b_{ih}c_{hj}>0$. Otherwise, for each $k$, at least one of $b_{ik}$ or $c_{kj}$ is zero and hence $[BC]_{ij}=0$.■

Lemma 2.11.

Let $B$ be a square substochastic matrix, $i\notin \hat{J}(B)$, and $k$ be a positive integer. Then, $i\in \hat{J}(B^{k})$ if and only if there is a walk $p$ in $\hat{P}_{i}(B)$ such that $|p|<k$.

Proof.

To simplify notation, let $i_{1}\coloneq i$.

Suppose there exists a walk $i_{1}\rightarrow i_{2}\rightarrow \cdots \rightarrow i_{\ell }$ in $\hat{P}_{i_{1}}(B)$. We claim that $i_{1}\rightarrow i_{\ell }$ is an edge in $\operatorname {graph}(B^{\ell -1})$. If this is the case, Lemma 2.10 (ii) and (iii) guarantee that $i_{1}\in \hat{J}(B^{\ell -1}B)=\hat{J}(B^{\ell })$. If $\ell \leq k$, $i_{1}\in \hat{J}(B^{k})$ by Lemma 2.10 (ii), as desired.

We now return to the claim in the previous paragraph. Since the claim is trivial if $\ell =2$, we proceed assuming $\ell >2$. Let $n$ be an integer satisfying $2<n\leq \ell$. If $i_{1}\rightarrow i_{n-1}$ is an edge in $\operatorname {graph}(B^{n-2})$, then since $i_{n-1}\rightarrow i_{n}$ is an edge in $\operatorname {graph}B$, Lemma 2.10 (iv) implies that $i_{1}\rightarrow i_{n}$ is an edge in $\operatorname {graph}(B^{n-2}B)=\operatorname {graph}(B^{n-1})$. Since $i_{1}\rightarrow i_{2}$ is an edge in $\operatorname {graph}B$, it follows by induction that $i_{1}\rightarrow i_{\ell }$ is an edge in $\operatorname {graph}(B^{\ell -1})$, as desired.

As for the converse, suppose $i_{1}\in \hat{J}(B^{k})$. Let $\ell$ be the smallest positive integer such that $i_{1}\notin \hat{J}(B^{\ell -1})$ and $i_{1}\in \hat{J}(B^{\ell })$. Since $i_{1}\notin \hat{J}(B)$ and $i_{1}\in \hat{J}(B^{k})$, it follows that $\ell \leq k$. By Lemma 2.10 (iii), there exists $i_{\ell }\in \hat{J}(B)$ such that $i_{1}\rightarrow i_{\ell }$ is an edge in $\operatorname {graph}(B^{\ell -1})$.

If $\ell =2$, the trivial walk $i_{1}\rightarrow i_{\ell }$ is in $\hat{P}_{i_{1}}(B)$, and hence we proceed assuming $\ell >2$. Let $n$ be an integer satisfying $2<n\leq \ell$. If there exists a positive integer $i_{n}$ such that $i_{1}\rightarrow i_{n}$ is an edge in $\operatorname {graph}(B^{n-1})=\operatorname {graph}(B^{n-2}B)$, Lemma 2.10 (iv) implies that there exists a positive integer $i_{n-1}$ such that $i_{1}\rightarrow i_{n-1}$ is an edge in $\operatorname {graph}(B^{n-2})$ and $i_{n-1}\rightarrow i_{n}$ is an edge in $\operatorname {graph}B$. Since $i_{1}\rightarrow i_{\ell }$ is an edge in $\operatorname {graph}(B^{\ell -1})$, it follows by induction that $i_{n-1}\rightarrow i_{n}$ is an edge in $\operatorname {graph}B$ for each integer $n$ satisfying $2\leq n\leq \ell$. Therefore, $i_{1}\rightarrow i_{2}\rightarrow \cdots \rightarrow i_{\ell }$ is a walk in $\hat{P}_{i_{1}}(B)$, as desired.

■

We are now ready to prove Theorem 2.5.

Proof of Theorem 2.5.

Since $\Vert B^{k+1}\Vert _{\infty }\leq \Vert B^{k}\Vert _{\infty }\Vert B\Vert _{\infty }\leq \Vert B^{k}\Vert _{\infty }$, the inequalities $1\geq \Vert B^{1}\Vert _{\infty }\geq \Vert B^{2}\Vert _{\infty }\geq \cdots$ follow trivially.

The remaining inequalities in the theorem statement follow by applying Lemma 2.11 to each row not in $\hat{J}(B)$ and invoking Lemma 2.9.

■

2.2. M-matrices

In this subsection, we recall some well-known results on M-matrices (see, e.g., Reference 2, Chapter 6).

Definition 2.12.

An M-matrix is a square matrix $A$ that can be expressed in the form $A=sI-B$, where $B$ is a nonnegative matrix and $s\geq \rho (B)$, where $\rho (B)$ is the spectral radius of $B$.

Definition 2.13.

A Z-matrix is a real matrix with nonpositive off-diagonal entries.

Definition 2.14.

An L-matrix is a Z-matrix with positive diagonal entries.

Proposition 2.15.

A nonsingular M-matrix is an L-matrix.

Definition 2.16.

Let $A$ be a square real matrix. $A$ is monotone if and only if it is nonsingular and its inverse consists only of nonnegative entries.

Proposition 2.17.

The following are equivalent:

(i): $A$ is a nonsingular M-matrix.
(ii): $A$ is a monotone Z-matrix.

We close this subsection by introducing the following enlargement of the family of L-matrices (Definition 2.14), to be used in what follows.

Definition 2.18.

An $\operatorname {L}_{0}$-matrix is a Z-matrix with nonnegative diagonal entries.

2.3. Weakly chained diagonally dominant (w.c.d.d.) matrices

Before we can define w.c.d.d. matrices, we require some preliminary definitions.

Definition 2.19.

Let $A\coloneq (a_{ij})$ be a complex matrix.

(i): The $i$th row of $A$ is w.d.d. (resp., s.d.d.) if $|a_{ii}|\geq \sum _{j\neq i}|a_{ij}|$ (resp., $>$).
(ii): $A$ is w.d.d. (resp., s.d.d.) if all of its rows are w.d.d. (resp., s.d.d.).

Let $A\coloneq (a_{ij})$ be an $m\times n$ complex w.d.d. matrix. We define the sets

$$\begin{align*} J(A) & \coloneq \left\{ 1\leq i\leq m\colon \left|a_{ii}\right|>{\textstyle \sum _{j\neq i}}\left|a_{ij}\right|\right\}, \\ \text{ and }P_{i}(A) & \coloneq \Bigl \{ p\in \operatorname {walks}A\colon \operatorname {head}p=i\text{ and }\operatorname {last}p\in J(A)\Bigr \}. \end{align*}$$

Note that if $J(A)$ is empty, so too is $P_{i}(A)$ for each $i$. We will see shortly that the sets $J(\cdot )$ and $P_{i}(\cdot )$ are related to $\hat{J}(\cdot )$ and $\hat{P}_{i}(\cdot )$.

We are now ready to introduce w.c.d.d. matrices:

Definition 2.20.

A square complex matrix $A$ is w.c.d.d. if the points below are satisfied:

(i): $A$ is w.d.d.
(ii): $J(A)$ is nonempty.
(iii): For each $i\notin J(A)$, $P_{i}(A)$ is nonempty.

We now define the index of connectivity associated with a square complex w.d.d. matrix $A$ as

$$\begin{equation*} \operatorname {con}A\coloneq \max \left(0,\sup _{i\notin J(A)}\left\{ \operatorname *{inf}_{p\in P_{i}(A)}\left|p\right|\right\} \right) \end{equation*}$$

(compare this with the index of contraction $\widehat{\operatorname {con}}$ defined in Equation 2.1). The lemma below is a trivial consequence of the definitions above and as such requires no proof.

Lemma 2.21.

A square complex w.d.d. matrix $A$ is w.c.d.d. if and only if $\operatorname {con}A$ is finite.

We are now able to establish a duality between w.d.d. L-matrices (or more accurately, $\operatorname {L}_{0}$-matrices) and substochastic matrices that, as we will see, connects the nonsingularity of the former to the convergence of the latter.

Lemma 2.22.

Let $A\coloneq (a_{ij})$ be an $n\times n$ w.d.d. $\operatorname {L}_{0}$-matrix and $D\coloneq (d_{ij})$ be an $n\times n$ diagonal matrix whose diagonal entries are positive and satisfy $d_{ii}\leq 1/a_{ii}$ for each $i$ such that $a_{ii}\neq 0$. Then, $B\coloneq I-DA$ is substochastic and

$$\begin{equation} \operatorname {con}A=\widehat{\operatorname {con}}B. \cssId{texmlid6}{\tag{2.5}} \end{equation}$$

Conversely, let $B$ be an $n\times n$ substochastic matrix and $D$ be an $n\times n$ diagonal matrix whose diagonal entries are positive. Then, $A\coloneq D(I-B)$ is a w.d.d. $\operatorname {L}_{0}$-matrix and Equation 2.5 holds.

Proof.

We prove only the first claim, the converse being handled similarly.

Let $A$ and $B\coloneq I-DA$ be given as in the lemma statement. To simplify notation, denote by $a_{ij}$ and $b_{ij}$ the elements of $A$ and $B$. First, note that $b_{ii}=1-d_{ii}a_{ii}\geq 0$ and $b_{ij}=-d_{ii}a_{ij}\geq 0$ whenever $i\neq j$. Since

$$\begin{equation*} \sum _{j}b_{ij}=1-\sum _{j}d_{ii}a_{ij}=1-d_{ii}\left(a_{ii}-\sum _{j\neq i}\left|a_{ij}\right|\right)\leq 1, \end{equation*}$$

it follows that $B$ is substochastic and $J(A)=\hat{J}(B)$. Letting $\operatorname {graph}A\equiv (V,E)$ and $\operatorname {graph}B\equiv (V^{\prime },E^{\prime })$, note that $V=V^{\prime }$ and

$$\begin{equation*} E\setminus \{(i,i)\}_{i}\subset E^{\prime }\subset E. \end{equation*}$$

More concisely, $\operatorname {graph}B$ is simply $\operatorname {graph}A$ with zero or more self-loops (i.e., edges of the form $i\rightarrow i$) removed. As a result of these facts, Equation 2.5 follows immediately.

■

Example 2.23.

Let $A\coloneq (a_{ij})$ be a square w.d.d. L-matrix of order $n$ and

$$\begin{equation*} B_{A}\coloneq I-\operatorname {diag}(a_{11},\ldots ,a_{nn})^{-1}A \end{equation*}$$

denote the point Jacobi matrix associated with $A$ (cf. Reference 21, Chapter 3). By the previous results, $A$ is w.c.d.d. if and only if $\operatorname {con}A=\widehat{\operatorname {con}}B_{A}$ is finite.

Note that the substochastic matrix in Figure 2.1 is the point Jacobi matrix associated with the w.d.d. L-matrix in Figure 2.2.

We now restate and prove characterization Equation 1.1 from the introduction.

Theorem 2.24.

The following are equivalent:

(i): $A$ is a nonsingular w.d.d. M-matrix.
(ii): $A$ is a nonsingular w.d.d. L-matrix.
(iii): $A$ is a w.c.d.d. L-matrix.

Since a nonsingular w.d.d. $\operatorname {L}_{0}$-matrix must be an L-matrix, we can safely replace all occurrences of “L-matrix” with “$\operatorname {L}_{0}$-matrix” in the above theorem without affecting its validity (recall that any w.c.d.d. matrix is nonsingular Reference 18).

Proof.

(i)$\implies$(ii) follows from Proposition 2.15 while (iii)$\implies$(i) is established in Reference 4, Theorem 2.2. We prove below the claim (ii)$\implies$(iii).

Let $A\coloneq (a_{ij})$ be a nonsingular w.d.d. L-matrix of order $n$. Then, the associated point Jacobi matrix $B_{A}$ is substochastic and $I-B_{A}$ is nonsingular since

$$\begin{equation*} I-B_{A}=\operatorname {diag}(a_{11},\ldots ,a_{nn})^{-1}A. \end{equation*}$$

Corollary 2.6 and Lemma 2.22 imply that $\operatorname {con}A=\widehat{\operatorname {con}}B_{A}$ is finite. Therefore, by Lemma 2.21, $A$ is w.c.d.d.

■

Remark 2.25.

Instead of calling upon the results of Reference 4, it is also possible to prove (iii)$\implies$(i) of Theorem 2.24 directly by using arguments involving the index of contraction. In particular, let $A$ be a w.c.d.d. L-matrix of order $n$. Then, by Lemma 2.21 and Lemma 2.22, the associated point Jacobi matrix $B_{A}$ is substochastic with $\widehat{\operatorname {con}}B_{A}=\operatorname {con}A$ finite. By Corollary 2.6, $B_{A}$ is convergent and hence the Neumann series $I+B_{A}+B_{A}^{2}+\cdots$ for the inverse of $I-B_{A}$ converges to a matrix whose entries are nonnegative. Therefore, $A$ is monotone by Definition 2.16, and hence a nonsingular M-matrix by Proposition 2.17.

An immediate consequence of Theorem 2.24, which can be considered an analogue of Corollary 2.7, is given below.

Corollary 2.26.

A square irreducible w.d.d. L-matrix $A$ is a nonsingular M-matrix if and only if $J(A)$ is nonempty.

While the reverse direction in the above result is well known Reference 21, Corollary 3.20, we are not aware of a reference for the forward direction.

3. Computing the index of contraction

In this section, we present a procedure to compute the index of contraction $\widehat{\operatorname {con}}B$ of a substochastic matrix $B$ and show that it is robust in the presence of inexact (i.e., floating point) arithmetic.

By the results of the previous section, such a procedure can also be used to determine if an arbitrary w.d.d. matrix $A$ is a nonsingular M-matrix as follows. If $A$ is not a square L-matrix, it is trivially not a nonsingular M-matrix (Proposition 2.15). Otherwise, we can check the finitude of the index of contraction of its associated point Jacobi matrix $B_{A}$ to determine whether or not $A$ is a nonsingular M-matrix (recall Example 2.23 and Theorem 2.24).

3.1. The procedure

Before we can describe the procedure, we require the notion of a vertex contraction (a.k.a. vertex identification), a generalization of the well-known notion of edge contraction from graph theory.

Definition 3.1.

Let $G\equiv (V,E)$ be a graph, $W\subset V$, $w$ denote a new vertex (i.e., $w\notin V$), and $f$ be a function which maps every vertex in $V\setminus W$ to itself and every vertex in $W$ to $w$ (i.e., $f|_{V\setminus W}=\operatorname {id}_{V\setminus W}$ and $f|_{W}(\cdot )=w$). The vertex contraction of $G$ with respect to $W$ is a new graph $G^{\prime }\equiv (V^{\prime },E^{\prime })$, where $V^{\prime }\coloneq (V\setminus W)\cup \{w\}$ and $E^{\prime }\coloneq \{(f(i),f(j))\colon (i,j)\in E\}$.

An overview of the procedure for computing the index of contraction for an arbitrary substochastic matrix $B$ is given below:

(1): Obtain the vertex contraction of $\operatorname {graph}B$ with respect to $\hat{J}(B)$. Label the new vertex in the contraction $w=0$ and the new vertex set $V^{\prime }$. Note that $V^{\prime }=\hat{J}(B)^{\complement }\cup \{0\}$ (recall that the superscript $\complement$ denotes complement).
(2): Reverse all edges in the resulting graph (see, e.g., Figure 3.1).
(3): In the resulting graph, find the shortest distances $d(i)$ from the new vertex $0$ to all vertices $i\in V^{\prime }$ by a breadth-first search (BFS) starting at $0$. It is understood that $d(0)=0$ and that if $i$ is unvisited in the BFS, $d(i)=\infty$.
(4): Return $\max _{i\in V^{\prime }}d(i)$.

That this procedure terminates is trivial (BFS is performed on a graph with finitely many vertices). As for the correctness of the procedure, it is easy to verify that

$$\begin{equation*} d(i)=\inf _{p\in \hat{P}_{i}(B)}|p|\text{ for }i\notin \hat{J}(B) \end{equation*}$$

so that $\widehat{\operatorname {con}}B=\max (0,\sup _{i\notin \hat{J}(B)}d(i))=\max _{i\in V^{\prime }}d(i)$.

Remark 3.2.

Since BFS does not revisit vertices, the correctness of the procedure is unaffected if $\operatorname {graph}B$ is preprocessed to remove self-loops (i.e., edges of the form $i\rightarrow i$) and edges of the form $i\rightarrow j$ with $i\in \hat{J}(B)$.

Algorithm 1 gives precise pseudocode for steps (1) to (4). Without loss of generality, it is assumed that the input matrix is square (the rectangular case is obtained by a few trivial additions to the code). The pseudocode makes use of the list and queue data structures (see, e.g., Reference 6, Chapter 10). The operation $L$.add($x$) appends the element $x$ to the list $L$. The operation $Q$.enqueue($x$) adds the element $x$ to the back of the queue $Q$. The operation $Q$.dequeue() removes and returns the element at the front of the queue $Q$.

It is obvious that if the input to Algorithm 1 is a dense matrix of order $n$, $\Theta (n^{2})$ operations are required. Suppose instead that we restrict our inputs to matrices $B\coloneq (b_{ij})$ that are sparse in the sense that $\operatorname {nnz}\coloneq \max _{i}|\{j\colon b_{ij}\neq 0\}|$, the maximum number of nonzero entries per row, is bounded independent of $n$ (i.e., $\operatorname {nnz}=\Theta (1)$ as $n\rightarrow \infty$). If the matrices are stored in an appropriate format (e.g., compressed sparse row (CSR) format, Ellpack-Itpack, etc. Reference 17), the loops on lines 6 and 20 require only a constant number of iterations for each fixed $i$. In this case, $\Theta (n)$ operations are required. An obvious generalization of this fact is that if $\operatorname {nnz}=O(f(n))$, $O(nf(n))$ operations are required.

3.2. Floating point arithmetic considerations

The loop on line 6 of Algorithm 1 computes the $i$th row-sum of the substochastic matrix $B\coloneq (b_{ij})$. In the presence of floating point arithmetic, the operation $t+b_{ij}$ on line 7 can introduce error into calculations. In order to analyze this error, we take the standard model of floating point arithmetic in which floating point addition introduces error proportional to the size of the result:

$$\begin{equation} fl(x+y)=\left(x+y\right)\left(1+\delta _{x,y}\right),\text{ where }\left|\delta _{x,y}\right|\leq \epsilon . \cssId{texmlid8}{\tag{3.1}} \end{equation}$$

$\epsilon >0$ is a machine-dependent constant (often referred to as machine epsilon) which gives an upper bound on the relative error due to rounding. In performing our analyses, we make the standard assumptions that the order $n$ of the input matrix $B$ satisfies $n\epsilon \leq 1$ Reference 9 and that the entries of $B$ are floating point numbers.

A floating point implementation of the loop on line 6 is represented by the recurrence $S_{j}\coloneq fl(S_{j-1}+b_{ij})$ with initial condition $S_{0}\coloneq 0$. Letting $\gamma _{k}\coloneq k\epsilon /(1-k\epsilon )$, this direct implementation has an error bound of Reference 9, Eq. (2.6)

$$\begin{equation} \left|S_{n}-\sum _{j}b_{ij}\right|\leq \gamma _{\operatorname {nnz}-1}\sum _{j}b_{ij}\leq \gamma _{\operatorname {nnz}-1}. \cssId{texmlid7}{\tag{3.2}} \end{equation}$$

Recall that $\operatorname {nnz}$ is the maximum number of nonzero entries per row of the matrix $B$. If the matrix $B$ is sparse (i.e., $\operatorname {nnz}=\Theta (1)$ as $n\rightarrow \infty$), we obtain

$$\begin{equation*} \gamma _{\operatorname {nnz}-1}=(\operatorname {nnz}-1)\epsilon +O(\epsilon ^{2})\text{ as }\epsilon \rightarrow 0 \end{equation*}$$

by the power series representation of $\gamma _{k}$. In this case, for each $i$, the absolute error in computing $\sum _{j}b_{ij}$ is independent of $n$.

Note that if the exact value of $\sum _{j}b_{ij}$ is close to $1$, the comparison $t<1$ on line 9 may return either a false-positive or a false-negative. Motivated by Equation 3.2, an implementation of Algorithm 1 should use instead the condition $t<1-\operatorname {tol}$, where $\operatorname {tol}$ is a small constant strictly larger than $\gamma _{\operatorname {nnz}-1}$ to preclude the possibility that the condition evaluates to true when the exact value of $\sum _{j}b_{ij}$ is $1$ (for simplicity, we assume $1-\operatorname {tol}$ has a precise floating point representation). Then, the error bound Equation 3.2 and discussion above yield the accuracy result below.

Lemma 3.3.

Let $B$ be a substochastic matrix with at most $\operatorname {nnz}$ nonzero entries per row. Denoting by $(\widehat{\operatorname {con}}B)_{fl}$ the quantity computed by Algorithm 1 under the standard model of floating point arithmetic Equation 3.1 and with condition $t<1$ replaced by $t<1-\operatorname {tol}$, where $\operatorname {tol}>\gamma _{\operatorname {nnz}-1}$, the following results hold:

(i): if $\widehat{\operatorname {con}}B=\infty$, then $(\widehat{\operatorname {con}}B)_{fl}=\widehat{\operatorname {con}}B$.
(ii): if $\widehat{\operatorname {con}}B\neq \infty$ and $\sum _{j}b_{ij}\leq 1-2\operatorname {tol}$ for $i\in \hat{J}(B)$, then $(\widehat{\operatorname {con}}B)_{fl}=\widehat{\operatorname {con}}B$.

Remark 3.4.

If $B$ is not sparse, the error Equation 3.2 depends on $n$. In this case, one should substitute the naïve summation outlined by the loop on line 6 for a more scalable algorithm, such as Kahan’s summation algorithm, whose absolute error in approximating $\sum _{j}b_{ij}$, is $(2\epsilon +O(n\epsilon ^{2}))\sum _{j}b_{ij}\leq 2\epsilon +O(n\epsilon ^{2})$ Reference 9, Eq. (3.11), which is independent of $n$ due to the assumption $n\epsilon \leq 1$. We can obtain an analogue of Lemma 3.3 under Kahan summation by choosing $\operatorname {tol}$ appropriately.

Note that Lemma 3.3 suggests that the value of $(\widehat{\operatorname {con}}B)_{fl}$ and $\widehat{\operatorname {con}}B$ may disagree in certain cases. Fortunately, as demonstrated in the next example, this occurs only if the matrix $B$ is “nearly nonconvergent” (i.e., $\rho (B)=1-\epsilon _{0}$, where $\epsilon _{0}>0$ is close to zero). This error may even be considered desirable behaviour since a nearly nonconvergent matrix may not be convergent in the presence of floating point error.

Example 3.5.

Consider the $n\times n$ matrix

$$\begin{equation*} B_{\nu }\coloneq \begin{pmatrix} & 1\\ & & 1\\ & & & \ddots \\ & & & & 1\\ & & & & & 1\\ 1/n-\nu & 1/n & 1/n & \cdots & 1/n & 1/n \end{pmatrix}, \end{equation*}$$

where $0<\nu \leq 1/n$. Note that even though $\widehat{\operatorname {con}}B_{\nu }=n-1$ independent of the value of $\nu$, $\rho (B_{\nu })\rightarrow 1$ as $\nu \rightarrow 0$. When $\nu$ is very close to zero, floating point error may cause Algorithm 1 to erroneously determine that $\hat{J}(B_{\nu })$ is empty and thereby mistakenly conclude that the index of contraction is infinite.

We close this section by discussing stability. The test in Reference 15, which determines if an arbitrary matrix is a nonsingular M-matrix, uses a modified Gaussian elimination procedure. As such, to establish numerical stability, the author proves that the growth factor (see the definition in Reference 8) of the test is bounded by the order of the input matrix Reference 15, Theorem 3.1. In our case, the floating point error made in computing $\sum _{i}b_{ij}$ has no bearing on the error made in computing $\sum _{i^{\prime }}b_{i^{\prime }j}$ for distinct rows $i$ and $i^{\prime }$. That is, floating point errors do not propagate from row to row. Moreover, as demonstrated in the previous paragraphs, the error made in computing each row-sum can be bounded by a constant (without any additional effort in the sparse case, and with, e.g., Kahan summation in the dense case). As such, we conclude that Algorithm 1 is stable in the sense that it does not involve numbers that grow large due to floating point error.

4. Numerical experiments

In this section, we compare the efficiency of our test described at the beginning of Section 3 to Peña’s test detailed in Reference 15. To minimize bias, we run the tests on randomly sampled matrices (sampled according to the procedure in Appendix A).

We run the tests on matrices whose maximum number of nonzeros per row ($\operatorname {nnz}$) are $6$, $12$, $24$, and $48$. We employ two versions of our test: a sparse version, in which the matrices are stored in compressed sparse row (CSR) format, and a dense version, in which the matrices are two-dimensional arrays. All tests are performed on an Intel Xeon E5440 2.83GHz CPU. The average time to process a randomly sampled matrix is shown in Figure 4.1a (error bars are omitted as even the 99% confidence interval is too small to be visible). We mention that in terms of accuracy, the tests produced the same results on all randomly sampled matrices (Figure 4.1b).

Figure 4.1a suggests that our test outperforms Peña’s. Even for the experiments involving the $1024\times 1024$ sparse matrices (small by most scientific computing standards), our sparse implementation executes on the order of tenths of milliseconds while Peña’s test executes on the order of seconds.

Appendix A. Sampling procedure

This appendix details the procedure (employed in the numerical experiments of Section 4) used to randomly sample w.d.d. $\operatorname {L}_{0}$-matrices. The procedure, for which pseudocode is given in Algorithm 2, works by sampling a matrix $B\coloneq (b_{ij})_{1\leq i,j\leq n}$ from the space of substochastic matrices and returning $I-B$, which is a w.d.d. $\operatorname {L}_{0}$-matrix by Lemma 2.22.

We use $\operatorname {Unif}\Omega$ to denote a uniform distribution on the sample space $\Omega$. For $\alpha \in \mathbb{R}^{m}$, we use $\operatorname {Dir}\alpha$ to denote a Dirichlet distribution of order $m$ with parameter $\alpha$. It is well known that when $\alpha$ is a vector whose entries are all one, $\operatorname {Dir}\alpha$ is a uniform distribution over the unit simplex in $\mathbb{R}^{m-1}$. We use $x\sim \mathcal{D}$ to mean that $x$ is a sample drawn from the distribution $\mathcal{D}$.

The inputs to the procedure are a positive integer $n$ corresponding to the order of the output matrix and a positive integer $\operatorname {nnz}\leq n$ corresponding to the maximum number of nonzero entries per row.

Appendix B. Generalizing Theorem 2.5

This appendix generalizes Theorem 2.5. To present the generalization, we first extend our notion of walks.

Definition B.1.

Let $(A_{n})_{n\geq 1}$ be a sequence of compatible complex matrices (i.e., the product $A_{k}A_{k+1}$ is well-defined for each $k$).

(i): A walk in $(A_{n})_{n}$ is a nonempty finite sequence of edges $(i_{1},i_{2})$, $(i_{2},i_{3})$, $\ldots$, $(i_{\ell -1},i_{\ell })$ such that each $(i_{k},i_{k+1})$ is an edge in $\operatorname {graph}A_{k}$. The set of all walks in $(A_{n})_{n}$ is denoted $\operatorname {walks}(A_{1},A_{2},\ldots )$.
(ii): For $p\in \operatorname {walks}(A_{1},A_{2},\ldots )$, $\operatorname {head}p$, $\operatorname {last}p$, and $|p|$ are defined in the obvious way.

Note, in particular, that if we fix a square complex matrix $A$, we are returned to the original definition of a walk given in Section 2 if we take $A_{n}\coloneq A$ for all $n$.

It is also useful to generalize the sets $\hat{P}_{i}(\cdot )$ of Section 2. In particular, given a sequence $(B_{n})_{n\geq 1}$ of compatible substochastic matrices, let

$$\begin{equation*} \hat{P}_{i}(B_{1},B_{2},\ldots )\coloneq \Bigl \{ p\in \operatorname {walks}(B_{1},B_{2},\ldots )\colon \operatorname {head}p=i\text{ and }\operatorname {last}p\in \hat{J}(B_{|p|+1})\Bigr \}. \end{equation*}$$

We are now ready to give the generalization.

Theorem B.2.

Let $(B_{n})_{n\geq 1}$ be a sequence of compatible substochastic matrices, $(C_{n})_{n\geq 0}$ be defined by $C_{0}\coloneq I$ and $C_{n}\coloneq B_{1}B_{2}\cdots B_{n}$ whenever $n$ is a positive integer, and

$$\begin{equation*} \widehat{\operatorname {con}}(B_{1},B_{2},\ldots )\coloneq \max \left(0,\sup _{i\notin \hat{J}(B_{1})}\left\{ \operatorname *{inf}_{p\in \hat{P}_{i}(B_{1},B_{2},\ldots )}\left|p\right|\right\} \right). \end{equation*}$$

If $\alpha \coloneq \widehat{\operatorname {con}}(B_{1},B_{2},\ldots )$ is finite, then

$$\begin{equation*} 1=\Vert C_{0}\Vert _{\infty }=\cdots =\Vert C_{\alpha }\Vert _{\infty }>\Vert C_{\alpha +1}\Vert _{\infty }\geq \Vert C_{\alpha +2}\Vert _{\infty }\geq \cdots . \end{equation*}$$

Otherwise,

$$\begin{equation*} 1=\Vert C_{1}\Vert _{\infty }=\Vert C_{2}\Vert _{\infty }=\cdots . \end{equation*}$$

The proof of the above is nearly identical to that of Theorem 2.5, requiring only a simple generalization of Lemma 2.11. However, in this general case, the finitude of the index of contraction is no longer an indicator of convergence.

Example B.3.

Let $(B_{n})_{n\ge 1}$ be a sequence of compatible substochastic matrices satisfying $B_n=(1-1/2^n) I$ and $(C_{n})_{n\geq 0}$ be defined as above. Clearly, each matrix $B_{n}$ is convergent, but $\Vert C_{n}\Vert _{\infty }=\prod _{k=1}^{n}(1-1/2^{k})\nrightarrow 0$ as $n\rightarrow \infty$.

Moreover, even if each $B_{n}$ is itself convergent, it is still possible that the index of contraction is infinite:

Example B.4.

Let $(B_{n})_{n\geq 1}$ be given by

$$\begin{equation*} B_{n}\coloneq \frac{1}{2}\begin{pmatrix} 0 & 1+(-1)^{n}\\ 1-(-1)^{n} & 0 \end{pmatrix}. \end{equation*}$$

Defining $(C_{n})_{n\geq 0}$ as above, we find that

$$\begin{equation*} C_{n}\coloneq \frac{1}{2}\begin{pmatrix} 0 & 0\\ 1-(-1)^{n} & 1+(-1)^{n} \end{pmatrix}\text{ for }n\geq 1. \end{equation*}$$

That is, $\Vert C_{n}\Vert _{\infty }=1$ independent of $n$.

It is not hard to find interesting cases in which $\widehat{\operatorname {con}}(B_{1},B_{2},\ldots )$ is finite.

Example B.5.

Let $(B_{n})_{n\geq 1}$ be a sequence of square substochastic matrices of order $n$ satisfying the following properties:

(i): $B_{1}$ is convergent.
(ii): $\hat{J}(B_{1})=\hat{J}(B_{n})$ and $\operatorname {graph}B_{1}=\operatorname {graph}B_{n}$ for all $n$.

Then, $\widehat{\operatorname {con}}(B_{1},B_{2},\ldots )<n$.

Acknowledgments

The author thanks Edward Cheung (University of Waterloo) for discussions on M-matrices, a careful review of this document, and (more importantly) his unfaltering friendship.