Sequential stochastic blackbox optimization with zeroth-order gradient estimators

1.   Introduction

Schur complement of a matrix is widely used and has attracted the attention of many scholars. In 1979, the Schur complement question of a strictly diagonally dominant (SDD) matrix was studied by Carlson and Markham ^[1]. They certified the Schur complement of SDD matrix is also an SDD matrix. Before long, some renowned matrices such as doubly diagonally dominant matrices and Dashnic-Zusmanovich (DZ) matrices were researched, and the results were analogous ^[2,3,4,5]. In 2020, Li et al. proved that the Schur complements and the diagonal-Schur complements of Dashnic-Zusmanovich type (DZ-type) matrices are DZ-type matrices under certain conditions in ^[6]. In 2023, Song and Gao ^[7] proved that the Schur complements and the diagonal-Schur complements of CKV-type matrices are CKV-B-type matrices under certain conditions. Furthermore, there are many conclusions on Schur complements and diagonal-Schur complements for other classes of matrices, see ^{[8,9,10,11,12,13,14,15]}.

The upper bound of the inverse infinite norm of the non-singular matrix is widely used in mathematics, such as the convergence analysis of matrix splitting and matrix multiple splitting iterative method for solving linear equations. A traditional way to find the upper bound of an infinite norm for the inverse of a nonsingular matrix is to use the definition and properties of a given matrix class, see ^{[16,17,18,19]} for details. The first work was by Varah ^[19], who in 1975 gave the upper bound of the infinite norm of the inverse of the SDD matrix. However, in some cases, the bounds of Varah may yield larger values. In 2020, Li ^[20] obtained two upper bounds of the infinite norm of the inverse of the SDD matrix based on Schur complement, and in 2021, Sang ^[21] obtained two upper bounds for the infinity norm of DSDD matrices. In 2022, based on the Schur complement, Li and Wang obtained some upper bounds for the infinity norm of the inverse of GDSDD matrices ^[22].

In this paper, $n$ is a positive integer and $N = \{1, 2, ..., n\}$. Let $S$ be any nonempty subset of $N$, $S\subset N$, $\overline{S}: = N\setminus S$ for the complement of $S$. $C^{n\times n}$ denotes the set of complex matrices of all $n\times n$. $R^{n\times n}$ denotes the set of all $n\times n$ real matrices. $I \in {R^{n \times n}}$ is an identity matrix, $A = [a_{ij}]\in {C^{n \times n}},$ $|A| = [|a_{ij}|]\in {R^{n \times n}}$ and

The matrix $A$ is known as the strictly diagonal dominance SDD matrix, abbreviated as $A\in$ SDD, if

Definition 1. ^[23] Let $S$ be an arbitrary nonempty proper subset of the index set. $A = [a_{ij}] \in C^{n\times n}, n\geq 2$, is called an $S$-SOB ($S$-Sparse Ostrowski-Brauer) matrix if

(i) $|a_{ii}| > r_{i}^{S}(A)$ for all $i\in S$;

(ii) $|a_{jj}| > r_{j}^{\overline{S}}(A)$ for all $j\in S$;

(iii) For all $i\in S$ and all $j\in \bar{S}$ such that $a_{ij}\neq0$,

(iv) For all $i\in S$ and all $j\in \bar{S}$ such that $a_{ji}\neq0$,

Definition 2. ^[24] A matrix A is called GDSDD matrix if $J\neq \emptyset$ and there exists proper subsets $N_{1}, N_{2}$ of $N$ such that $N_{1}\cap N_{2} = \emptyset, N_{1}\cup N_{2} = N$ and for any $i\in N_{1}$ and $j\in N_{2},$

where $J: = \{i\in N :|a_{ii}| > r_{i}(A)\}.$

Definition 3. ^[25] A matrix $A$ is called an $H$-matrix, if its comparison matrix $\mu(A) = [\mu_{ij}]$ defined by

is an $M$-matrix, i.e., $[\mu(A)]^{ - 1} \geq 0.$

It is shown in ^[1] that if $A$ is an $H$-matrix, then,

Let $A$ be an $M$-matrix, then $det(A) > 0$.

In addition, it was shown that $S$-SOB, SDD and GDSDD matrices are nonsingular $H$-matrix in ^[23,26]. Varah ^[19] gave the following upper bound for the infinity norm of the inverse of SDD matrices:

Theorem 1. ^[19] Let $A = [a_{ij}]$ be an SDD matrix. Then,

Theorem 2. ^[27] Let $A = [a_{ij}]\in C^{n\times n}, n\geq2$, be an $S$-SOB matrix, where $S\subset N$, $1\leq|S|\leq n-1$. Then,

where

Theorem 3. ^[28] Let $A = [a_{ij}]\in C^{n\times n}$, $n\geq2$, be an GDSDD matrix, where $S\subset N$, $1\leq|S|\leq n-1$. Then,

In this paper, based on the Schur complement, we present some upper bounds for the infinity norm of the inverse of $S$-SOB matrices, and numerical examples are given to show the effectiveness of the obtained results. In addition, applying these new bounds, a lower bound for the smallest singular value of $S$-SOB matrices is obtained.

2.   The Schur complement of $S$-SOB matrices

