CKV-type $B$-matrices and error bounds for linear complementarity problems

1.   Introduction

Given an $n\times n$ real matrix $A$ and a vector $q\in \mathbb{R}^n$, the linear complementarity problem is to find a vector $x\in \mathbb{R}^{n}$ satisfying

or to show that no such vector $x$ exists. We denote the problem (1.1) and its solution by LCP$(A, q)$ and $x^*$, respectively. The LCP$(A, q)$, as one of the fundamental problems in optimization and mathematical programming, has various applications in the quadratic programming, the optimal stopping, the Nash equilibrium point of a bimatrix game, the network equilibrium problem, the contact problem, and the free boundary problem for journal bearing, for details, see ^[1,2,26].

It is well known that the LCP$(A, q)$ has a unique solution $x^*$ for any $q\in \mathbb{R}^n$ if and only if $A$ is a $P$-matrix ^[2]. Here, a real square matrix $A$ is called a $P$-matrix if all its principal minors are positive. For this case, an important topic in the study of the LCP$(A, q)$ concerns the bound of $||x-x^*||_{\infty}$, since it can be used as termination criteria for iterative algorithms and can be used to measure the sensitivity of the solution of LCP$(A, q)$ in response to a small perturbation, e.g., ^{[18,19,28,34]}. When the matrix $A$ is a $P$-matrix, Chen and Xiang ^[3] gave the following error bound for the LCP$(A, q)$:

where $D = diag(d_i)$ with $0\leq d_i \leq 1$ for each $i\in N: = \{1, \ldots, n\}$, $d = (d_1, d_2, \ldots, d_n)^{T}\in [0, 1]^n$, and $r(x) = \min\{ x, Ax+q\}$ in which the min operator denotes the componentwise minimum of two vectors. Furthermore, to avoid the high-cost computations of the inverse matrix in (1.2), some easily computable bounds for the LCP$(A, q)$ were derived for the different subclass of $P$-matrices, such as, $B$-matrices ^[10,20], doubly $B$-matrices ^[6], $SB$-matrices ^[7,8], $MB$-matrices ^[4], $B$-Nekrasov matrices ^[11,21], weakly chained diagonally dominant $B$-matrices ^[22,32,35], $B_{\pi}^{R}$-matrices ^[12,13,27], and so on ^{[9,14,15,16,17,23,36]}.

Recently, Li et al. ^[24] presented a new subclass of $P$-matrices called Dashnic-Zusmanovich type $B$-matrices (DZ-type-$B$-matrices), and provided an error bound for the LCP$(A, q)$ when $A$ is a DZ-type-$B$-matrix.

Definition 1.1. ^[33] A matrix $A = [a_{ij}]\in \mathbb{C}^{n\times n}$, with $n\geq 2$, is a DZ-type matrix if for each $i\in N$, there exists $j\in N, j\neq i$ such that

where $r_i^j(A) = r_i(A)-|a_{ij}|$ and $r_i(A) = \sum\limits_{j\in N\setminus\{i\}} |a_{ij}|$.

Definition 1.2. ^[24] Let $A = [a_{ij}]\in {\mathbb{C}}^{n\times n}$ be written in the form

where

and $r_i^+: = \max\{0, a_{ij}|j\ne i\}$. Then, $A$ is called a DZ-type-B-matrix if $B^+$ is a DZ-type matrix with all positive diagonal entries.

Theorem 1.1. [24,Theorem 6] Let $A = [a_{ij}]\in {\mathbb{R}}^{n\times n}$ be a DZ-type-$B$-matrix, and $B^+ = [b_{ij}]$ be the matrix of (1.3). Then,

where

and

Very recently, Cvetković et al. ^[5] proposed a new subclass of $H$-matrices called CKV-type matrices, which generalizes CKV matrices (also known as $\Sigma$-SDD matrices in the literature) and DZ-type matrices.

Definition 1.3. ^[5] A matrix $A = [a_{ij}]\in \mathbb{C}^{n\times n}$, with $n\geq 2$, is called a CKV-type matrix if $N_A = \emptyset$ or $S_i^{\star}(A)$ is not empty for all $i\in N_A$, where $N_A: = \{i\in N:|a_{ii}|\leq r_i(A)\}$ and

with $\Sigma(i): = \{S\subsetneq N:i\in S\}$ and $r_i^S(A): = \sum\limits_{j\in S\backslash\{i\}}|a_{ij}|$.

