Note on error bounds for linear complementarity problems involving $B^S$-matrices

1.   Introduction

The linear complementarity problem $(LCP)$ is to find a vector $x\in R^{n}$ such that

or to show that no such vector $x$ exists, where $M = (m_{ij})\in R^{n\times n}$ and $z\in R^{n}$. Many problems such as the contact problem, Nash equilibrium point of a bimatrix game, and the free boundary problem for journal bearing can be posed in the framework of the $LCP$, see ^[1,2,3].

It is well known that the $LCP$ has a unique solution for any $z\in R^{n}$ if and only if $M$ is a $P$-matrix ^[2]. Here, a matrix $M\in R^{n\times n}$ is called a $P$-matrix if all its principal minors are positive ^[4]. In 2006, Chen et al. ^[5] gave the following result for the $LCP$ when $M$ is a $P$-matrix:

where $x^{*}$ is the solution of the $LCP$, $r(x) = min\{x, Mx+z\}$, $D = diag(d_i)$ with $0\leq d_i\leq 1$, and the min operator $r(x)$ denotes the componentwise minimum of two vectors. When the matrix $M$ for the $LCP$ belongs to $P$-matrices or some subclass of $P$-matrices, various bounds for $\max\limits_{d\in [0, 1]^{n}} \| (I-D+DM)^{-1}\|_{\infty}$ are established ^{[6,7,8,9,10,11,12,13,14]}.

In 2012, García-Esnaola et al. ^[9] gave upper bounds for $\max\limits_{d\in [0, 1]^{n}} \| (I-D+DM)^{-1}\|_{\infty}$ when $M$ is a $B^S$-matrix as a subclass of $P$-matrices. Here a matrix $M = (m_{ij})\in R^{n\times n}$ is called a $B^S$-matrix ^[15] if there exists a subset $S$ of the set $N = \{1, 2, \ldots, n\}$, with $2 \leq card(S)\leq n-2$, such that for all $i, j \in N$, $t\in T(i)\setminus \{i\}$, and $k \in K(j)\setminus \{j\}$,

where $R^{S}_{i} = \frac{1}{n} \sum\limits_{k\in S} m_{ik}$, $T(i) = \{t\in S|m_{it} > R^{S}_{i} \}$ and $K(j) = \{k\in \overline{S}|m_{jk} > R^{\overline{S}}_{j} \}$ with $\overline{S} = N\setminus \{S\}$.

A square real matrix $M = (m_{ik})_{1\leq i, k\leq n}$ with positive row sums is a $B$-matrix ^[4] if all of its off-diagonal elements are bounded above by the corresponding row means, i.e., for all $i = 1, \ldots, n$,

Let $M = (m_{ij})\in R^{n\times n}$ be a $B^S$-matrix, and let $X = diag(x_1, \cdots, x_n)$ with

such that $\tilde{M} = MX$ is a $B$-matrix with the form $\tilde{M} = \tilde{B}^{+}+\tilde{C}$, where

and $\tilde{r}_i^{+} = \max\{0, m_{ij}x_j| j\neq i\}$. Then

where $\tilde{\beta}_i = \tilde{b}_{ii}-\sum\limits_{j\neq i} |\tilde{b}_{ij}|$, $\tilde{\beta} = \min\limits_{i\in N}\{\tilde{\beta}_i\}$, and

assuming that if $K(j)\setminus \{j\} = \emptyset(T(i)\setminus \{i\} = \emptyset)$, then max (min) is set to be $-\infty(\infty)$ ^[9].

In 2018, Gao ^[14] presented a new bound: Let $M = (m_{ij})\in R^{n\times n}$ be a $B^S$-matrix. Then

where $\hat{\beta}_i = \tilde{b}_{ii}-\sum\limits_{j = i+1}^{n} |\tilde{b}_{ij}|l_i(\tilde{B}^{+})$, $l_k(\tilde{B}^{+}) = \max\limits_{k\leq i\leq n}\left\{ \frac{1}{|\tilde{b}_{ii}|} \sum\limits_{j = k, \neq i}^{n} |\tilde{b}_{ij}| \right\}$, and

In order to improving the above results, in this paper, we establish some new upper bounds for the condition constant $\max\limits_{d\in [0, 1]^{n}} \| (I-D+DM)^{-1}\|_{\infty}$ when $M$ is a $B^S$-matrix.

Next, we recall the following definition and lemmas for an $n \times n$ matrix.

Definition 1. ^[13] A matrix $M = (m_{ij})\in C^{n\times n}$ is called a row strictly diagonally dominant matrix if for each $i\in N$, $|m_{ii}| > \sum\limits_{j = 1, \neq i}^{n} |m_{ij}|$. A matrix $M = (m_{ij})$ is called a $Z$-matrix if $m_{ij}\leq 0$ for any $i\neq j$, and an $M$-matrix if $M$ is a $Z$-matrix with $M^{-1}$ being nonnegative.

