Infinity norm upper bounds for the inverse of $SDD_1$ matrices

1.   Introduction

Let $n$ be an integer number, $N = \{1, 2, \ldots, n\}$, and ${\mathbb{C}}^{n\times n}$ be the set of all complex matrices of order $n$. A matrix $A = [a_{ij}]\in {\mathbb{C}}^{n\times n}$ ($n\geq 2$) is called a strictly diagonally dominant ($SDD$) matrix if

where

It was shown that $SDD$ matrices is a subclass of $H$-matrices ^[1], where a matrix $A = [a_{ij}] \in \mathbb{C}^{n\times n}$ is an $H$-matrix if and only if there exists a positive diagonal matrix $X$ such that $AX$ is an $SDD$ matrix ^[1].

In 2011, a new subclass of $H$-matrices was proposed by J. M. Peña, which is called $SDD_1$ matrices ^[2], and the definition of $SDD_1$ matrix is given as follows.

Definition 1. ^[2] A matrix $A = [a_{ij}]\in {\mathbb{C}}^{n\times n}\; (n\geq 2)$ is called an $SDD_1$ matrix if

where

$N_{1}(A) = \{ i|\; | a_{ii}|\le r_{i}(A)\}\; and\; N_{2}(A) = \{ i|\; | a_{ii}| > r_{i}(A)\}.$

In ^[2], J. M. Peña "proved" the following result:

Theorem 1. ([2 Theorem 2.3]) If a matrix $A = [a_{ij}]\in {\mathbb{C}}^{n\times n}$ is an $SDD_1$ matrix by rows, then it is an $H$-matrix.

From the definition of $H$-matrix and Theorem 1, given an $SDD_1$ matrix $A$, there exists a correspondingly positive diagonal matrix $D$, such that $AD$ is an $SDD$ matrix. The great interest of the constitution of positive diagonal matrix $D$ was commented in the introduction in ^[2], and divided it into two cases, that is, the given $SDD_1$ matrix has a unique row $i$ strictly diagonally dominant and at least two rows $i$ and $j$ strictly diagonally dominant, to constitute positive diagonal matrix. However, Dai in ^[3] found that the proof of Theorem 1 is incorrect, and a counter example was given as follows.

Example 1. ^[3] Let us consider $SDD_1$ matrices

From the proof of Theorem 1 in ^[2], it is easy to obtain that $D = diag\{\frac{3}{4}, \frac{1}{3}, \frac{1}{4}, 1\}$, however, $AD$ is not an $SDD$ matrix by rows.

Dai found that the proof of the case that the given $SDD_1$ matrix has at least two rows $i$ and $j$ strictly diagonally dominant is incorrect, and a correct proof of Theorem 1 was presented in ^[3]. The correct proof of Theorem 1 divides the case that $SDD_1$ matrices have at least two rows $i$ and $j$ strictly diagonally dominant into $S = \varnothing$ and $S\neq \varnothing$, where $S$ is given as follows:

However, when we use the correct proof to give the upper bound for the infinity norm of the inverse of $SDD_1$ matrices, the upper bound needs to be considered in different cases. Therefore, in order to avoid the difficult, we need to improve the proof of Theorem 1.

In addition, it was shown that upper bound of the infinity norm of inverse of a given nonsingular matrix has many potential applications in computational mathematics, such as for bounding the condition number and for proving the convergence of iteration methods. Moreover, upper bounds of the infinity norm of inverse for different classes of matrix have been widely studied, such as Nekrasov matrices ^[4,5,6], $S$-Nekrasov matrices ^[7,8], $QN$-Nekrasov matrices ^[8], $\{p_1, p_2\}$-Nekrasov matrices ^[9,10], DZT matrices ^[11,12], $S$-$SDD$ matrices ^[13], $S$-$SDDS$ matrices ^[14] and so on. However, the estimation of upper bounds of the infinity norm of inverse for $SDD_1$ matrices has never been reported.