Motivated by the definition of DZ-type-$B$-matrices, two meaningful questions naturally arise: can we get a more general subclass of $P$-matrices using CKV-type matrices, and can we obtain a sharper error bound than the bound (1.4) for the linear complementarity problem of DZ-type-$B$-matrices? To answer these questions, in Section 2, we present a new class of matrices: CKV-type $B$-matrices, and prove that it is a subclass of $P$-matrices containing DZ-type-$B$-matrices and $SB$-matrices. Meanwhile, we give an upper bound for the infinity norm for the inverse of CKV-type $B$-matrices. In Section 3, we give an error bound for the LCP$(A, q)$ when $A$ is a CKV-type $B$-matrix, consequently, for the LCP$(A, q)$ when $A$ is a DZ-type-$B$-matrix, and some comparisons with other results are also discussed. Finally, in Section 4, numerical examples are given to illustrate the corresponding theoretical results.

2.   CKV-type $B$-matrices

Using CKV-type matrices, we first give the definition of CKV-type $B$-matrices.

Definition 2.1. A matrix $A\in \mathbb{R}^{n\times n}$ is called a CKV-type $B$-matrix if $B^{+}$ given by (1.3) is a CKV-type matrix with positive diagonal entries.

To show that a CKV-type $B$-matrix is a $P$-matrix, we recall the following results.

Lemma 2.1. [5,Theorem 6] Every $CKV$-type matrix is a nonsingular $H$-matrix.

Lemma 2.2. [29,Corollary 2.4] If $A$ is a real nonsingular $M$-matrix and $P$ is a nonnegative matrix with rank($P$) = 1, then $A+P$ is a $P$-matrix.

Proposition 2.1. If $A$ is a $CKV$-type $B$-matrix, then $A$ is a $P$-matrix.

Proof. Let $A$ be written in the form $A = B^++C$ as shown in (1.3). It follows from (1.3) and Definition 2.1 that $B^+$ is a $Z$-matrix (all non-diagonal entries are non-positive ^[1]) with positive diagonal entries and $C$ is a nonnegative matrix of rank 1. By Lemma 2.1, we know that $B^+$ is a nonsingular $H$-matrix, and thus the conclusion follows from Lemma 2.2.

As shown in ^[5,33], the relations of strictly diagonally dominant (SDD) matrices, doubly strictly diagonally dominant (DSDD) matrices, $S$-strictly diagonally dominant ($S$-SDD) matrices, DZ-type matrices, and CKV-type matrices are:

● $\{\rm{SDD}\}\subseteq \{\rm{DSDD}\}\subseteq \{\rm{DZ}\}\subseteq \{\rm{S-SDD}\}$ and $\{\rm{SDD}\}\subseteq \{\rm{DZ}$-type$\}$;

● $\{\rm{DSDD}\}\not\subseteq \{\rm{DZ}$-type$\}$ and $\{ \rm{DZ}$-type$\}$ $\not\subseteq$ $\{\rm{DSDD}\}$;

● $\{\rm{DZ}\}\not\subseteq \{\rm{DZ}$-type$\}$ and $\{ \rm{DZ}$-type$\}$ $\not\subseteq$ $\{\rm{DZ}\}$;

● $\{\text{S-SDD}\}$$\subseteq$$\{\rm{CKV}$ -type$\}$ and $\{ \rm{DZ}$-type$\}$ $\subseteq$ $\{$ $\rm{CKV}$-type$\}.$

According to ^[24] and the above relations, we give a figure to illustrate the relations among $B$-matrices, DZ-type-$B$-matrices, $DB$-matrices, $SB$-matrices, CKV-type $B$-matrices. Here, the notions of $B$-matrices, $DB$-matrices, and of $SB$-matrices are listed as follows. Let $A = B^++C\in {\mathbb{R}}^{n\times n}$, where $B^+$ is defined by (1.3). Then, $A$ is called

● a $B$-matrix if $B^+$ is SDD with all positive diagonal entries ^[30];

● a $DB$-matrix if $B^+$ is DSDD with all positive diagonal entries ^[29];

● a $SB$-matrix if $B^+$ is $S$-SDD with all positive diagonal entries for a given non-empty proper subset $S$ of $N$ ^[25].

Next, we give a sufficient and necessary condition for a CKV-type $B$-matrix. Before that, a lemma is needed.

Lemma 2.3. [5,Remark 9] A matrix $A = [a_{ij}]\in \mathbb{C}^{n\times n}$, with $n\geq 2$, is called a CKV-type matrix if $S_i^{\star}(A)$ given by Definition 1.3 is not empty for all $i\in N$. Especially, if $A$ is an SDD matrix, then for all $i\in N$, all proper subsets $S$ containing $i$ belong to $S_i^{\star}(A)$.