Lemma 1. ^[9] Let $M = (m_{ij})\in R^{n\times n}$ be a $B^S$-matrix. Then there exists a positive diagonal matrix $X = diag(x_1, \cdots, x_n)$ with

such that $\tilde{M} = MX$ is a $B$-matrix, where $\gamma > 0$,

and max (min) is set to be $-\infty(\infty)$ if $K(j)\setminus \{j\} = \emptyset(T(i)\setminus \{i\} = \emptyset)$.

Remark 1. From the definitions of $B$-matrix and $B^{S}$-matrix, if $M$ is a $B^S$-matrix such that $T(i) = \{i\}$ for all $i\in S$ and $K(j) = \{j\}$ for all $j\in \overline{S}$, then $M$ is a $B$-matrix. Moreover, each $3\times 3$ $B$-matrix is not a $B^{S}$-matrix and there exists a $B^{S}$-matrix that is not a $B$-matrix ^[9]. Thus the notions of $B$-matrix and $B^S$-matrix are only related in the sense of Lemma $1$.

Lemma 2. ^[9] Let $M = (m_{ij})\in R^{n\times n}$ be a $B^S$-matrix and let $X$ be the diagonal matrix in Lemma $1$ such that $\tilde{M} = MX$ is a $B$-matrix with the form $\tilde{M} = \tilde{B}^{+}+\tilde{C},$ where $\tilde{B}^{+} = (\tilde{b}_{ij})$ is the matrix in $(1.1)$. Then $\tilde{B}^{+}$ is strict diagonal dominant by rows with positive diagonal entries.

Lemma 3. ^[9] If $M = (m_{ij})\in R^{n\times n}$ is a $B^{S}$-matrix that is not a $B$-matrix, then there exist $k, i\in N$ with $k\neq i$ such that

Furthermore, if $k\in S$ (resp., $k\in \overline{S})$, then $\gamma < 1$ (resp., $\gamma > 1$), where $\gamma$ is the parameter $\gamma$ satisfying $(1.4)$.

Some notations are given, which will be used in the sequel. Let $A = (a_{ij})\in R^{n\times n}$. For $i, j, k \in N$, $i\neq j$, denote

Lemma 4. ^[16] Let $A = (a_{ij})\in R^{n\times n}$ be a row strictly diagonally dominant $M$-matrix. Then

where

Lemma 5. ^[13] Let $\gamma > 0$ and $\eta \geq 0$. Then for any $x\in [0, 1]$,

Lemma 6. ^[12] Let $A = (a_{ij})\in R^{n\times n}$ with

Then for any $x_i\in [0, 1]$, $i\in N$,

The rest of this paper is organized as follows: In Section 2, we present some new bounds for $\max\limits_{d\in [0, 1]^{n}} \| (I-D+DM)^{-1}\|_{\infty}$ when $M$ is a $B^S$-matrix, and new perturbation bounds of $B^S$-matrices linear complementarity problems are also considered. In Section 3, a numerical example is given to show that our proposed bounds are respectively better than those in ^[6,11] in some cases.

2.   Error bounds for LCPs of $B^S$-matrices

In this section, we propose some new error bounds for linear complementarity problems involved with $B^S$-matrices.

Theorem 1. Let $M = (m_{ij})\in R^{n\times n}$ be a $B^S$-matrix and let $X$ be the diagonal matrix given by Lemma $1$ such that $\tilde{M} = MX$ is a $B$-matrix with the form $\tilde{M} = \tilde{B}^{+}+\tilde{C},$ where $\tilde{B}^{+} = (\tilde{b}_{ij})$ is the matrix in $(1.1)$. Then

where $\bar{\beta}_i = \tilde{b}_{ii}-\sum\limits_{j = i+1}^{n} |\tilde{b}_{ij}| w_i(\tilde{B}^{+})$, and

Proof. Let $\tilde{M}_D = X-DX+D\tilde{M}$. From Lemma $1$, we deduce that

where $\tilde{B}_D^{+} = X-DX+D\tilde{B}^{+}$, $\tilde{C}_D = D\tilde{C}$. By Lemma $2$, $\tilde{B}^{+}$ is a strictly diagonal dominant matrix. Let $M_D = I-D+DM$. Note that $M = \tilde{M }X^{-1}$. Then, similarly to the proof of Theorem $2.2$ in ^[8], we can obtain that $\tilde{B}_D^{+}$ is a strictly diagonally dominant $M$-matrix with positive diagonal elements and that

