Iterative Method for Linear System with Coefficient Matrix as an $M_\vee$-matrix

Abstract

An $M_\vee$-matrix A has the form $A=sI-B$, with B an eventually nonnegative matrix and $s\ge \rho (B)$, the spectral radius of B. In this paper we study iterative procedures associated with a splitting of A, to solve the linear system $Ax=b$, with the coefficient matrix A an $M_\vee$-matrix. We generalize the concepts of regular and weak regular splitting of a matrix using the notion of eventually nonnegative matrix , and term them as E-regular and weak E-regular splitting, respectively. We obtain necessary and sufficient conditions for the convergence of these types of splittings. We also discuss the convergence of Jacobi and Gauss-Seidel splittings for $M_\vee$-matrices.

1 Introduction

Consider the linear system

$$\begin{aligned} Ax=b \end{aligned}$$

(1)

where $x, b\in \mathbbm {R}^{n}$ and $A\in \mathbbm {R}^{n,n}$, is an invertible matrix. An iterative technique to solve the linear system (1) involves an initial approximation $x_{0}$ to the solution x and determines a sequence $\{x_{k}\}$ that converges to the exact solution x. Most of these methods reduce to the iterative scheme $x^{k+1}=Hx^{k}+c$, with $k\ge 0$, where the matrix H is called an iteration matrix of the system  (1). It is well known that the iterative scheme converges to the exact solution x of (1) if and only if $\rho (H)<1$ for $\rho (H)$ the spectral radius of H.

As it is well known with a splitting $A=M-N$ of A, one may associate an iterative scheme

$$\begin{aligned} x^{k+1}=M^{-1}Nx^{k}+M^{-1}b \end{aligned}$$

(2)

for solving the system (1) (see [2, 15]), and the convergence of such iterative scheme depends on the spectral radius of $M^{-1}N.$ An M-matrix has the form $A=sI-B$ with B a nonnegative matrix and $s\ge \rho (B)$. To solve (1) with the coefficient matrix A an M-matrix , deserves attention due to its occurrence in a wide variety of areas including finite difference method for solving partial differential equations. In [8], the authors considered such system of linear equations with A an M-matrix , and the convergence of iterative scheme (2) was obtained via regular and weak regular splittings of A, concept introduced in  [12, 15].

Initiated by Friedland [7], attempts were made to study generalized nonnegative matrices , called eventually nonnegative matrices (see [3, 4, 6, 9, 10]), and subsequently generalized M-matrices were studied (see [5, 11]). In  [11], the authors introduced $M_\vee$-matrices, which have the form $A=sI-B$, where B is eventually nonnegative and $s\ge \rho (B)$. Thereafter, in [13, 14], researchers studied some combinatorial properties of this class of matrices. One of the reason that motivated researchers to study this class of matrices is due to its occurrence in engineering, biological and economic applications (see [1]).

Elhashash and Szyld in [5], generalized the concept of regular and weak regular splitting based on Perron-Frobenius property and studied the convergence of such splittings for another generalization of M-matrices , known as GM-matrices . In this paper, we are concerned with the system  (1), where the coefficient matrix A is an $M_\vee$-matrix. We generalize regular and weak regular splitting using the notion of eventually nonnegative matrices , to study the convergence of the iterative scheme (2).

The paper proceeds as follows. In Sect. 2, we consider the basic definitions and some preliminary notations. In Sect. 3, we generalize the concept of regular and weak regular splitting and discuss the convergence of the iterative scheme (2), when the coefficient matrix A in (1) is a nonsingular $M_\vee$-matrix. In particular, we concern with the convergence of Jacobi and Gauss-Seidel methods for such type of linear systems . Lastly, in Sect. 4, we consider singular linear systems and derive a necessary and sufficient condition for semi-convergence of the linear system  (1).

2 Notations and Preliminaries:

Let $\mathbbm {R}^{m,n}$ denote the set of all $m\times n$ real matrices. We say a matrix $A\in \mathbbm {R}^{m,n}$ is nonnegative (or positive) if $a_{ij}\ge (\text { or}>)0$, for all i, j, and we denote it by $A\ge 0$ (or $A>0$). For any matrix $A\in \mathbbm {R}^{n,n}$, and for any negative integer k with $0<|k|<n$, $\mathop {\mathrm {tril}}\nolimits (A,k)$ is the lower triangular part of A with $a_{ij}=0$ for $i=j+r,$ $r=0,1,2,\ldots , |k|-1$, and for any positive integer k with $0<k<n$, $\mathop {\mathrm {triu}}\nolimits (A,k)$ is the upper triangular part of A with $a_{ij}=0$ for $j=i+r,~~r=0,1,2,\ldots , k-1$.

The spectral radius of A is denoted by $\rho (A)$, and by $\sigma (A)$, we mean the spectrum of A. Let $\lambda \in \sigma (A)$, then $\mathop {\mathrm {index}}\nolimits _{\lambda }(A)$ defines the size of the largest Jordan block associated with $\lambda$. When A is singular , we simply write $\mathop {\mathrm {index}}\nolimits (A)$ for $\mathop {\mathrm {index}}\nolimits _{0}(A)$.

We begin with some preliminary definitions.

Definition 1

([11]) A matrix B is said to be an eventually nonnegative matrix if there exists a positive integer $k_0$ such that $B^{k}\ge 0$ for all $k\ge k_0$. A matrix A which has the form $A=sI-B$, with eventually non-negative B and $s\ge \rho (B)$, is called an $M_\vee$-matrix.

Definition 2

([9]) A matrix B is said to possess Perron-Frobenius property if there exists a nonnegative vector $y\ne 0$ such that $By=\rho (B)y$. By WPFn, we denote the collection of all matrices $B\in \mathbbm {R}^{n,n}$ such that both B and $B^{T}$ possess Perron-Frobenious property .

Definition 3

([12, 15]) Recall that a splitting of a matrix A is of the form

$$\begin{aligned} A=M-N \end{aligned}$$

(3)

with a nonsingular matrix M. Then the splitting (3) is called

• (i)  a nonnegative splitting if $M^{-1}N\ge 0$.

• (ii)  a regular splitting if $M^{-1}\ge 0$ and $N\ge 0$.

• (iii)   a weak regular splitting if $M^{-1}N\ge 0$ and $M^{-1}\ge 0$.

Lemma 1

([2]) Let $A=M-N\in \mathbbm {R}^{n,n}$ with nonsingular matrices A and M. Then for $H=M^{-1}N$ and $c=M^{-1}b$, the iterative method (2) converges to the solution $A^{-1}b$ of (1) for each $x^{0}$ if and only if $\rho (H)<1$.

The following definition is due to Elhashash and Syzld, which generalized the above definition.

Definition 4

([6]) A splitting $A=M-N$ is called a Perron-Frobenius splitting if $M^{-1}N$ is a nonnilpotent matrix having the Perron-Frobenius property .

3 Splitting of Nonsingular $M_\vee$-matrices

In this section we generalize the concepts of regular and weak regular splitting using the notion of eventually nonnegative matrices and call them as E-regular and weak E-regular splitting, respectively. We study the convergence of such types of splittings for nonsingular A. We also obtain sufficient conditions for the convergence of classical Jacobi and Gauss-Seidel iterative methods , in case the coefficient matrix A of (1) is a nonsingular $M_\vee$-matrix. We now define the new splittings introduced in this paper.

Definition 5

For $A\in \mathbbm {R}^{n,n}$, a splitting of A is defined as $A=M-N$, with nonsingular M. The splitting $A=M-N$ is said to be an E-regular splitting if both $M^{-1}$ and N are nonnilpotent eventually nonnegative matrices .

Definition 6

For $A\in \mathbbm {R}^{n,n}$, a splitting $A=M-N$ is said to be a weak E-regular splitting if both $M^{-1}N$ and $M^{-1}$ are nonnilpotent eventually nonnegative matrices .

We now consider the iterative schemes (2) starting with two different initial approximations and show that their convex combination approximates the exact solution $A^{-1}b$ of (1). We also give a sufficient condition for the existence such initial guess.

Theorem 1

Let $A=M-N$ with nonsingular matrices A and M, and let the iterative matrix $H=M^{-1}N$ be a nonnilpotent eventually nonnegative matrix . Consider the system  (1) and the iterative scheme (2).