In this paper, a new proof of Theorem 1 is given firstly. Secondly, some properties of $SDD_1$ matrices are presented. Finally, based on the new proof, some upper bounds of the infinity norm of inverse of $SDD_1$ matrices and $SDD$ matrices are obtained. Moreover, it is shown that these new bounds of $SDD$ matrices works better than the well-known Varah bound in some cases, and numerical examples are given to illustrate the corresponding results.

2.   Main results

Firstly, some notations and a lemma are listed.

$D = diag\{d_1, d_2, \ldots, d_n\}$ denotes a diagonal matrix.

$(AD)_{ij}$ denotes the entry $(i, j)$ of matrix $AD$, and $(AD)_{ii}$ denotes the diagonal element of the $i$th row of matrix $AD$.

Lemma 1. If a matrix $A = [a_{ij}]\in {\mathbb{C}}^{n\times n}\; (n\geq 2)$ is an $SDD_1$ matrix if and only if $|a_{ii}| > p_{i}(A)$ for all $i \in N$.

Proof. From Definition 1, we get that $|a_{ii}| > p_i(A)$ for any $i \in N_1(A)$ and for any $i \in N_2(A)$,

thus, we obtain that a matrix $A$ is an $SDD_1$ matrix if and only if $|a_{ii}| > p_{i}(A)$ for all $i \in N$.

Next, a new proof of Theorem 1 is given as follows.

Proof. It is sufficient to prove that each $SDD_1$ matrix $A$ is an $H$-matrix. In order to do that, let us define the diagonal matrix as $D = diag\{d_1, d_2, \ldots, d_n\}$, where

and

if $\sum\limits_{j\in N_{2}(A)\backslash \{i\}} |a_{ij}| = 0,$ then the corresponding fraction is defined to be $\propto.$

Since matrix $A$ is an $SDD_1$ matrix, $D$ is a positive diagonal matrix.

In the following, we prove that $AD$ is an $SDD$ matrix, and divided it into two cases.

Case 1: for any $i \in N_1(A)$, it is easy to obtain that $|(AD)_{ii}| = |a_{ii}|$, and

Case 2: for any $i \in N_2(A)$, we get that $|(AD)_{ii}| = |a_{ii}|(\frac {p_i(A)}{|a_{ii}|}+\varepsilon) = {p_i(A)}+ \varepsilon |a_{ii}|$, and

From Cases 1 and 2, we obtain that $|(AD)_{ii}| > \sum\limits_{\substack{j = 1 \\ j\neq i}}^{n} |a_{ij}| d_j = r_{i}(AD)$ for any $i\in N$, that is, $AD$ is an $SDD$ matrix, then according to the definition of $H$-matrix, $A$ is an $H$-matrix.

Since the definition of $SDD_1$ matrix was proposed, some properties of $SDD_1$ matrices were obtained, such as Schur complements of $SDD_1$ matrices ^[2], subdirect sums of $SDD_1$ matrices ^[15]. Next, some new properties of $SDD_1$ matrices are listed as follows.

Theorem 2. If a matrix $A = [a_{ij}]\in {\mathbb{C}}^{n\times n}\; (n\geq 2)$ is an $SDD_1$ matrix by rows, and $N_{1}(A) \neq \varnothing$, then for each $i\in N_{1}(A)$, there is at least one $a_{ij}\neq 0$, where $j\in N_{2}(A)$ and $j\neq i$.

Proof. Suppose on the contrary that for each $i\in N_{1}(A)$, $a_{ij} = 0$, where $j\in N_{2}(A)$ and $j\neq i$, then it is easy to obtain that $p_{i}(A) = r_{i}(A)$ for any $i\in N_{1}(A)$ from Definition 1, thus we obtain that $|a_{ii}| > p_{i}(A) = r_{i}(A)\leq |a_{ii}|$, which does not hold, hence for each $i\in N_{1}(A)$, there is at least one $a_{ij}\neq 0$, where $j\in N_{2}(A)$ and $j\neq i$.