Given a matrix $A = \left({{a_{ij}}} \right) \in {C^{n \times n}}$ that is nonsingular, $\alpha = \{i_{1}, i_{2}, ..., i_{k}\}$ is any nonempty proper subset of $N$, $|\alpha|$ is the cardinality of $\alpha$ (the number of elements in $\alpha$, i.e., $|\alpha| = k$), $\bar{\alpha} = N-\alpha = \left\{ {{j}_{1}}, \cdots, {{j}_{l}} \right\}$ is the complement of $\alpha$ with respect to $N$, $A(\alpha, \bar{\alpha})$ is the submatrix of $A$ lying in the rows indexed by $\alpha$ and the columns indexed by $\bar{\alpha}$, $A(\alpha)$ is the leading submatrix of $A$ whose row and column are both indexed by $\alpha$, and the elements of $\alpha$ and of $\bar{\alpha}$ are both conventionally arranged in increasing order. If $A(\alpha)$ is not singular, the matrix $A/\alpha$ is called the Schur complement of $A$ with respect to $A(\alpha)$. At this point

Lemma 1. (Quotient formula ^[28,29]) Let $A$ be a square matrix. Let $B$ is a nonsingular principal submatrix of $A$ and $C$ is a nonsingular principal submatrix of $B$. Then, $B/C$ is a nonsingular principal submatrix of $A/C$ and $A/B = (A/C)/(B/C)$, where $B/C$ is the Schur complement of $C$ in matrix $B$.

Lemma 2. Let $A = ({{a}_{ij}})\in {{C}^{n\times n}}$ be an $S$-SOB matrix, $n\ge 2$ and where $\alpha\subseteq S$ or $\alpha\subseteq \bar{S}$. Then, $A(\alpha)$ is an SDD matrix.

Proof. When $\alpha\subseteq S$, since $A$ is an $S$-SOB matrix and $|a_{ii}| > r_{i}^{S}(A)\geq r_{i}^{\alpha}(A) = \sum\limits_{k\neq i, k\in\alpha}|a_{ik}|$ for all $i\in \alpha$, we have $r_{i}[A(\alpha)] = \sum\limits_{k\neq i, k\in\alpha}|a_{ik}| = r_{i}^{\alpha}(A)$ and $|a_{ii}| > r_{i}[A(\alpha)].$ It is easy to obtain that $A(\alpha)$ is an $SDD$ matrix. Homoplastically, so is $\alpha\subseteq \bar{S}$. □

Lemma 3. Let $A = ({{a}_{ij}})\in {{C}^{n\times n}}$ be an $S$-SOB matrix, $n\ge 2$ and $\alpha$ be a subset of $N$. Then, $A(\alpha)$ is an $S$-SOB matrix.

Proof. If $S\subset\alpha$, since $A$ is an $S$-SOB matrix, then,

(i) For all $i\in S$, $|a_{ii}| > r_{i}^{S}(A) = r_{i}^{S}(A(\alpha))$,

(ii) For all $j\in \bar{S}\cap\alpha$, $|a_{jj}| > r_{j}^{\bar{S}}(A) > r_{j}^{\bar{S}\cap\alpha}(A) = r_{j}^{\bar{S}\cap\alpha}(A(\alpha))$,

(iii) For all $i\in S, \; j\in \bar{S}\cap\alpha$ such that $a_{ij}\neq0$,

(iv) For all $i\in S, \; j\in \bar{S}\cap\alpha$ such that $a_{ji}\neq0$,

Thus, $A(\alpha)$ is an $S$-SOB matrix and $A(\alpha)\in$\{$S$-SOB$\}$.

In a similar way, if $\bar{S}\subset\alpha$, $A(\alpha)$ is an $\bar{S}$-SOB matrix. Meanwhile, when $\alpha$ is contained neither in $S$ nor in $\bar{S}$, $A(\alpha)$ is an $(S\cap\alpha)$-SOB matrix. Finally, $A(\alpha)\in${$S$-SOB}. □

Lemma 4. Let $A = ({{a}_{ij}})\in {{C}^{n\times n}}$ be an $S$-SOB matrix, $n\ge 2$ and let $A$ be a matrix satisfying ${{a}_{ij}} = 0, {{a}_{ii}} > r_{i}(A)$ and ${{a}_{ji}} = 0, {{a}_{jj}} > r_{j}(A)$ for $i\in S, j\in \bar{S}.$ If $\alpha = \{i_{1}\}\subset S,$ denote

where $j_{t}\in (S\setminus\alpha), j_{s}\in \bar{S}$, then $B\in\{$SGDD$_{3}\}$.

Proof. Since $A$ is an $S$-SOB matrix, if $S_{B} = \{1, 2\}$, for all $i\in S_{B}$, then,

There exist four different cases.

Case 1. When $|a_{j_{s}i_{1}}|\neq0$, $|a_{i_{1}j_{s}}|\neq0$.

(i) If $|a_{j_{s}j_{s}}| < r_{j_{s}}(A)$, from Definition 1, we have $|a_{i_{1}i_{1}}|\geq r_{i_{1}}(A)$,

(ii) If $|a_{j_{s}j_{s}}| > r_{j_{s}}(A)$, $|a_{i_{1}i_{1}}|\geq r_{i_{1}}(A)$, we get