Proposition 2.2. Given any diagonal matrix $D = diag(d_1, d_2, \ldots, d_n)$ with $d_i\in [0, 1]$ for all $i\in N$, and let $I$ be the identity matrix, then $A$ is a CKV-type $B$-matrix if and only if $I-D+DA$ is a CKV-type $B$-matrix.

Proof. Sufficiency is clearly established. We next show the necessity. Suppose $A = [a_{ij}]\in \mathbb{R}^{n\times n}$ is a CKV-type $B$-matrix. Then, $A = B^++C$, where $B^+$ is the matrix of (1.3). Let $\overline{A}: = I-D+DA = [\bar{a}_{ij}]$ and $\overline{A}: = I-D+DA = \overline{B}^++\overline{C}$, where

and $\bar{r}_i^+: = \max\{0, \bar{a}_{ij}|j\ne i\}$.

Note that

It follows that

and

Since $A = B^++C$, it holds that

Note that $B^+ = [b_{ij}]$ and $b_{ij} = a_{ij}-r_i^+$. Hence, from (2.1) and (2.2), we easily obtain that

Let $\overline{B}^+ = [\bar{b}_{ij}]$. Then,

Since $A$ is a CKV-type $B$-matrix, then $B^+ = [b_{ij}]$ is a CKV-type matrix with positive diagonal entries. Thus, by Lemma 2.3, it follows that for each $i\in N$, there exists $S\in S_i^\star(B^+)$, which implies that

Hence, for each $i\in N$, it follows from (2.3) that

and that for all $j\in \overline{S}$, if $d_i\neq0$ and $d_j\neq0$, then

and if $d_i = 0$ or $d_j = 0$, then

These mean that $S\in S_i^\star(\overline{B}^+)$ for each $i\in N$. Therefore, from Definition 1.3, $\overline{B}^+$ is a CKV-type matrix with positive diagonal entries, and consequently, $\overline{A} = I-D+DA$ is a CKV-type $B$-matrix from Definition 2.1.

In the following, we give an infinity norm bound for the inverse of CKV-type $B$-matrices. First, two lemmas are listed.

Lemma 2.4. ^[5] Let $A = [a_{ij}]\in {\mathbb{C}}^{n\times n}, {n\geq 2}$, be a CKV-type matrix. Then

where $S_i^{\star}(A)$ is given by Definition 1.3, and

Lemma 2.5. ^[11] Suppose $P = (p_1, \ldots, p_n)^Te$, where $e = (1, \ldots, 1)$ and $p_i\geq 0$ for all $i\in N$, then

Theorem 2.1. Let $A = [a_{ij}]\in {\mathbb{R}}^{n\times n}, {n\geq 2}$, be a CKV-type $B$-matrix, and $B^+ = [b_{ij}]$ be the matrix of (1.3). Then

where $S_i^{\star}(B^+)$ is defined as in Definition 1.3, and

Proof. Since $A$ is a CKV-type $B$-matrix, so $B^+$ is a CKV-type matrix with positive diagonal entries and also a $Z$-matrix. By Corollary 4 of ^[31], we know that $B^+$ is an $M$-matrix and thus $(B^+)^{-1}$ is nonnegative. Hence, from $A = B^++C$ in which $B^+$ and $C$ are given by (1.3), we have

which implies that

Note that $C = (r_1^+, \ldots, r_n^+)^Te$ is nonnegative. Therefore, $(B^+)^{-1}C$ can be written as $(p_1, \ldots, p_n)^Te$, where $p_i\geq 0$ for all $i\in N$. By Lemma 2.5, we get

Since $B^+$ is a CKV-type matrix, it follows from Lemma 2.4 that

Hence, from (2.4), (2.5), and (2.6), the conclusion follows.

3.   Error bounds for the linear complementarity problem

Based on Theorem 2.1, we give in this section an upper bound of $\max\limits_{d\in[0, 1]^n}||(I-D+DA)^{-1}||_\infty$ when $A$ is a CKV-type $B$-matrix, and give some comparisons with other results. Before that, a useful lemma is needed.

Lemma 3.1. [20,Lemma 3] Let $\gamma > 0$ and $\eta\ge 0$. Then for any x $\in [0, 1]$,

and

Theorem 3.1. Let $A = [a_{ij}]\in {\mathbb{R}}^{n\times n}, {n\geq 2}$, be a $CKV$-type $B$-matrix, and $B^+ = [b_{ij}]$ be the matrix of (1.3). Then