Theorem 3. If a matrix $A = [a_{ij}]\in {\mathbb{C}}^{n\times n}\; (n\geq 2)$ is an $SDD_1$ matrix by rows, and for each $i\in N_{2}(A)$, there is at least one $a_{ij}\neq 0$, where $j\in N_{2}(A)$ and $j\neq i$, then $|a_{ii}| > p_{i}(A) > 0$ for any $i\in N$ and $|a_{ii}| > r_{i}(A) > p_{i}(A) > 0$ for any $i\in N_{2}(A)$.

Proof. From the Lemma 1, we get that $|a_{ii}| > p_{i}(A)$ for any $i\in N$ and $|a_{ii}| > r_{i}(A)\geq p_{i}(A)$ for all $i\in N_{2}(A)$.

Since $A$ is an $SDD_1$ matrix, and from the condition that for each $i\in N_{2}(A)$, $A$ has at least one $a_{ij}\neq 0$, where $j\in N_{2}(A)$ and $j\neq i$, it is easy to obtain that $|a_{ii}| > r_{i}(A) > p_{i}(A) > 0$ for any $i\in N_{2}(A)$.

We next prove that $|a_{ii}| > p_{i}(A) > 0$ for any $i\in N$, and consider the following two cases separately.

Case 1: if $N_{1}(A) = \varnothing$, then $A$ is an $SDD$ matrix, and from the condition that for each $i\in N_{2}(A)$, $A$ has at least one $a_{ij}\neq 0$, where $j\in N_{2}(A)$ and $j\neq i$, thus it is easy to get $|a_{ii}| > p_{i}(A) > 0$ for any $i\in N = N_{2}(A)$.

Case 2: if $N_{1}(A) \neq \varnothing$, then from Theorem 2 and the condition that for each $i\in N_{2}(A)$, $A$ has at least one $a_{ij}\neq 0$, where $j\in N_{2}(A)$ and $j\neq i$, we obtain that $|a_{ii}| > p_{i}(A) > 0$ for all $i\in N$.

From Cases 1 and 2, we obtain that $|a_{ii}| > p_{i}(A) > 0$ for any $i\in N$.

Theorem 4. Let $A = (a_{ij}) \in {\mathbb{C}}^{n\times n}$ ($n\geq 2$) be an $SDD_1$ matrix by rows, and for each $i\in N_{2}(A)$, $A$ has at least one $a_{ij}\neq 0$, where $j\in N_{2}(A)$ and $j\neq i$, then there exists a diagonal matrix $D = diag\{d_1, d_2, \ldots, d_n\}$, where $d_i = \frac{p_{i}(A)}{|a_{ii}|}, i = 1, 2, \ldots, n$, such that $AD$ is an $SDD$ matrix.

Proof. In order to prove that matrix $AD$ is an $SDD$ matrix, we need to prove that matrix $AD$ satisfies the following inequalities:

Since for each $i\in N_{2}(A)$, there is at least one $a_{ij}\neq 0$, where $j\in N_{2}(A)$ and $j\neq i$, from Theorems 2 and 3, we obtain that $|a_{ii}| > p_{i}(A) > 0$ for any $i\in N$ and $|a_{ii}| > r_{i}(A) > p_{i}(A) > 0$ for all $i\in N_{2}(A)$.

Therefore, for any $i \in N$, it is easy to get $|(AD)_{ii}| = p_i(A)$, and from $0 < \frac{p_{j}(A)} {|a_{jj}|} < \frac{r_{j}(A)} {|a_{jj}|} < 1$ for any $j\in N_2(A)$, Theorems 2 and 3, we get that

Obviously, for any $i\in N$, we get $|(AD)_{ii}| > r_{i}(AD)$, that is, $AD$ is an $SDD$ matrix.

Finally, some upper bounds of the infinity norm of inverse of $SDD_1$ matrices and $SDD$ matrices are established. Before that, a theorem which will be used later is listed.

Theorem 5. (Varah bound) ^[4] Let $A = (a_{ij}) \in {\mathbb{C}}^{n\times n}$ ($n\geq 2$) be an $SDD$ matrix, then

Theorem 6. Let $A = (a_{ij}) \in {\mathbb{C}}^{n\times n}$ ($n\geq 2$) be an $SDD_1$ matrix, then

where

