Global error bounds for the extended vertical LCP of $\sum-SDD$ matrices

1.   Introduction and Preliminaries

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

or prove that there is no such vector, where the min operater works componentwise for both vectors and matrices. Here, it is abbreviated by EVLCP(A, q), where

is a block matrix and

is a block vector.

When $k = 1, A_{0} = I, q_{0} = 0$, the EVLCP(A, q) reduces to linear Complementarity problems (denoted by LCP ($A_{1}, q_{1}$), and when $A_{0} = I, q_{0} = 0$, the EVLCP(A, q) comes back to vertical linear complementarity problems (can be found in ^[2,3]).The results proposed by Gohda and Sznajder (can be found in ^[4,5,6]) for the extended vertical linear complementarity problem.

Some experts and scholars have extended the theories of existence, uniqueness, and error bound of the linear complementarity problem to the extended vertical linear complementarity problem. For example, for any vector $q$, in the LCP (A, q) has unique solutions if and only if matrix A is the $P$-matrix (can be found in ^[7,8]). Gowda and Sznajder extended this to the extended vertical linear complementarity to be replaced by problem ^[2] in 1994, which became the theoretical basis for the later study of the extended vertical linear complementarity problem.

In ^[9,10,11,12], the algorithms for solving the extended vertical linear complementarity problem are proposed, but the solutions obtained by using these algorithms often have errors; thus, the error estimation of the extended vertical linear complementarity problem is worth studying.

Next, let us review some relevant symbols, concepts, theorems, and lemmas.

When the $B = \left(b_{ij}\right) \in R^{n \times n}$ matrix satisfies $b_{i j} \leq 0$, for any $i \neq j$, B is called $Z$-matrices; if the principal and sub equations of B are all positive, then B is a $P$-matrix; if B is a $Z$-matrix and $B^{-1} > 0$, then B is an $M$-matrix; if $\tilde{B} = (\tilde{b}_{ij})$ and if the comparison matrix of B is an $M$-matrix, when $i = j, \tilde{b} _{ij} = \left | b_{ij} \right |$, when $i\neq j, \tilde{b}_{ij} = -\left | b_{ij}\right |$, then B is an $H$-matrix (can be found in ^[12]).

Definition 1.1. ^[13]   B matrix is $B = \left(b_{ij}\right) \in R^{n \times n}$, if for any $i, j\in N, \left|b_{ii}\right| > r_{i}(B)$, is called a strictly diagonally dominant ($SDD$) matrix.

Definition 1.2. ^[1]   If for any $i\in N$,

where $\left(A_{j}^{\prime}\right)_{i_{.}}$ represents the i-th row of matrix $\left(A_{j}^{\prime}\right)$, then the block matrix $A^{\prime} = \left(A_{0}^{\prime}, A_{1}^{\prime}, \cdots, A_{k}^{\prime}\right)$ is called row rearrangement. Similarly, block vectors $q$ and $q^{\prime}$ also satisfy the above relationship, respectively and here use $\Re(M)$ and $\Re(q)$ to represent the set of rearranged rows of $A$ and $q$.

Theorem 1.1. ^[13]   For any block vector $q = \left(q_{0}, q_{1}, \cdots, q_{k}\right)$, the EVLCP(A, q) has a unique solution if and only if the block matrix $A = \left(A_{0}, A_{1}, \cdots, A_{k}\right)$ has the row W-property, i.e.,

where, the max and min operators work componentwise for both matrices and vectors, 0 represents a zero vector.

In 2009, Zhang et al. (can be found in ^[1]) applied the property of row rearrangement in block matrices to provid necessary and sufficient conditions for block matrices to have the row properties. The specific expression is as follows:

Lemma 1.1. ^[1]   The block matrix $A = \left(A_{0}, A_{1}, \cdots, A_{k}\right)$ has the row W-property if and only if $(I-D) A_{j}^{\prime}+D A_{l}^{\prime}$ is nonsingular for any two blocks $A_{j}^{\prime}, A_{l}^{\prime}$ of $A^{\prime}\in \Re(A)$ and for any $D = \operatorname{diag}\left(d_{i}\right), d_{i} \in[0, 1], i \in N$.

Furthermore, a global error estimation formula for the EVLCP(A, q) is also provided, as follows:

Let $x^{*}$ be the solution of the EVLCP(A, q). If the block matrix $A = \left(A_{0}, A_{1}, \cdots, A_{k}\right)$ has the row W-property, then for any $x\in R^{n}$,

where

Apparently, due to the difficulty to compute $\left \| \left [(I-D)A_{j}^{'}+DA_{l}^{'} \right]^{-1} \right \|$ exactly, it is upper bound (1.1) for $\alpha (A)$ and cannot be computed easily. Thus, some computable upper bounds for $\alpha (A)$ are given under various matrix norms by considering the structured property for matrices $A_{j}, j = 0, 1, \dots, k$.

For example, Zhang et al. provided an upper bound on $\alpha _{\infty } (A)$ when all $A_{j}$ are $SDD$ matrices in ^[1], and also provided an upper bound on another $\alpha _{\infty } (A)$ for a special matrix A under certain conditions.

Theorem 1.2. ^[1]   Suppose that matrices $A_{0}, A_{1}, \cdots, A_{k}$ has the positive diagonals, with the spectral radius

then $A = \left(A_{0}, A_{1}, \cdots, A_{k}\right)$ has the row W-property and

where $\Lambda_{i}$ is the diagonal part of $A_{i}$, $Q_{i} = \Lambda_{i}-A_{i}$, for $i = 0, 1, \dots, k$.

In addition, Zhang et al. presented a computable upper bound for $\alpha (A)$ under the infinity norm in another rspecial class of block matrices.

Theorem 1.3. ^[1]   Suppose that $A_{0}, A_{1}, \cdots, A_{k}$ are $SDD$ matrices and $A = \left(A_{0}, A_{1}, \cdots, A_{k}\right)$ has the row W-property, and for each $i\in N, \left(A_{j}\right)_{ii}\left(A_{l}\right)_{ii} > 0$, with any $j < l\in\left \{ 0, 1, \dots, k \right \}$, then

where $\tilde{A}_{i}$ is the comparison matrix of ${A}_{i}$, i.e., $\left (\tilde{A}_{i}\right) _{\tau \tau } = \left | \left (A_{i} \right)_{\tau \tau } \right |, \left (\tilde{A}_{i}\right) _{\tau j } = -\left | \left (A_{i} \right)_{\tau j } \right |$ for $\tau \neq j, \left(A_{i}\right)_{\tau j}$ is the element in the $\tau$-th row and j-th column of $A_{i}$, and $\tilde{\left(A_{i}\right)} _{\tau j}$ is the element in the $\tau$-th row and j-th column of $\tilde{(A)} _{i}$.

However, the error estimation formula provided is applicable only to a certain type of special matrix, and it is not easy to verify. Therefore, it is necessary to explore the error estimation formula for solutions of EVLCP(A, q) for other special matrix classes.

In 2021, Wang et al. provided error estimation formulas for the EVLCP(A, q) of $B_{\pi }^{R}$-matrices and $B$-matrices in reference ^[14]. In 2023, Zhao et al. provided error estimation formulas for the EVLCP(A, q) of $S-SDDS-B$ matrix and $S-SDDS$ matrix in reference ^[15].

In 2013, García Esnaola and Peña first proposed a special class of $H$-matrices: $\sum$-SDD matrices (see ^[16] for details) and provided error estimates for their linear complementarity problems with parameters. Its definition is as follows:

Definition 1.3. ^[16]   Let matrix $B = \left(b_{ij}\right) \in C^{\operatorname{n\times n}}$ if there is a non empty subset $S$ such that the following two conditions hold:

(I) $\left|b_{i i}\right| > r_{i}^{S}(B), i \in S$;

(II) $\left(\left|b_{ii}\right|-r_{i}^{s}(B)\right)\left(\left|b_{j j}\right|-r_{j}^{s}(B)\right) > r_{i}^{\bar{s} }(B) r_{j}^{s}(B), i \in S, j \in \bar{S}$.

then $B$ is called the $\sum-SDD$ matrix.

Theorem 1.4. ^[16]   If $B$ is an $\sum-SDD$ matrix and $S$ is a nonempty subset of N, then

where

2.   A global error bound for the extended vertical LCP of $\sum-SDD$ Matrix

Proposition 2.1. Let $B = \left(b_{ij}\right) \in C^{\operatorname{n\times n}}$ and $M = \left(m_{ij}\right) \in C^{\operatorname{n\times n}}$ be $\sum-SDD$ matrices with positive main diagonal elements, and all have the same set $S \subset N$, If $\forall i \in S, \forall j \in \bar{S}$, satisfies $b_{i j} m_{i j} > 0$ (or $b_{ji} m_{ji} > 0$) and

then $(I-D) B+D M$ is a $\sum-SDD$ matrices, where $D = \operatorname{diag}\left(d_{i}\right), d_{i} \in[0, 1], i \in N$.

Proof. Since both $B$ and $M$ are $\sum-SDD$ matrice, so for any $i \in S, j \in \bar{S}$, the following hold:

Note that $d_{i} \in[0, 1]$, hence $1-d_{i} \geq 0$ and $d_{i} \geq 0$, they are not equal to 0 at the same time. Let $(I-D) B+D = C = (c_{ij})$. Thus for any $i \in S, j \in \bar{S}$, we have

i.e.,

and for any $i \in S, j \in \bar{S}$, we have

form Definition 1.3 the conclusion follows.

According to Proposition 2.1, Lemma 1.1 and the fact that a $\sum-SDD$ matrix is nonsingular(can be found in ^[17] for), block matrix composed of $\sum-SDD$ matrix has the row W-property.

Proposition 2.2. $A_{0}, A_{1}, \cdots, A_{k}$ are $\sum-SSD$ matrices, and each $A_{l_i}\left(l_{i} = 0, 1, \cdots, k\right)$ satisfies the condition of Proposition 2.1, then each $A_{l}^{'}$ in $A^{'} \in \Re (A)$ is a $\sum-SDD$ matrix, $A = (A_{0}, A_{1}, \cdots, A_{k})$ has the row W-property.

Proof. From Definition 1.2, for the i-th row $\left (A_{l}^{'} \right)_{i.} \left (i\in N \right)$ of $A_{l}^{'}$, there exist $l_{i} \in\{0, 1, \cdots, k\}$, such that $\left(A_{l}^{\prime}\right)_{i.} = \left(A_{j i}\right)_{i.}$. Since $A_{l_{i} }$ is a $\sum-SDD$ matrix, for any $i\in S, j\in \bar{S}$, we have

i.e.,

from Definition 1.3, $A_{l}^{'}$ is a $\sum-SDD$ matrix.

Let $A_{j}^{'}, A_{l}^{'}$ be any two blocks in $A^{'} \in \mathfrak{R}(A)$, then $A_{j}^{'}, A_{l}^{'}$ are all $\sum-SDD$ matrices. According to Proposition 2.1, $\left (I-D \right)A_{j}^{'}+DA_{l}^{'}$ is a $\sum-SDD$ matrix for any $D = \operatorname{diag}\left(d_{i}\right), d_{i} \in[0, 1], i \in N$, and thus $\left (I-D \right)A_{j}^{'}+DA_{l}^{'}$ is nonsingular. From Lemma 1.1, block matrix $A = (A_{0}, A_{1}, \cdots, A_{k})$ has the row W-property.

Next, we provide an upper bounds for $\alpha _{\infty } (A)$ with each $A_{l}, l = 0, 1, 2, \cdots, k$ being a $\sum-SDD$ matrix.

Theorem 2.1. Let $A = (A_{0}, A_{1}, \cdots, A_{k})$, if each $A_{l_{i} } \left (l_{i} = 0, 1, \dots, k \right)$ is a $\sum-SDD$ matrix and satisfies the condition of Proposition 2.1, then

where

Proof. For any two blocks $A_{j}^{'}, A_{l}^{'}$ in $A^{'} \in \mathfrak{R}(A)$, and any $D = \operatorname{diag}\left(d_{i}\right), d_{i} \in[0, 1], i \in N$. According to Propositions 2.1 and 2.2, it can be inferred that $A_{j}^{'}, A_{l}^{'}$ and $A_{D}$ all are $\sum-SDD$ matrices with positive main diagonal elements. According to Theorem 1.4,

where any $i\in S, \tau \in \bar{S}$,

We have

where $t = i, l$, and

Similarly, we have

where $t = j, l$, and

Therefore, it can be concluded that

where $t = j, l$, and

Therefore,

Similarly, it can be inferred that

then

Furthermore, from Definition 1.2, we can regard $A_{j}^{'}$ and $A_{l}^{'}$ as two blocks in a row rearrangement fo $A = \left (A_{0}, A_{1}, \dots, A_{k} \right)$, and thus for $t = j$ or $t = l$ and for any $i \in N$, there exists $t_{i} \in\{0, 1, \cdots, k\}$ such that

we have

and

and

thus

Similarly, it can be concluded that

then for any $A_{j}^{'}$ and $A_{l}^{'}$ for $A^{'} \in \mathfrak{R}(A)$, satisfy

from the arbitrariness of $A_{j}^{'}$ and $A_{l}^{'}$, the conclusion follows.

Next, we give a numerical example to illustrate that our results have advantages over some existing results.

Example 1. Let $A = \left (A_{0}, A_{1}, A_{2} \right)$, where

are all $\sum-SDD$ matrices and satisfies the condition of Proposition 2.1, thus $A = \left (A_{0}, A_{1}, A_{2} \right)$$A = \left (A_{0}, A_{1}, A_{2} \right)$ has the row W-property. Then by Theorem 2.1 we can get

By Theorem 1.2, Since $\rho\left(\max \left(\Lambda_{0}^{-1}\left|Q_{0}\right|, \Lambda_{1}^{-1}\left|Q_{1}\right|, \cdots, \Lambda_{k}^{-1}\left|Q_{k}\right|\right)\right) = 0.8760 < 1$, we get

By Theorem 1.3 we get

According to the calculation example, it can be seen that new bound in Theorem 2.1 is sharper than those in Theorems 1.2 and 1.3 given by Zhang et al. in ^[1] in some cases.

3.   Conclusions

In this paper, I first apply the properties of $\sum-SDD$ matrices to prove that block matrices composed of $\sum-SDD$ matrices have row W-properties under certain conditions and obtains the extension of $\sum-SDD$ matrices under these conditions for the error bound of the solution to the vertical linear complementarity problem. In the process of research, it is found that the error bounds of extended vertical linear complementarity problems for other types of matrices need to be further studied and explored, such as $N$-type matrices and $CKV$-type matrices.

Use of AI tools declaration

The author declares he/she has not used Artificial Intelligence (AI) tools in the creation of this article.

Conflict of interest

The author declares no conflict of interest.