Next, by Lemma $4$, we have

From Lemma $5$, we can easily get the following results: For each $i, j, k\in N$,

and

Furthermore, by Lemma $5$ and Lemma $6$, we have

and

Finally, by $(2.3)$–$(2.5)$, we obtain

Therefore, the result in $(2.1)$ holds from $(2.2)$ and $(2.6)$.

Based on Theorem $1$ and Lemma $3$, the following Corollary can be proved easily.

Corollary 1. Let $M = (m_{ij})\in R^{n\times n}$ be a $B^S$-matrix that is not a $B$-matrix and let $k_0, i_0\in N$ with $k_0\neq i_0$ such that $m_{i_0k_0}\geq \frac{1}{n} \sum\limits_{j\in N} m_{i_0j}$. If $k_0\in \overline{S}$, then

If $k_0\in S$, then

Similarly to the proof of Theorem $2.4$ in ^[6], we can also obtain new perturbation bounds for linear complementarity problems of $B^S$-matrices based on Theorem $1$.

Theorem 2. Let $M = (m_{ij})\in R^{n\times n}$ be a $B^S$-matrix and let $\tilde{B}^{+} = (\tilde{b}_{ij})$ be the matrix in $(1.1)$. Then

where $\beta_{\infty}(M) = \max\limits_{d\in [0, 1]^{n}} \| (I-D+DM)^{-1}D\|_{\infty}$, $D = diag(d_i)$ with $0\leq d_i \leq 1$ for each $i \in N$, and

Finally, we give a comparison of the bounds in $(1.3)$ and $(2.1)$ as follows.

Theorem 3. Let $M = (m_{ij})\in R^{n\times n}$ be a $B^S$-matrix and let $X$ be the diagonal matrix given by Lemma $1$ such that $\tilde{M} = MX$ is a $B$-matrix with the form $\tilde{M} = \tilde{B}^{+}+\tilde{C},$ where $\tilde{B}^{+} = (\tilde{b}_{ij})$ is the matrix in $(1.1)$. Let $\hat{\beta}_i$ and $\bar{\beta}_i$ be defined as in $(1.3)$ and $(2.1)$, respectively. Then

Proof. For any $i\in N$, based on $\tilde{B}^{+}$ is strict diagonal dominant, we have

and by (2.8), we get

Furthermore, by (2.9), for all $i\in N$, we have

and for each $j = 1, 2, \ldots, n-1$,

The result in (2.7) follows by $(2.10)$ and $(2.11)$.

3.   A numerical example

In this section, we give a numerical example to illustrate the advantages of new bound.

Example 1. Consider the family of $B^S$-matrices for $S = \{1, 2\}$ in ^[14]:

where $k\geq 1$. We choose $X = diag\{ \gamma, \gamma, 1, 1\}$ with $\gamma \in (\frac{3.5}{3}, 1.5)$. So $\tilde{M}_k = M_kX$ can be written $\tilde{M} = \tilde{B}^{+}_k+\tilde{C}_k$ as in (1.1), where

In fact, the bound $(1.2)$, with the hypotheses that $k\geq 1$, is

and it can be arbitrarily large when $k\rightarrow +\infty$.

In particular, let $\gamma = 1.3$, then we can use the bound $(1.2)$, the bound $(1.3)$ and the bound $(2.1)$ for $k = 2, 20, 30, 60,100 \ldots, +\infty$ to estimate $\max\limits_{d\in [0, 1]^{n}} \| (I-D+DM)^{-1}\|_{\infty}$, see Table 1.

Remark 2. From Example 1, it is easy to see that each bound $(1.2)$ or $(2.1)$ is better than the other one. Thus it is difficult to say in advance which one is better. However, for a $B^S$-matrix $M$ with $\tilde{M} = \tilde{B}^{+}+\tilde{C}$, where the diagonal dominance of $\tilde{B}^{+}$ is weak (e.g., for a matrix $M_k$ with a large number of $k$ here), the bound $(2.1)$ is more effective than the bound $(1.2)$.

4.   Conclusions

We present a new error bound for linear complementarity problems associated with $B^S$-matrices, which improves some existing results. A numerical example shows the feasibility and effectiveness of the results which are obtained in this paper. Besides $B^S$-matrices, some similar assertions for linear complementarity problems of other classes of matrices are provided, such as $DB$-matrices, $SB$-matrices and $MB$-matrices. So we conjecture here that by the technique above, new sharper bounds for linear complementarity problems of these classes of matrices could be given.

Acknowledgments

This work was supported by the Foundation of Science and Technology Department of Guizhou Province (20191161, 20181079) and the Research Foundation of Guizhou Minzu University (2019YB08).

Conflict of interest

The author declare that they have no competing interests.