and $\varepsilon$ satisfy inequality (2.3).

Proof. From the new proof of Theorem 1, we obtain that there exists a positive diagonal matrix $D$ such that $AD$ is an $SDD$ matrix, where $D$ is defined as Eq (2.2). Therefore, we have the following inequality:

Since the matrix $D$ is positive diagonal, it is easy to obtain that

where $\varepsilon$ satisfy inequality (2.3).

Since $AD$ is an $SDD$ matrix, by Theorem 5, we obtain

Thus, we get

Based the new proof, the upper bound of the infinity norm of inverse of $SDD_1$ matrix is presented, and since $SDD$ matrices is a subclass of $SDD_1$ matrices, from Theorem 6, it is easy to obtain the following Corollary 1.

Corollary 1. Let $A = (a_{ij}) \in {\mathbb{C}}^{n\times n}$ ($n\geq 2$) be an $SDD$ matrix, then

where

and

Example 2. Considering the following $SDD_1$ matrices

and

Obviously, $A_1$ and $A_2$ are also $SDD$ matrices. By calculation, we have

and

By the Varah bound (2.4) of Theorem 5, we obtain that $||A_1^{-1}||_\infty \leq 1$ and $||A_2^{-1}||_\infty \leq 5$. By the bound (2.6) of Corollary 1, we obtain that $||A_1^{-1}||_\infty \leq \frac{0.25+\varepsilon_1}{0.375+\varepsilon_1}$ (where $0 < \varepsilon_1 < 1$) and $||A_2^{-1}||_\infty \leq 5+\frac{5}{4\varepsilon_2}$(where $0 < \varepsilon_2 < 1.5$). In fact, $||A_1^{-1}||_\infty \approx 0.4434$ and $||A_2^{-1}||_\infty = 5$. Obviously, for the matrix $A_1$, it is easy to obtain that $||A_1^{-1}||_\infty \approx 0.4434 < \frac{0.25+\varepsilon_1}{0.375+\varepsilon_1} < 1$ for any the number $0 < \varepsilon_1 < 1$. However, for the matrix $A_2$, we have that $||A_2^{-1}||_\infty = 5 < 5+\frac{5}{4\varepsilon_2}$ for any the number $0 < \varepsilon_2 < 1.5$, which means that the bound in Corollary 1 is better than the Varah bound in Theorem 5 in some cases. Then, a meaningful discussion is concerned: under what conditions, the bound in Corollary 1 is better than the Varah bound in Theorem 5.

The following Theorem 7 shows that the bound in Corollary 1 is better than in Theorem 5 in some conditions.

Theorem 7. Let $A = (a_{ij}) \in {\mathbb{C}}^{n\times n}$ ($n\geq 2$) be an $SDD$ matrix, if

then

where $M_i$ is given as in Eq (2.7) and $\varepsilon$ satisfy inequality (2.8).

Proof. From the condition

it is easy to obtain that

thus, from combining similar terms at the left end of the above inequality, we obtain the following inequality

Since $A$ is an $SDD$ matrix, we have

Therefore, from inequality (2.9), it is easy to have

and thus from Corollary 1, we have

The following Example 3 also illustrates the Theorem 7.

Example 3. This is the previous Example 2. For the matrix $A_1$, by a simple calculation, we obtain

thus,

It is easy to verify that

that is, the matrix $A_1$ satisfies the conditions of Theorem 7. Therefore, from Theorem 7, we obtain that for any $0 < \varepsilon_1 < 1$,

However, the upper bound (2.5) contains the parameter $\varepsilon$. Next, based on the Theorem 4, a upper bound of the infinity norm of inverse of $SDD_1$ matrices is presented as follows, and this upper bound only depends on the elements of given matrices.

Theorem 8. Let $A = (a_{ij}) \in {\mathbb{C}}^{n\times n}$ ($n\geq 2$) be an $SDD_1$ matrix, and for each $i\in N_{2}(A)$, there is at least one $a_{ij}\neq 0$, where $j\in N_{2}(A)$ and $j\neq i$, then