• (i) If there exist vectors $x^{0}$ and $y^{0}$ such that $x^{0}\le x^{1}, ~x^{0}\le y^{0},~~ y^{0}\le y^{1}$, where $x^{1}$ and $y^{1}$ are computed from the iterative scheme (2) with initial values $x^{0}$ and $y^{0}$, respectively, then there exists $k_{0}$ such that

  $$\begin{aligned} x^{k_0}\le x^{k_0+1}\le \ldots \le x^k\le \ldots \le A^{-1}b\le \ldots \le y^k\le \ldots \le y^{k_0+1}\le y^{k_0} \end{aligned}$$

  (4)

  and for any scalar $\lambda$

  $$\begin{aligned} A^{-1}b=\lambda \displaystyle \lim _{k\rightarrow \infty } x^k+(1-\lambda )\displaystyle \lim _{k\rightarrow \infty } y^k. \end{aligned}$$

  (5)

• (ii)  If the iterative scheme (2) converges, then the existence of such $x^0$ and $y^0$ is ensured.

Proof

• (i) As H is eventually nonnegative , so there exists a positive integer $k_{0}$ such that $H^k\ge 0$, for all $k\ge k_0$. Equation (2) implies that for any $k\ge k_{0}$ we have

  $\begin{array}{llll} &{} x^k &{} = &{} H^kx^0+H^{k-1}M^{-1}b+H^{k-2}M^{-1}b+\ldots +HM^{-1}b+M^{-1}b\\ \text { and }&{} x^{k+1} &{} = &{} H^kx^1+H^{k-1}M^{-1}b+H^{k-2}M^{-1}b+\ldots +HM^{-1}b+M^{-1}b, \end{array}$

  so that $x^{k+1}-x^{k}=H^{k}(x^1-x^0)\ge 0$. Thus $x^{k+1}\ge x^{k}$,   for all $k\ge k_0$. Similarly it can be checked that for $k\ge k_{0}$,   $y^{k+1}\le y^{k}$ and $x^k\le y^k$. Thus for any k we have

  $$\begin{aligned} x^{k_0}\le x^{k_0+1}\le \ldots \le x^k\le y^k\le \ldots \le y^{k_0+1}\le y^{k_0}, \end{aligned}$$

  so that both sequences $\{x^{k}\}$ and $\{y^{k}\}$ are bounded and so they converge. Hence both the iterative schemes (2) with initial values $x^{0}$ and $y^{0}$ converge to $A^{-1}b$.

• (ii)  Suppose that the iterative scheme (2) converges, say to x. Then it follows that $x=A^{-1}b$ and $\rho (H)<1$. Since H is nonnilpotent eventually nonnegative , there exists $z\ge 0$ such that $Hz=\rho (H) z<z$ (see [3]). If we take $x^{0}= A^{-1}b-z$ and $y^{0}=A^{-1}b+z$, then $y^{0}-x^{0}=2z\ge 0$ and $x^{1}=Hx^{0}+M^{-1}b=HA^{-1}b-\rho (H)z+M^{-1}b$. As $A^{-1}=(I-H)^{-1}M^{-1}$, which implies that $M^{-1}=(I-H)A^{-1}$, so $x^1=A^{-1}b-\rho (H)z\ge A^{-1}b-z=x^0$. Similarly, it can be verified that $y^1\le y^0$.

   $\square$

Our next result contains a necessary and sufficient condition for the convergence of a weak E-regular splitting. We first state a theorem from  [9], used to prove our result.

Theorem 2

([9]) If $\mathrm {(i)}$ $A^{T}\in \mathbbm {R}^{n,n}$ possesses the Perron-Frobenius property and $x\ge 0~(x\ne 0)$ is such that $Ax-\alpha x\le 0$ for a constant $\alpha >0$, or, $\mathrm {(ii)}$ $A\in \mathbbm {R}^{n,n}$ possesses the Perron-Frobenius property and $x\ge 0~(x\ne 0)$ is such that $x^{T}A-\alpha x^{T}\le 0$, for a constant $\alpha >0$, then $\alpha \le \rho (A)$.

Theorem 3