where $S_i^{\star}(B^+)$ is defined as in Definition 1.3, and

Proof. Since $A$ is a CKV-type $B$-matrix, by Proposition 2.2, it follows that $I-D+DA$ is also a CKV-type $B$-matrix. Taking into account that $A = B^++C$ in which $B^+$ and $C$ are defined as (1.3), then

Denote $\overline{B}^+: = I-D+DB^+ = [\overline{b}_{ij}]$ and $\overline{C} = DC$. Then, from Theorem 2.1, we have

By Lemma 3.1, it follows that for all $i\in N, j\in \overline{S}$,

Furthermore, by the proof of Proposition 2.2, $S_i^{\star}(B^+)\subseteq S_i^{\star}(\overline{B}^+)$ for each $i\in N$. Thus,

Hence, the conclusion follows from (3.2) and (3.3).

Remark 3.1. Note that, if $b_{ii}-r_i^S(B^+)\le 1$ and $b_{jj}-r_j^{\overline{S}}(B^+)\le 1$, then

If $b_{ii}-r_i^S(B^+) > 1$ and $b_{jj}-r_j^{\overline{S}}(B^+)\le 1$, then

If $b_{ii}-r_i^S(B^+)\le 1$ and $b_{jj}-r_j^{\overline{S}}(B^+) > 1$, then

If $b_{ii}-r_i^S(B^+) > 1$ and $b_{jj}-r_j^{\overline{S}}(B^+) > 1$, then

Since a DZ-type-$B$-matrix is a CKV-type $B$-matrix, the bound (3.1) can also be used to estimate $\max\limits_{d\in[0, 1]^{n}}||(I-D+DA)^{-1}||_\infty$ when $A$ is a DZ-type-$B$-matrix. The following theorem provides that the bound (3.1) is better than the bound (1.4) in Theorem 1.1 (Theorem 6 of ^[24]).

Theorem 3.2. Let $A = [a_{ij}]\in {\mathbb{R}}^{n\times n}$ be a DZ-type-$B$-matrix, and $B^+ = [b_{ij}]$ be the matrix of (1.3). Then (3.1) holds. Furthermore,

where $\gamma_i(B^+)$ and $\zeta_{ij}(B^+)$ are given by Theorem 1.1, $S_i^{\star}(B^+)$ and $\alpha_{ij}^S(B^+)$ are defined in Theorem 3.1.

Proof. For each $i\in N$, note that

and

with $\Sigma(i): = \{S\subsetneq N:i\in S\}$. Take $S = N\setminus\{j\}$, $\overline{S} = \{j\}$, $j\neq i$, then

which leads to

It is easy to see that $j\in \gamma_i(B^+)$ is equivalent to $S = N\setminus\{j\}\in S_i^{\star}(B^+)$. Therefore, for each $i\in N$,

This completes the proof.

Particularly, for $B$-matrices, as an important subclass of CKV-type $B$-matrices, we next show that the bound (3.1) is better than that given by García-Esnaola and Peña in ^[10] in some cases.

Theorem 3.3. [10,Theorem 2.3] Let $A\in {\mathbb{R}}^{n\times n}$ be a $B$-matrix, and $B^+ = [b_{ij}]$ be the matrix of (1.3). Let $\beta_i: = b_{ii}-r_i(B^+)$ and $\beta : = \min\limits_{i\in N}\{\beta_i\}$. Then

Theorem 3.4. Let $A = [a_{ij}]\in {\mathbb{R}}^{n\times n}$ be a $B$-matrix, and $B^+ = [b_{ij}]$ be the matrix of (1.3). Let $\beta_i: = b_{ii}-r_i(B^+)$, $\beta: = \min\limits_{i\in N}\{\beta_i\}$, and $S$ be a nonempty proper subset of $N$. Then (3.1) holds. Furthermore, if $b_{ii}-r_i^S(B^+)\le 1$ for all $i\in N$ and $b_{jj}-r_j^{\overline{S}}(B^+)\le 1$ for all $j\in \overline{S}$, then,

and if $\beta_i > 1$ for each $i\in N$, then

where $\alpha_{ij}^S(B^+)$ is defined as in Theorem 3.1.

Proof. By the fact that a $B$-matrix is a CKV-type $B$-matrix, we know that (3.1) holds directly. We now prove that (3.5) and (3.6) hold. For each $i\in N$, $S\in S_i^{\star}(B^+)$, and $j\in \overline{S}$, if $b_{ii}-r_i^S(B^+)\le 1$ and $b_{jj}-r_j^{\overline{S}}(B^+)\le 1$, then from Remark 3.1 that