(iii) If $|a_{j_{s}j_{s}}| > r_{j_{s}}(A)$, $|a_{i_{1}i_{1}}|\leq r_{i_{1}}(A)$, we obtain

Case 2. When $|a_{j_{s}i_{1}}|\neq0$, $|a_{i_{1}j_{s}}| = 0$, $|a_{i_{1}i_{1}}|\geq r_{i_{1}}(A)$ the proof is analogous to (i) and (ii) in Case 1. We obtain

Case 3. If $|a_{j_{s}i_{1}}| = 0$, $|a_{i_{1}j_{s}}|\neq0$, then, $|a_{j_{s}j_{s}}| > r_{j_{s}}(A)$. By the same proof method as (ii) and (iii) in Case 1, we have

Case 4. If $|a_{j_{s}i_{1}}| = 0$, $|a_{i_{1}j_{s}}| = 0$, then, $|a_{i_{1}i_{1}}| > r_{i_{1}}(A)$, $|a_{j_{s}j_{s}}| > r_{j_{s}}(A)$, and

To sum up, the inequality $[|b_{11}|-r_{1}^{S_{B}}(B)][|b_{33}|-r_{3}^{\bar{S}_{B}}(B)] > r_{1}^{\bar{S}_{B}}(B)r_{3}^{S_{B}}(B)$ is held. In the same way, the inequality $[|b_{22}|-r_{2}^{S_{B}}(B)][|b_{33}|-r_{3}^{\bar{S}_{B}}(B)] > r_{2}^{\bar{S}_{B}}(B)r_{3}^{S_{B}}(B)$ also holds. At last, we obtain $B\in\{$GDSDD$_{3}\}$ and $B = \mu(B)$ is an $M$-matrix. By Definition 3, we know that det$B > 0$. The proof is completed. □