Let $A=sI-B\in \mathbbm {R}^{n,n}$, with B a nonnilpotent eventually nonnegative matrix , be a nonsingular matrix. Then A is an $M_\vee$-matrix if and only if every weak E-regular splitting $A=M-N$ with $M\ge 0$ is convergent.

Proof

Suppose that $\rho =\rho (M^{-1}N)\ge 1$. As $M^{-1}N$ is a nonnilpotent, eventually nonnegative matrix , there exists $x\ge 0~(x\ne 0)$ such that $M^{-1}Nx=\rho x$ which implies that $Nx=\rho Mx\ge Mx$, that is, $Ax\le 0$ or, $sx\le Bx$. Hence by Theorem 2 we have that $s\le \rho (B)$, which is a contradiction. Hence the splitting $A=M-N$ converges.

Conversely let every weak E-regular splitting is convergent. As $A=sI-B$ is a weak E-regular splitting of A, hence $\rho (s^{-1}B)<1$, that is $\rho (B)<s$. Thus A is an $M_{\vee }$-matrix.   $\square$

We now turn to the special splitting of $M_\vee$-matrices, namely Jacobi and Gauss-Seidel splittings and to their convergence.

Corollary 1

Let $A=sI-B$ be an nonsingular $M_\vee$-matrix with positive diagonals. If the Jacobi iterative matrix $J=D^{-1}(L+U)$, with $D=\mathrm {diag}(A)\,\,L=-\mathop {\mathrm {tril}}\nolimits (A,-1),U=\mathop {\mathrm {triu}}\nolimits (A,1)$, is a nonnilpotent eventually nonnegative matrix , then the Jacobi splitting converges.

Similarly, if the Gauss-Seidel iterative matrix $G=(D-L)^{-1}U$ is a nonnilpotent eventually nonnegative matrix and $L\ge 0$, then Gauss-Seidel method for solving the system  (1) converges.

In  [2], the authors established that for nonsingular M-matrices , both Jacobi and SOR(and hence Gauss-Seidel ) splittings converge. But the following example shows that neither Jacobi nor Gauss-Seidel methods may converge for $M_\vee$-matrices, if the associated iterative matrix is not a nonnilpotent eventually nonnegative matrix .

Example 1

Consider the nonsingular $M_\vee$-matrix $A=12.5I-B$, with

$$B=\left[ \begin{array}{rrr} 9.5 &{} 1 &{} 1.5\\ -14.5 &{} 16 &{} 10.5\\ 10.5 &{} -3 &{} 4.5 \end{array}\right] .$$

Consider the Jacobi splitting $A=M-N$, with $M=\mathrm {diag}(A)$ and $N=M-A$. If $J=M^{-1}N$ is the Jacobi iteration matrix, $\rho (J)=2.0454$ and hence the Jacobi splitting of A does not converge.

Again, if we consider the Gauss-Seidel iterative matrix $G=(D-L)^{-1}U$, with $L=-\mathop {\mathrm {tril}}\nolimits (A, -1)$ and $U=-\mathop {\mathrm {triu}}\nolimits (A,1)$, $\rho (G)=4.248$, the Gauss-Seidel splitting of A also diverges.

As both Jacobi and Gauss-Seidel methods converge for M-matrices , and M-matrices have nonnegative diagonals and off-digonals are nonpositive, so one may raise the question whether Jacobi and Gauss-Seidel methods converge for $M_\vee$-matrices if $D\ge 0$ or $-L-U\in WPFn$ or eventually nonnegative matrices . But this is not the case as the following example shows.

Example 2

Consider the $M_\vee$-matrix $A=12I-B$, where

$$B=\left[ \begin{array}{rrr} 9.5 &{} 1 &{} 1.5\\ -14.5 &{} 11.9 &{} 10.5\\ 10.5 &{} -3 &{} 4.5 \end{array} \right] $$

Let $M=\mathrm {diag}(A)$ and $N=-L-U$, where $L=\mathop {\mathrm {tril}}\nolimits (A,-1),~U=\mathop {\mathrm {triu}}\nolimits (A,1)$. Note that $M\ge 0$, and the eigenvalues of N are $~-3.8763,~-1.9381\pm 6.4435 i$. The Jacobi iterative matrix $J=M^{-1}N$ has eigenvalues $-0.4678 \pm 9.9908i$ so that Jacobi method does not converge, because $\rho (J)=10.0018>1$.