If $b_{jj}-r_j(B^+) < b_{ii}-r_i(B^+)$, then

which implies that

i.e.

It follows that

If $b_{jj}-r_j(B^+)\ge b_{ii}-r_i(B^+)$, then

implying that

i.e.

It holds that

Hence, (3.5) follows from (3.7) and (3.8).

If $\beta_i: = b_{ii}-r_i(B^+) > 1$ for each $i\in N$, then

By Remark 3.1, we can see that

Therefore,

The proof is complete.

Remark from Theorem 3.4 that we can take the minimum of bounds (3.1) and (3.4) to estimate the error bound for the LCP$(A, q)$ with $A$ being a $B$-matrix, that is,

4.   Numerical examples

In this section, three examples are given to show the advantage of the bound (3.1) in Theorem 3.1.

Example 4.1. Consider the following matrix

Obviously, $B^+ = A$ and $C = 0$. It is easy to verify that $B^+$ is not a DZ-type matrix and an $S$-SDD matrix, consequently, not a SDD matrix and a DSDD matrix. Hence, $A$ is not a DZ-type-$B$-matrix and an $SB$-matrix, and thus not a $B$-matrix and a $DB$-matrix. So we cannot use the error bounds in ^{[6,7,8,10,20,24]} to estimate $\max\limits_{d\in[0, 1]^4}||(I-D+DA)^{-1}||_\infty$. However, by calculations, one has that $B^+$ is a CKV-type matrix with positive diagonal entries, and thus $A$ is a CKV-type $B$-matrix. So by the bound (3.1) in Theorem 3.1, we get

Example 4.2. Consider the following matrix

Note that $r_i^+: = \max\{0, a_{ij}|j\ne i\} = 0$ for $i = 1, 2, 3, 4$. Hence, $B^+ = A$ and $C = 0$. By calculations, we have that $A$ is a DZ-type-$B$-matrix, and thus it is a CKV-type $B$-matrix. By the bound (3.1) in Theorem 3.1, we have

while by the bound (1.4) in Theorem 1.1, it holds that

Obviously, the bound (3.1) is sharper than bound (1.4) in Theorem 1.1 (Theorem 6 of ^[24]).

Example 4.3. Consider the $B$-matrix

Note that $B^+ = A$, $C = 0$. Then, by the bound (3.4) in Theorem 3.3, we have

In addition, $A$ is also a CKV-type $B$-matrix. By calculations, for $i = 1, 2, 3$, take $S = \{1, 2, 3\}$ and $\overline{S} = \{4\}$, it follows that $b_{ii}-r_i^S(B^+)\le 1$ for all $i\in \{1, 2, 3, 4\}$ and $b_{44}-r_4^{\overline{S}}(B^+)\le 1$; and for $i = 4$, take $S = \{4\}$ and $\overline{S} = \{1, 2, 3\}$, it follows that $b_{ii}-r_i^S(B^+)\le 1$ for all $i\in \{1, 2, 3, 4\}$ and $b_{jj}-r_j^{\overline{S}}(B^+)\le 1$ for all $j\in \overline{S}$, which satisfy the hypothesis of Theorem 3.4. Therefore, by Theorem 3.4, we get

which is smaller than the bound (3.4) in Theorem 3.3 (Theorem 2.3 of ^[10]).

5.   Conclusions

In this paper, on the basis of the class of CKV-type matrices, a new subclass of $P$-matrices: CKV-type $B$-matrices, containing $B$-matrices, $DB$-matrices, $SB$-matrices as well as DZ-type-$B$-matrices, is introduced, and an upper bound for the infinity norm for the inverse of CKV-type $B$-matrices is provided. Then, by this bound, an error bound for the corresponding LCP$(A, q)$ is given. We also proved that the new error bound is sharper than those of ^[10] and ^[24] in some cases, and give numerical examples to show the advantage of our results.

Acknowledgments

The authors sincerely thank the editors and anonymous reviewers for their valuable suggestions and helpful comments, which greatly improved the quality of the paper. This work was supported by National Natural Science Foundation of China (31600299), Young Talent fund of University Association for Science and Technology in Shaanxi, China (20160234), the Natural Science Foundations of Shaanxi province, China (2017JQ3020, 2020JM-622), the Scientific Research Program Funded by Shaanxi Provincial Education Department (18JK0044), and the Key Project of Baoji University of Arts and Sciences (ZK2017021).

Conflict of interest

The authors declare no conflict of interest.