Theorem 4. Let $A = ({{a}_{ij}})\in {{C}^{n\times n}}$ be an $S$-SOB matrix, $n\ge 2$ and let $A$ be a matrix satisfying ${{a}_{ij}} = 0, \; {{a}_{ii}} > r_{i}(A)$ and ${{a}_{ji}} = 0, \; {{a}_{jj}} > r_{j}(A)$ for $i\in S, j\in \bar{S}.$ Denote $A/\alpha = (a^{'}_{j_{t}j_{s}})$. If $\alpha\subset S$, then, $A/\alpha\in\{$ GDSDD$_{n-k}^{(S\setminus\alpha), \bar{S}}\}$.

Proof. Note that $\alpha$ contains only one element. If $\alpha = {i_{1}}\subset S$, for all $j_{t}\in S\setminus\alpha$, $j_{s}\in \bar{S}$, then we have

We have $A/\{i_{1}\}\in\{$ GDSDD$_{n-1}^{(S\setminus\{i_{1}\}), \bar{S}}\}$ for any $i_{1}\in S$. Consider that $\alpha$ contains more than one element. If $i_{1}\in \alpha$, by the quotient formula (in ^[9] Theorem 2 (ii)), we have $A/\alpha = (A/\{i_{1}\})/((A(\alpha)/{i_{1}})\in\{$GDSDD$_{n-k}^{(S\setminus\alpha), \bar{S}}\}$. The proof is completed. □

Corollary 1. Let $A = ({{a}_{ij}})\in {{C}^{n\times n}}$ be an $S$-SOB matrix, $n\ge 2$ and let $A$ be a matrix satisfying ${{a}_{ij}} = 0, \; {{a}_{ii}} > r_{i}(A)$ and ${{a}_{ji}} = 0, \; {{a}_{jj}} > r_{j}(A)$ for $i\in S, j\in \bar{S}.$ Denote $A/\alpha = (a^{'}_{j_{t}j_{s}})$. If $\alpha\subset \bar{S}$, $j_{t}\in S, \; j_{s}\in \bar{S}\setminus\alpha$, then, $A/\alpha\in\{$GDSDD$_{n-k}^{S, (\bar{S}\setminus\alpha)}\}$.

Proof. The conclusion can be drawn by using the same proof method as Theorem 4. □

Corollary 2. Let $A = ({{a}_{ij}})\in {{C}^{n\times n}}$ be an $S$-SOB matrix, $n\ge 2$ and let $A$ be a matrix satisfying ${{a}_{ij}} = 0, \; {{a}_{ii}} > r_{i}(A)$ and ${{a}_{ji}} = 0, \; {{a}_{jj}} > r_{j}(A)$ for $i\in S, j\in \bar{S}.$ Denote $A/\alpha = (a^{'}_{j_{t}j_{s}})$. If $\alpha$ is contained neither in $S$ nor in $\bar{S}$, $j_{t}\in S\setminus\alpha, \; j_{s}\in \bar{S}\setminus\alpha$, then $A/\alpha\in\{$GDSDD$_{n-k}^{(S\setminus\alpha), (\bar{S}\setminus\alpha)}\}$.

Proof. The proof is similar to (^[9], Theorem 2 (iii)), so we get $A/\alpha = (A/(S\cap\alpha))/((A(\alpha)/(S\cap\alpha))\in\{$GDSDD$_{n-k}^{(S\setminus\alpha), (\bar{S}\setminus\alpha)}\}$. □

Theorem 5. Let $A = ({{a}_{ij}})\in {{C}^{n\times n}}$ be an $S$-SOB matrix, $n\ge 2$ and denote $A/\alpha = (a^{'}_{j_{t}j_{s}})$. If $\alpha = S$ or $\alpha = \bar{S}$, then $A/\alpha$ is an SDD matrix.

Proof. If $\{i_{1}\} = \alpha = S,$ for all $j_{t}\in \bar{\alpha}$, then we have

If $a_{j_{t}i_{1}} = 0$, then we get

If $a_{j_{t}i_{1}}\neq0$, then we obtain

Hence, for any $\{i_{1}\} = \alpha = S$, $A/\{i_{1}\}$ is an $SDD$ matrix. Taking $i_{1}\in \alpha = S$ and using the fact that $A$ is $SDD$, we know its Schur complement is as well. At last, we have $A/\alpha = (A/\{i_{1}\})/(A(\alpha)/\{i_{1}\})\in\{SDD\}$. By the same argument, so is $\alpha = \bar{S}$. □

Corollary 3. Let $A = ({{a}_{ij}})\in {{C}^{n\times n}}$ be an $S$-SOB matrix, $n\ge 2$ and denote $A/\alpha = (a^{'}_{j_{t}j_{s}})$. If $S\subset\alpha$ or $\bar{S}\subset\alpha$, then $A/\alpha$ is an SDD matrix.

Proof. From Theorem 5, $A/S$ is an $SDD$ matrix, consequently, $A/\alpha = [A/S]/[(A(\alpha)/S]\in\{SDD\}$. Similarly, if $\bar{S}\subset\alpha$, we have $A/\alpha = [A/\bar{S}]/[(A(\alpha)/\bar{S}]\in\{SDD\}$. □

Finally, making a summary of part of the content: if $\alpha\subset S$ or $\alpha\subset\bar{S}$, then $A(\alpha)\in\{SDD\}$, $A/\alpha\in\{$ GDSDD$\}$; if $S\subset\alpha$ or $\bar{S}\subset\alpha$, then $A(\alpha)\in${$S$-SOB}, $A/\alpha\in\{SDD\}$; if $S = \alpha$ or $\bar{S} = \alpha$, then $A(\alpha)\in\{SDD\}$, $A/\alpha\in\{SDD\}$; if $\alpha$ is contained neither in $S$ nor in $\bar{S}$, then $A(\alpha)\in${$S$-SOB}, $A/\alpha\in\{$GDSDD$\}$.

3.   Schur complement-based infinity bounds for the inverse of $S$-SOB matrices

In order to obtain the upper bound of the infinite norm of the inverse of the $S$-SOB matrix, we need to give the definition of a permutation matrix in which every row and every column of it has only one element of 1 and all the other elements are 0. It is easy to see from the definition that permutation matrices are also elementary matrices, so multiplication of any matrix only changes the position of the matrix elements, but does not change the size of the matrix elements.

For a given nonempty proper subset $\alpha$, there is a permutation matrix $P$ such that

We might as well assume that $A(\alpha)$ is nonsingular, let

under the circumstances

and

where ${{I}_{1}}$ (resp.${{I}_{2}}$) is the identity matrix of order $l$ (resp.$m$). We know that if $P$ is a permutation matrix, then ${{P}^{T}}$ is also a permutation matrix, and $||P|{{|}_{\infty }} = 1$. From the above we can obtain

Therefore, if the upper bounds of $||F|{{|}_{\infty }}$, $||{{(E{{P}^{T}}APF)}^{-1}}|{{|}_{\infty }}$, and $||E|{{|}_{\infty }}$ can be obtained, the upper bounds of $||{{A}^{-1}}|{{|}_{\infty }}$ can also be obtained, that is, the product of the above three norm bounds needs to be calculated. It's not hard to figure out

and

In ^[20], Li gives an upper bound for $||E|{{|}_{\infty }}$ as follows:

Lemma 5. ^[20] Let $A = \left[{{a}_{ij}} \right]\in {{C}^{n\times n}}$ be nonsingular with ${{a}_{ii}}\ne 0$, for $i\in N,$ and $\varnothing \ne \alpha \subset N$. If $A(\alpha)$ is nonsingular and

then,

Theorem 6. Let $A = \left[{{a}_{ij}} \right]\in {{{C}}^{n\times n}}$ be an $S$-SOB matrix and $D = [{{d}_{ij}}]\in {{C}^{n\times m}}.$ Then,

where $R_{i}(D) = \sum\limits_{k\in M}{|{{d}_{ik}}}|.$

Proof. Since $A = \left[{{a}_{ij}} \right]\in {{C}}^{n\times n}$ is an $S$-SOB matrix, we know from ^[1] that $A$ is an $H$-matrix, $[\mu(A)]^{ - 1} \geq |A^{ - 1}|$. Let

and $e = {{(1, ..., 1)}^{T}}$ be an m-dimensional vector, consequently,

Because of $S\subset N$, ${{\psi}_{p}} = \underset{k\in S}{\mathop{\max }}\, \{{{\psi}_{k}}\}, \; {{\psi}_{q}} = \underset{k\in \bar{S}}{\mathop{\max }}\, \{{{\psi}_{k}}\},$ it implies that

If ${{\psi}_{p}}\geq {{\psi}_{q}}$, then,

That is to say, if ${{\psi}_{p}}\geq {{\psi}_{q}}$, $r_{p}^{\bar{S}}(A) = 0$, then,

and

If ${{\psi}_{p}}\geq {{\psi}_{q}}$, $r_{p}^{\bar{S}}(A)\neq0$, then,

and

By Eq (3.10) $\times|{{a}_{qq}}|$ + Eq (3.11)$\times r_{p}^{\bar{S}}(A)$, we have

Thus,

If ${{\psi}_{q}}\geq {{\psi}_{p}}$, equally,

When $r_{q}^{S}(A) = 0$, $\sum\limits_{k\in M}{|{{d}_{qk}}}|\geq[|{{a}_{qq}}|-r_{q}^{\bar{S}}(A)]{{\psi}_{q}}$.

When $r_{q}^{S}(A)\neq0$, then

Eq (3.14) $\times r_{q}^{S}(A)$ + Eq (3.15)$\times |{{a}_{pp}}|$, we have

Consequently,

The conclusion follows from inequalities Eqs (3.9), (3.12), (3.13) and (3.16). □

Replacing $A$ and $D$ in Theorem 6 with $A(\alpha)$ and $A(\alpha, \bar{\alpha})$, respectively, yields Corollary 4.

Corollary 4. Let $A = \left[{{a}_{ij}} \right]\in {{{C}}^{n\times n}}$ be an $S$-SOB matrix and $\alpha\in N$, then, $||F||_{\infty}\leq1+\max\{\max\limits_{i\in\alpha}\frac{R_{i}[A(\alpha, \bar{\alpha})]}{|a_{ii}|-r_{i}[A(\alpha)]}, \; \beta(\alpha), \; \gamma(\alpha), \lambda(\alpha)\},$ where

Proof. Let $\alpha\subseteq S$ or $\alpha\subseteq\bar{S}$, $A(\alpha)$ be an $SDD$ matrix (from Lemma 2). Thus,

From Lemma 3, we have

(1) if $S\subset\alpha$, $A(\alpha)$ is an $S$-SOB matrix, then

Hence, $||F|{{|}_{\infty }}\leq 1+\beta(\alpha)$.

(2) If $\bar{S}\subset\alpha$, $A(\alpha)$ is an $\bar{S}$-SOB matrix, then

Accordingly, $||F|{{|}_{\infty }}\leq 1+\gamma(\alpha)$.

(3) If $\alpha$ is contained neither in $S$ nor in $\bar{S}$, $A(\alpha)$ is an $(S\cap\alpha)$-SOB matrix, then we have

Hence, $||F|{{|}_{\infty }}\leq 1+\lambda(\alpha)$. The proof is completed. □

Lemma 6. Let $A = \left[{{a}_{ij}} \right]\in {{{C}}^{n\times n}}$ be an $S$-SOB matrix and $x = [\mu(A(\alpha))]^{-1}y^{T}$, where $\alpha\subseteq S$, or $\alpha\subseteq \bar{S}.$ Let $\; x = (x_{1}, x_{2}, \cdots, x_{k})$, $y = (y_{1}, y_{2}, \cdots, y_{k})$, $y_{k} > 0$, $x_{g} = \max\limits_{i_{k}\in\alpha} x_{k}$, then

Proof. Note that $x = [\mu(A(\alpha))]^{-1}y^{T}$, so $[\mu(A(\alpha))]x = y^{T}.$ For all $\alpha\in S$, or $\alpha\in \bar{S}$, from Lemma 2, $\mu(A(\alpha))$ is an $H$-matrix, so $[\mu(A(\alpha))]^{-1}\geq0$ by Eq (1.3). Then

which gives $x_{g}\leq\frac{y_{g}}{|a_{i_{g}i_{g}}|-\sum\limits_{i_{v}\in \alpha}|a_{i_{g}i_{v}}|} = \frac{y_{g}}{|a_{i_{g}i_{g}}|- r_{i_{g}}^{\alpha}(A)}.$ Consequently, $0 \leq x_{k} \leq\max\limits_{i_{v}\in \alpha}\frac{y_{v}}{|a_{i_{v}i_{v}}|- r_{i_{v}}^{\alpha}(A)}, \; i_{k}\in\alpha$. □

Lemma 7. Let $A = \left[{{a}_{ij}} \right]\in {{{C}}^{n\times n}}$ be an $S$-SOB matrix, $x, \; y^{T}$ from Lemma 6, if $\alpha$ is contained neither in $S$ nor in $\bar{S}$, $x_{g} = \max\limits_{i_{k}\in\alpha} x_{k}$, then

where

Proof. When $\alpha$ is contained neither in $S$ nor in $\bar{S}$, $A(\alpha)$ is an $(S\cap\alpha)$-SOB matrix, so is $\mu(A(\alpha))$. Thus,

Replacing $A$ and $D$ in Theorem 6 with $[\mu(A(\alpha))]^{-1}$ and $y^{T}$, respectively, yields

Which implies that: $0 \leq x_{k} \leq \pi_{y^{T}}(\alpha)), \; i_{k}\in\alpha.$ □

For the sake of convenience, assume that the symbol of $A/\alpha$ in this part is the same as in the second part and denote:

$I = (1, 1, \cdots, 1)^{T}$ is an $k$ order column vector.

Theorem 7. Let $A = ({{a}_{ij}})\in {{C}^{n\times n}}$ be an $S$-SOB matrix, $n\ge 2$ and $A$ is a matrix satisfying ${{a}_{ij}} = 0, {{a}_{ii}} > r_{i}(A)$ and ${{a}_{ji}} = 0, {{a}_{jj}} > r_{j}(A)$ for $i\in S, j\in \bar{S}.$ Denote $A/\alpha = (a^{'}_{j_{t}j_{s}})$. If $\alpha\subset S$, then,

where $\theta_{1}(\alpha) = \max\{\max\limits_{i\in\alpha}\frac{1}{|a_{ii}|-r_{i}(A(\alpha))}, \; \eta_{1}(\alpha)\},$

Proof. By Lemma 2, we know $A(\alpha)$ is an $SDD$ matrix. Applying Varah's bound to $A(\alpha)$, we get

By Corollary 4, we have

By Theorem 4, it is easy to know $A/\alpha\in\{$ GDSDD$_{n-k}^{(S\setminus\alpha), \bar{S}}\}$. Therefore, from Theorem 3,

And then

Similarly,

Let

Furthermore, by Eqs (3.21)–(3.23), we have

Finally, by Eqs (3.2), (3.3), (3.19), (3.20) and (3.24), the conclusion follows. □

The following inference can be naturally drawn from Theorem 7:

Corollary 5. Let $A = ({{a}_{ij}})\in {{C}^{n\times n}}$ be an $S$-SOB matrix, $n\ge 2$ and $A$ be a matrix satisfying ${{a}_{ij}} = 0, {{a}_{ii}} > r_{i}(A)$ and ${{a}_{ji}} = 0, {{a}_{jj}} > r_{j}(A)$ for $i\in S, j\in \bar{S}.$ Denote $A/\alpha = (a^{'}_{j_{t}j_{s}})$. If $\alpha\subset \bar{S}$, then,

where $\theta_{2}(\alpha) = \max\{\max\limits_{i\in\alpha}\frac{1}{|a_{ii}|-r_{i}(A(\alpha))}, \; \eta_{2}(\alpha)\},$

Theorem 8. Let $A = ({{a}_{ij}})\in {{C}^{n\times n}}$ be an $S$-SOB matrix, $n\ge 2$ and $A$ be a matrix satisfying ${{a}_{ij}} = 0, {{a}_{ii}} > r_{i}(A)$ and ${{a}_{ji}} = 0, {{a}_{jj}} > r_{j}(A)$ for $i\in S, j\in \bar{S}.$ Denote $A/\alpha = (a^{'}_{j_{t}j_{s}})$. If $\alpha$ is contained neither in $S$ nor in $\bar{S}$, then,

where $\theta_{3}(\alpha) = \max\{\delta_{1}(\alpha), \; \eta_{3}(\alpha)\},$

Proof. By Lemma 3, we know $A(\alpha)$ is an $(S\cap\alpha)$-SOB matrix. Applying the bound of Theorem 2 to $A(\alpha)$, we get

By Corollary 4, we have

By Corollary 2, we know $A/\alpha\in\{$ GDSDD$_{n-k}^{(S\setminus\alpha), (\bar{S}\setminus\alpha)}\}$. Therefore,

And then,

Let $y^{T} = \mathbf{y_{1}} = \sum\limits_{j_{k}\in (\bar{S}\setminus\alpha)}|w_{j_{k}}|$, $y^{T}$ from Lemma 7, we get

In like manner, let $y^{T} = \mathbf{y_{2}} = \sum\limits_{j_{k}\in (S\setminus\alpha)}|w_{j_{k}}|$, $y^{T}$ from Lemma 7, we get

Let

Furthermore, by Eqs (3.28)–(3.30), we have

Finally, by Eqs (3.2), (3.3), (3.25), (3.26) and (3.31), the conclusion follows. □

Theorem 9. Let $A = \left[{{a}_{ij}} \right]\in {{{C}}^{n\times n}}$ be an $S$-SOB matrix, $\phi\neq\alpha = S$. If Eq (3.7) holds, then,

where $\theta_{4}(\alpha) = \max\{\max\limits_{i\in\alpha}\frac{1}{|a_{ii}|-r_{i}(A(\alpha))}, \; \eta_{4}(\alpha)\},$

Expressly, when $\phi\neq\alpha = S = \{i\}$,

$\theta_{4}'(\alpha) = \max\{\frac{1}{|a_{ii}|}, \; \eta_{4}'(\alpha)\},$

Proof. By Lemma 2, we know $A(\alpha)$ is an $SDD$ matrix. $||A(\alpha)^{-1}||_{\infty}$ is the same as Eq (3.19), and $||F||_{\infty}$ is the same as Eq (3.20). By Theorem 5, knowing that $A/\alpha$ is an $SDD$ matrix. Therefore,

Finally, by Eqs (3.2), (3.3), (3.19), (3.20) and (3.32), the conclusion follows. □

A proof similar to Theorem 9 leads to the results.

Corollary 6. Let $A = \left[{{a}_{ij}} \right]\in {{{C}}^{n\times n}}$ be an $S$-SOB matrix, where $\phi\neq\alpha = \bar{S}$. If Eq (3.7) holds, then,

where $\theta_{5}(\alpha) = \max\{\max\limits_{i\in\alpha}\frac{1}{|a_{ii}|-r_{i}(A(\alpha))}, \; \eta_{5}(\alpha)\},$

Distinguishingly, when $\phi\neq\alpha = \bar{S} = \{i\}$,

$\theta_{5}'(\alpha) = \max\{\frac{1}{|a_{ii}|}, \; \eta_{5}'(\alpha)\},$

Theorem 10. Let $A = \left[{{a}_{ij}} \right]\in {{{C}}^{n\times n}}$ be an $S$-SOB matrix, where $S\subset\alpha$. If Eq (3.7) holds, then,

where $\theta_{6}(\alpha) = \max\{\delta_{2}(\alpha), \; \eta_{6}(\alpha)\},$

Proof. $A(\alpha)$ is an $S$-SOB matrix (by Lemma 3). Thus,

From Corollary 4, we know

By Corollary 3, we obtain $A/\alpha$ is an $SDD$ matrix. Therefore,

Finally, by Eqs (3.2), (3.3), (3.33), (3.34) and (3.35), the conclusion follows. □

According to Theorem 10, the following result will come out naturally.

Corollary 7. Let $A = \left[{{a}_{ij}} \right]\in {{{C}}^{n\times n}}$ be an $S$-SOB matrix, $\bar{S}\subset\alpha$. If Eq (3.7) holds, then

where $\theta_{7}(\alpha) = \max\{\delta_{3}(\alpha), \; \eta_{7}(\alpha)\},$

$\eta_{7}(\alpha) = \max\limits_{{i\in(S\setminus\alpha) }}\frac{1} {|{{a}_{ii}}|-r_{i}^{(S\setminus\alpha)}(A) -|v_{i}|[\mu(A(\alpha))]^{-1}\sum\limits_{k\in (S\setminus\alpha)}|w_{k}|}.$

Theorem 11. Let $A = ({{a}_{ij}})\in {{C}^{n\times n}}$ be an $S$-SOB matrix, $n\ge 3$ and let $A$ satisfy that when ${{a}_{ij}} = 0, {{a}_{ii}} > r_{i}(A)$ and ${{a}_{ji}} = 0, {{a}_{jj}} > r_{j}(A)$ for $i\in S, j\in \bar{S}.$ Denote $A/\alpha = (a^{'}_{j_{t}j_{s}})$, then,

where $\Gamma_{i}(A) = (1+\frac{\max\limits_{j\in N, \atop j\neq i}|a_{ji}|}{|a_{ii}|})(1+\frac{\max\limits_{j\in N, \atop j\neq i}|a_{ij}|}{|a_{ii}|})\tilde{\Gamma}_{i}(A),$

and $c_{jk} = a_{jk}-\frac{a_{ji}a_{ik}}{a_{ii}}.$

Proof. Since $A$ is an $S$-SOB matrix, by Lemma 2 and Theorem 5, we know $A(\alpha)$ and $A/\alpha$ are nonsingular. Therefore, taking $\alpha = \{i\}$, then $A(\alpha) = a_{ii}$, $\bar{\alpha} = N-\{i\}$, and

Because $A/\alpha = (a^{'}_{j_{t}j_{s}})$, let $|a^{'}_{j_{t}j_{s}}| = |a_{j_{t}j_{s}}-\frac{a_{j_{t}i}a_{ij_{s}}}{a_{ii}}| = |c_{j_{t}j_{s}}|(j_{t}, j_{s}\in (N\setminus \{i\}))$. By calculation, we obtain for $j_{t}\in (S\setminus \{i\}), j_{s}\in (\bar{S}\setminus \{i\})$,

By Eq (3.27), we have

Finally, by Eqs (3.36), (3.37), (3.38) and (3.39) the conclusion follows. □

We illustrate our results by the following examples:

Example 1. Consider matrix $A$ as a tri-diagonal $n\times n$ matrix

Let $b = 1.5, \; n = 10000$. We get that matrix $A$ is an $SDD$ matrix. It is easy to verify matrix A is an $SDD$ matrix, so it is also a $S$-SOB, $DSDD$, $GDSDD$ and $DZ$ matrix. Therefore, from Theorem 1, we put the result in Table 1.

Actually, $\|A^{-1}\|_{\infty} = 0.0002$. This example shows that the boundary in Theorem 11 is superior to other theorems in some cases.

Example 2. Consider matrix

By computation, the matrix A is an $S$-SOB matrix and $S = \{2, 3, 5\}$. According to Theorem 2, we obtain

According to Theorem 11, it is easy to get

In practice, $||{{A}^{-1}}|{{|}_{\infty }} = 0.2155$. Obviously, the boundary in Theorem 11 is superior to Theorem 2 in some cases.

Example 3. Consider matrix

Obviously, the matrix A is an SDD matrix, and it's also an $S$-SOB matrix and $S = \{2, 3, 4, 5, 8\}$. According to Theorem 1, we can obtain

According to Theorem 2, we can obtain

According to Theorem 11, we can obtain

In fact, $||{{A}^{-1}}|{{|}_{\infty }} = 0.0497.$ This example shows that the boundary in Theorem 11 is superior to Theorems 1 and 2 in some cases.

4.   Error bounds for LCPs of $S$-SOB matrices

In this section, we will apply the result in Section 3 to the linear complementarity problems (LCPs), to obtain two kinds of error bounds for LCPs of $S$-SOB matrices. We first need to give some lemmas that would be used in the following theorems:

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

Lemma 9. Suppose that $M = (m_{ij})\in \mathbb{R}^{n\times n}$ is an S-SOB matrix with positive diagonal entries, let

then, $\tilde{M}$ is also a real S-SOB matrix with positive diagonal entries, where $D = diag(d_{1}, \cdots, d_{n})$, $d_{i}\in[0, 1]$.

Proof. Note that

Hence, for each $i\in S$, $j\in \bar{S}$,

Then, for any $i\in S$, $j\in\bar{S}$, $d_{i}\in(0, 1)$, we have

For any $i\in S$, $j\in\bar{S}$, we get

When $d_{i} = 0$, $\tilde{m}_{ii} = 1-d_{i}+d_{i}m_{ii} = 1$, we obtain

When $d_{i} = 1$, $\tilde{m}_{ij} = 1-d_{i}+d_{i}m_{ij} = m_{ij}$, then

As $d_{i}\in[0, 1]$, conditions (i)–(iv) in Definition 1 are fulfilled for all $i\in S$ and $j\in \bar{S}$. So the conclusion follows. □

Lemma 9 indicates that $\tilde{M}$ is an $S$-SOB matrix when $M$ is an $S$-SOB matrix. We will present an error bound for the linear complementarity problem of $S$-SOB matrices. The following theorem is one of our main results, which gives an upper bound on the condition constant $\max_{d\in[0, 1]^{n}}\|(I-D+DA)^{-1}\|_{\infty}$ when $A$ is an $S$-SOB matrix.

Theorem 12. Let $A = (a_{ij})\in\mathbb{R}^{n\times n}$ be an S-SOB matrix with positive diagonal entries, and $\tilde{A} = [\tilde{a_{ij}}] = I-D+DA$, where $D = diag(d_{i})$ with $0\leq d_{i}\leq 1$. Then

where

and $\varsigma_{j}^{S}(A) = \frac{1-d_{j}+d_{j}a_{jj}}{1-d_{t}+d_{t}a_{tt}}-\frac{a_{ji}a_{ij}}{a_{ii}a_{jj}}-\sum\limits_{p\in S, \atop p\neq j, i} \frac{a_{jk}}{a_{jj}}-\sum\limits_{p\in S, \atop p\neq j, i}\frac{a_{ji}a_{ik}}{a_{ii}a_{jj}}$.

Proof. Because $\tilde{A} = (\tilde{a_{ij}}) = (I-D+DA)$, we know $\tilde{A}$ is an $S$-$SOB$ matrix with positive diagonal entries from Lemma 9. By Theorem 11, the following inequality holds

where $\Gamma_{i}(\tilde{A}) = (1+\frac{\max\limits_{j\in N, \atop j\neq i}|\tilde{a_{ji}}|}{|\tilde{a_{ii}}|})(1+\frac{\max\limits_{j\in N, \atop j\neq i}|\tilde{a_{ij}}|}{|\tilde{a_{ii}}|})\tilde{\Gamma}_{i}(\tilde{A}),$

and $\tilde{c_{jk}} = \tilde{a_{jk}}-\frac{\tilde{a_{ji}}\tilde{a_{ik}}}{\tilde{a_{ii}}}.$

Since $\tilde{A}$ is a $S$-SOB matrix, we have $\tilde{a_{ii}} = 1-d_{i}+d_{i}a_{ii}$ and $\tilde{a_{ij}} = d_{i}a_{ij}$ for all $i, j\in N$.

Similarly, we have

By Lemma 8, it is easy to get

Denote $1-d_{t}+d_{t}a_{tt} = \max_{i\in N}\{1-d_{i}+d_{i}a_{ii}\}$. From Lemmas 8 and 9, we get

where $\varsigma_{j}^{S}(A) = \frac{1-d_{j}+d_{j}a_{jj}}{1-d_{t}+d_{t}a_{tt}}-\frac{a_{ji}a_{ij}}{a_{ii}a_{jj}}-\sum\limits_{p\in S, \atop p\neq j, i} \frac{a_{jk}}{a_{jj}}-\sum\limits_{p\in S, \atop p\neq j, i}\frac{a_{ji}a_{ik}}{a_{ii}a_{jj}}$. In similar way, we know

So, from Eqs (4.2)–(4.6) the conclusion follows. This proof is completed. □

5.   Conclusions

Based on the fact that the Schur complement of the $S$-SOB matrix is a $GDSDD$ matrix, we give an infinity norm bound for the inverse of the $S$-SOB matrix based on the Schur complement. By using the infinity norm bound for the inverse of the $S$-SOB matrix, an error bound is given for the linear complementarity problem of the $S$-SOB matrix.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgements

This work was supported by the Natural Science Research Project of Department of Education of Guizhou Province (Grant No. QJJ2022015) and the Natural Science Research Project of Department of Education of Guizhou Province (Grant No. QJJ2022047). The Natural Science Research Project of Department of Education of Guizhou Province (Grant Nos. QJJ2023012, QJJ2023061, QJJ2023062).

Conflict of interest

The authors declare no conflict of interest.