Let $M=\mathrm {diag}(A)+L$ and $N=-U$, where $L=\mathop {\mathrm {tril}}\nolimits (A,-1),~U=\mathop {\mathrm {triu}}\nolimits (A,1)$. Note that the Gauss iterative matrix $G=M^{-1}N$ has eigenvalues $0, -65.2610, 0.9010$ so that Jacobi method does not converge, because $\rho (G)=65.2610>1$.

The following example shows that there are some $M_\vee$-matrices for which both Jacobi and Gauss-Seidel methods converge, whereas the corresponding iterative matrices are not eventually nonnegative matrices.

Example 3

Consider the $M_\vee$-matrix $A=3I-B$ with

$$B=\left[ \begin{array}{rrrr} 0 &{} 1 &{} 1 &{} -1\\ 1 &{} 0 &{} 1 &{} 1\\ 0 &{} 0 &{} 1 &{} 1\\ 0 &{} 0 &{} 1 &{} 1 \end{array}\right] $$

Consider the Jacobi splitting $A=M-N$, with $M=\mathrm {diag}(A)$ and $N=M-A$. If $J=M^{-1}N$ is the Jacobi iteration matrix , $\rho (J)=0.5<1$ and hence Jacobi splitting of A converges. But note that the matrix

$$J=\left[ \begin{array}{rrrr} 0 &{} \frac{1}{3} &{} \frac{1}{3} &{} -\frac{1}{3} \\ \frac{1}{3} &{} 0 &{}\frac{1}{3} &{} \frac{1}{3}\\ 0 &{} 0 &{} 0 &{} 0.5 \\ 0 &{} 0 &{} 0.5 &{} 0 \end{array}\right] $$

is not an eventually nonnegative matrix .

Again if we consider the Gauss-Seidel iterative matrix $G=(D-L)^{-1}U$, with $L=-\mathop {\mathrm {tril}}\nolimits (A, -1)$ and $U=-\mathop {\mathrm {triu}}\nolimits (A,1)$, $\rho (G)=0.8431$, the Gauss-Seidel splitting of A also converges, whereas the matrix

$$G=\left[ \begin{array}{rrrr} 0 &{} 0.3333 &{} 0.3333 &{} -0.3333 \\ 0.6667 &{} -0.1111 &{} 0.2222 &{} 0.4444\\ 0 &{} 0 &{} 0 &{} 0.5 \\ 0 &{} 0 &{} 1 &{} -0.25 \end{array}\right] $$

is not an eventually nonnegative matrix .

Remark 1

Jacobi splitting of the matrix A in Example 3 is not an E-regular splitting , but the splitting converges. Like with Theorem 3, it is not possible to characterize nonsingular $M_\vee$-matrices in terms of convergence of E-regular splittings .

The following theorem gives a sufficient condition for a matrix $A=sI-B$ with B an eventually nonnegative matrix to be an $M_\vee$-matrix and for the convergence of the Jacobi method for A. But the condition is not necessary. An example has been considered to illustrate the fact.

Lemma 2

If $M\in \mathbbm {R}^n$ and $D=\mathrm {diag}(d_i)$, is an nonsingular diagonal matrix, then $\min \limits _{i}|d_{i}|\cdot \rho (M)\le \rho (DM)\le \max \limits _{i}|d_{i}|\cdot \rho (M)$.

Proof

Let y be a nonzero vector such that $y^{T}DM=\lambda y^{T}$, where $|\lambda |=\rho (DM)$. Let x be a nonzero vector such that $Mx=\rho x$, where $|\rho | =\rho (M)$. Then $DMx=\rho Dx$ implies that $\lambda y^{T}x= \rho y^{T}Dx$. But,

$$|\rho |\cdot \min \limits _{i}|d_{i}|\cdot |y^{T}x|\le |\rho |\cdot | y^{T}Dx|\le |\rho |\cdot \max \limits _{i}|d_i|\cdot |y^{T}x|.$$