Proof. By Theorem 4, we obtain that there exists a positive diagonal matrix $D$ such that $AD$ is an $SDD$ matrix, where $D$ is defined as Theorem 4. Therefore, we get the following inequality:

Since the matrix $D$ is positive diagonal, it is easy to obtain that

Since $AD$ is an $SDD$ matrix, by Theorem 5, we obtain

Thus, we get that

Since $SDD$ matrices is a subclass of $SDD_1$ matrices, from Theorem 8, it is easy to obtain the following corollary.

Corollary 2. Let $A = (a_{ij}) \in {\mathbb{C}}^{n\times n}$ ($n\geq 2$) be an $SDD$ matrix, if $r_i(A)\neq 0$ for all $i\in N$, then

The following Theorems 9 and 10 show that the bound in Corollary 2 is better than in Theorem 5 in some conditions.

Theorem 9. Let $A = (a_{ij}) \in {\mathbb{C}}^{n\times n}$ ($n\geq 2$) be an $SDD$ matrix, if $r_i(A)\neq 0$ for all $i\in N$ and

then

Proof. Since $A$ is an $SDD$ matrix, it is easy to get that

thus

and from the condition

we obtain

Therefore, from Corollary 2, we get

The following Example 4 also illustrates the Theorem 9.

Example 4. Considering the following $SDD$ matrix

By the Varah bound (2.4) of Theorem 5, we obtain that $||A_3^{-1}||_\infty \leq 10$.

By a simple calculation, we obtain

then,

thus,

It is easy to verify that

Therefore, the matrix $A_3$ satisfies the conditions of Theorem 9, thus from the bound of Theorem 9, we obtain

In fact, $||A_3^{-1}||_\infty \approx 0.9480$. Obviously, $||A_3^{-1}||_\infty \approx 0.9480 < 4.1103 < 10$, which means that the bound in Corollary 2 is better than Varah bound of Theorem 5 in some conditions.

Theorem 10. Let $A = (a_{ij}) \in {\mathbb{C}}^{n\times n}$ ($n\geq 2$) be an $SDD$ matrix, if $r_i(A)\neq 0$ for all $i\in N$ and

then

Proof. Since $A$ is an $SDD$ matrix, we have

From the condition $r_i(A)\neq 0$ for all $i\in N$ and Theorem 4, it is easy to obtain that

Therefore, from the condition

we obtain

and thus from Corollary 2, we get

The following Example 5 also illustrates the Theorem 10.

Example 5. Considering the following the following $SDD$ matrix

By the Varah bound (2.4) of Theorem 5, we obtain that $||A_4^{-1}||_\infty \leq 1$.

By calculation, we obtain that

then,

thus,

It is easy to verify that

that is, the matrix $A_4$ satisfies the conditions of Theorem 10, thus by the bound of Theorem 10, we obtain

In fact, $||A_4^{-1}||_\infty \approx 0.4019$. Obviously, $||A_4^{-1}||_\infty\approx 0.4019 < 0.6667 < 1$, which means that the bound in Corollary 2 is better than Varah bound of Theorem 5 in some conditions.

3.   Conclusions

In this paper, a new proof that $SDD_1$ matrices is a subclass of $H$-matrices is given and based on the new proof, some upper bounds of the infinity norm of inverse of $SDD_1$ matrices are established, and some new upper bounds of the infinity norm of inverse of $SDD$ matrices are also obtained. Moreover, we show that these new upper bounds of the infinity norm of inverse of $SDD$ matrices are better than well-known Varah bound under some cases. In addition, some numerical examples are given to illustrate the corresponding results.

Acknowledgments

This work is partly supported by the National Natural Science Foundations of China (31600299), Natural Science Basic Research Program of Shaanxi, China (2020JM-622); the Scientific Research Program Funded by Shaanxi Provincial Education Department (18JK0044); the Science and Technology Project of Baoji (2017JH2-24); the Key Project of Baoji University of Arts and Sciences (ZK16050) and the Postgraduate Innovative Research Project of Baoji University of Arts and Sciences (YJSCX20ZD05).

Conflict of interest

The authors declare that they have no competing interests.