Hence $|\rho |\cdot \min \limits _{i}|d_{i}|\cdot |y^{T}x|\le |\lambda |\cdot |y^{T}x|\le |\rho |\cdot \max \limits _{i}|d_i|\cdot |y^{T}x|$ Thus, if $y^{T}x\ne 0$,

$$\begin{aligned} \rho (M)\cdot \min \limits _{i}|d_{i}|\le \rho (DM)\le \rho (M)\cdot \max \limits _{i}|d_{i}|. \end{aligned}$$

(6)

If $y^{T}x=0$, we consider a small perturbation of the matrices M and D such that the corresponding eigenvectors $\tilde{x}$ and $\tilde{y}$ of M and DM, respectively, satisfy $\tilde{y}^{T}\tilde{x}\ne 0$. Equation (6) holds for the new matrices and as the eigenvalues are continuous functions on the matrix entries, so  (6) is true for the given M and DM.   $\square$

Theorem 4

Let $A=sI-B=D+L+U$, where $D=\mathrm {diag}(A),~L=\mathop {\mathrm {tril}}\nolimits (A,-1)$ and $U=\mathop {\mathrm {triu}}\nolimits (A,1)$, and let B be an eventually nonnegative matrix . If $(-L-U)\in WPFn$ and $\rho (L+U)<\min \limits _{i}|a_{ii}|$, then A is a nonsingular $M_\vee$-matrix and the Jacobi splitting of A converges.

Proof

If A is an $M_\vee$-matrix and $\rho (L+U)<\min \limits _{i}|a_{ii}|$, then from the righthand side inequality of Lemma 2, $\rho (-D^{-1}(L+U))\le \frac{\rho (L+U)}{\min \limits _{i}|a_{ii}|}<1$, and hence the Jacobi splitting converges.

Let $\min \limits _{i}|a_{ii}|=d$, and let $\lambda =\rho (L+U)$. As $(-L-U)\in WPFn$ and B is an eventually nonnegative matrix , we choose nonnegative vectors x, y such that $(L+U)x=-\lambda x$ and $y^TA=\lambda _{n}y^{T}$, where $\lambda _{n}=s-\rho (B)$. Now, $y^{T}Ax=y^{T}(D-\lambda I)x\ge (d-\lambda )y^{T}x$. Therefore $\lambda _{n}\ge (d-\lambda )$, if $y^{T}x\ne 0$. Otherwise, the statement is also true considering perturbed matrices and using the continuity of spectral radius on the entries of the matrix, as discussed in Lemma 2. Thus, in any case $\lambda _{n}\ge (d-\lambda )>0$, and hence $s>B$, so that A is a nonsingular $M_\vee$-matrix.    $\square$

Example 4

Consider the $M_\vee$-matrix $A=3I-B$ with

$$B=\left[ \begin{array}{rrrr} 0 &{} 0 &{} 1 &{} 1\\ 0 &{} 0 &{} 1 &{} 1\\ 1 &{} 1 &{} 1 &{} 1\\ -1 &{} -1 &{} 1 &{} 1 \end{array}\right] $$

Consider the Jacobi splitting $A=M-N$, with $M=\mathrm {diag}(A)$ and $N=M-A$. If $J=M^{-1}N$ is the Jacobi iteration matrix , $\rho (J)=0.5<1$ and hence Jacobi splitting of A converges. But note that the matrix $N=-L-U\notin WPFn$.

4 Splitting of Singular $M_\vee$-matrices

In this section we consider singular $M_\vee$-matrices and characterize an interesting subclass of these matrices A with $\mathop {\mathrm {index}}\nolimits (A)\le 1$, with the convergence of weak E-regular splitting of A and with eventually monotone property.

Definition 7

([2]) A matrix $A\in \mathbbm {R}^{n,n}$ is said to be semiconvergent if $\displaystyle \lim _{j\rightarrow \infty }A^{j}$ exists.

Theorem 5

([2]) Let $A\in \mathbbm {R}^{n,n}$. Then A is semiconvergent if and only if each of the following conditions hold.

• (i)   $\rho (A)\le 1$.

• (ii)  if $\rho (A)=1$, then $\mathop {\mathrm {index}}\nolimits _{1}(A)=1$.

• (iii)   if $\rho (A)=1$, then $\lambda \in \sigma (A)$ with $|\lambda |=1$, implies that $\lambda =1$.

Definition 8

Let $A\in \mathbbm {R}^{n,n}$ and $S\subseteq \mathbbm {R}^{n}$. Then we say that A is eventually monotone on S,  if there exists a positive integer $k_{0},$ such that for any $x\in S,~~A^{k}x\ge 0$, for all $k\ge k_{0}$, implies $x\ge 0$.

Theorem 6

Let $A=\rho I-B$ be a singular $M_\vee$-matrix where $\rho (B)=\rho$, B is an irreducible, nonnilpotent, eventually nonnegative matrix with $\mathop {\mathrm {index}}\nolimits (B)\le 1$. Then A is an $M_\vee$-matrix with $\mathop {\mathrm {index}}\nolimits (A)\le 1$ if and only if every weak E-regular splitting $A=M-N$ with $M^{-1}$ eventually monotone on $\mathop {\mathrm {range}}\nolimits (M)$ is semiconvergent.

Proof

Suppose that every weak E-regular splitting is semiconvergent. Note that $A=sI-B$ is an weak E-regular splitting of A and hence by the assumption $\rho (s^{-1}B)\le 1$ so that A is an $M_\vee$-matrix. If $\rho (B)<s$, then A is nonsingular and hence $\mathop {\mathrm {index}}\nolimits (A)<1$. As the splitting $A=sI-B$ is semiconvergent, so Theorem 5 implies that $\mathop {\mathrm {index}}\nolimits (A)=1$.

Conversely, suppose that A is an $M_\vee$-matrix with $\mathop {\mathrm {index}}\nolimits (A)\le 1$ and choose $k_{0}>0$ such that for all $k\ge k_{0}$,   $(M^{-1}N)^{k}\ge 0$, $M^{-k}\ge 0$. For $k\ge k_{0}$, consider the series $\displaystyle \sum _{i=0}^{\infty }(M^{-1}N)^{i}M^{-(k+1)}x$, where $x\ge 0$ and $x\in \mathop {\mathrm {range}}\nolimits (M^{k}A)$.

Let $S_{p}=\displaystyle \sum _{i=0}^{p-1}(M^{-1}N)^{i}M^{-(k+1)}$. Note that $\{S_{p}x\}$ is a monotonic increasing sequence . If we set $x=M^{k}Az$ and $z\ge 0$, then

$$ S_{p}x=\displaystyle \sum _{i=0}^{p-1}(M^{-1}N)^{i}M^{-(k+1)}x=\displaystyle \sum _{i=0}^{p-1}(M^{-1}N)^{i}M^{-1}Az= z-(M^{-1}N)^{p}z$$

so that for a large value of p, $S_{p}x\le z$. Thus the sequence $\{S_{p}x\}$ converges, and hence the series $\displaystyle \sum _{i=0}^{\infty }(M^{-1}N)^{i}M^{-(k+1)}x$ converges.

Assume that $\rho =\rho (M^{-1}N)$ and let $\rho >1$. Let z be a nonzero nonnegative vector such that $M^{-1}Nz=\rho z$, so that $z=\left( \frac{1}{1-\rho }\right) M^{-1}Az$. Now, if we set $\alpha =\left( \frac{1}{1-\rho }\right)$, then

$$\displaystyle \sum _{i=0}^{\infty }(M^{-1}N)^{i}z= \alpha \sum _{i=0}^{\infty }(M^{-1}N)^{i}M^{-(k+1)} M^{k}Az=\sum _{i=0}^{\infty }(M^{-1}N)^{i}M^{-(k+1)}x,$$

where $x=\left( \frac{1}{1-\rho }\right) M^{k}Az\in \mathop {\mathrm {range}}\nolimits (M^{k})$ for large k, which implies that $M^{-k}x=\left( \frac{1}{1-\rho }\right) Az=Mz$ so that $M^{-(k+1)}x\ge 0,$ for sufficiently large k. As $M^{-1}$ is eventually monotone on $\mathop {\mathrm {range}}\nolimits (M)=\displaystyle \bigcap _{k=1}^{\infty }\mathop {\mathrm {range}}\nolimits (M^{k})$, then $x\ge 0.$ Hence the series $\displaystyle \sum _{i=0}^{\infty }(M^{-1}N)^{i}z$ converges, which contradicts the fact that $\rho >1$. Hence we have $\rho \le 1.$

If $\rho <1$, the Drazin inverse $(I-M^{-1}N)^{\#}=(I-M^{-1}N)^{-1}$ exists. Let $\rho =1$ so that $M^{-1}A=I-M^{-1}N$ is an $M_\vee$-matrix. As $\mathop {\mathrm {index}}\nolimits (A)<1$ and M is nonsingular , $\mathop {\mathrm {index}}\nolimits (M^{-1}A)<1$ and hence $(I-M^{-1}N)^{\#}$ exists.    $\square$

The following example shows that the condition $\mathop {\mathrm {index}}\nolimits (B)\le 1$ in Theorem 6 can not be relaxed.

Example 5

Consider an $M_\vee$-matrix $A=2I-B$, with

$$B=\left[ \begin{array}{rrll} 0 &{} 0 &{} 1 &{} 1 \\ 0 &{} 0 &{} 1 &{} 1 \\ 1 &{} 1 &{} 1 &{} 1 \\ -1 &{} -1 &{} 1 &{} 1 \end{array}\right] $$

Consider the splitting $A=M-N$ of A, where

$$M=\mathrm {tril}(A)=\left[ \begin{array}{rrrr} 2 &{} 0 &{} 0 &{} 0\\ 0 &{} 2 &{} 0 &{} 0 \\ -1 &{} -1 &{} 1 &{} 0 \\ 1 &{} 1 &{} -1 &{} 1 \end{array}\right] {\text { and } N=M-A.}$$

As $M^{-1}=\left[ \begin{array}{rrll} \frac{1}{2} &{} 0 &{} 0 &{} 0 \\ 0 &{} \frac{1}{2} &{} 0 &{} 0\\ \frac{1}{2} &{} \frac{1}{2} &{} 1 &{} 0 \\ 0 &{} 0 &{} 1 &{} 1 \end{array}\right]$ and $M^{-1}N=\left[ \begin{array}{rrll} 0 &{} 0 &{} \frac{1}{2} &{} \frac{1}{2} \\ 0 &{} \frac{1}{2} &{} \frac{1}{2} &{} 0\\ 0 &{} 0 &{} 1 &{} 2 \\ 0 &{} 0 &{} 0 &{} 1 \end{array}\right]$ are both nonnegative matrices , the splitting $A=M-N$ is a weak E-regular splitting of A. But $\mathop {\mathrm {index}}\nolimits (I-M^{-1}N)=2>1$, and hence $(I-M^{-1}N)^{\#}$ does not exist, which implies that the E-regular splitting $A=M-N$ is not semiconvergent. Note that $\mathop {\mathrm {index}}\nolimits (A)=1$ and $\mathop {\mathrm {index}}\nolimits (B)=2>1$ and thus the condition $\mathop {\mathrm {index}}\nolimits (B)<1$ in Theorem 6 cannot be relaxed.

5 Conclusion

In this article, we considered splittings of $M_\vee$-matrices. We introduced two types of splittings of a matrix, named as E-regular and weak E-regular splittings. We characterized an important subclass of $M_\vee$-matrices in terms of convergence of weak E-regular splittings . We also discussed necessary conditions for the convergence of Jacobi and Gauss-Seidel methods for $M_\vee$-matrices, and examples are considered to illustrate that the conditions are not sufficient.

Theorems 6 and 3, respectively, characterize an important subclass of singular and nonsingular $M_\vee$-matrices in terms of weak E-regular splittings . As E-regular splittings generalize regular splittings using the notion of eventually nonnegative matrices , and M-matrices are characterized using regular splittings (see [8]), an interesting open problem in this context is to discuss the convergence of E-regular splittings , in particular to develop necessary and sufficient conditions for their convergence, or for the convergence of Jacobi and Gauss-Seidel splittings.

As in the entire work we use the Perron-Frobenius property of the matrix B, where $A=sI-B$, the results obtained in the paper are also true for GM-matrices which have the form $A=sI-B$, where $s\ge \rho (B)$ and $B\in WPFn$.