Abstract
A new upper bound for the infinity norm for the inverse of \(\{P_{1},P _{2}\}\)-Nekrasov matrices is given. It is proved that the upper bound is sharper than those in Cvetković et al. (Open Math. 13:96–105, 2015) and than well-known Varah’s bound for strictly diagonally dominant matrices. Numerical examples are given to illustrate the corresponding results.
Similar content being viewed by others
1 Introduction
By \(\mathbb{C}^{n\times n}(\mathbb{R}^{n\times n})\) we denote the set of all complex (real) matrices of order n. A matrix \(A=[a_{ij}] \in \mathbb{C}^{n\times n}\) is called an H-matrix if its comparison matrix \(\langle A\rangle =[m_{ij}]\in \mathbb{R}^{n\times n}\) defined by
is a nonsingular M-matrix, i.e., \(\langle A\rangle ^{-1}\geq 0\) [1, 8, 20].
It is well known that H-matrices are widely used in many subjects such as numerical algebra, the control system, mathematical physics, economics, and dynamical system theory [1, 2, 4, 20]. An important problem among them is to find upper bounds for the infinity norm of the inverse of H-matrices, because it can be used to the convergence analysis of matrix splitting and matrix multi-splitting iterative methods for solving large sparse systems of linear equations [18], as well as linear complementarity problems [10,11,12,13, 19]. For example, when solving linear systems in practice, it is important to have an economical method for estimating the condition number \(\kappa (A)\) of the matrix of coefficients, which shows how ‘ill’ the systems could be. Here, the condition number is defined in the following way:
as the product of a matrix norm and a norm of its inverse. Hence, it can be useful to determine the upper bound for the norm of the inverse matrix without calculating the inverse.
In 1975, Varah provided a simple and elegant upper bound for the infinity norm of the inverse of strictly diagonally dominant (SDD) matrices as one of the most important subclass of H-matrices. Here a matrix \(A=[a_{ij}]\in \mathbb{C}^{n\times n}\) is said to be an SDD matrix if, for each \(i\in N:=\{1,2,\ldots ,n\}\),
where \(r_{i}(A)=\sum_{j\neq i} |a_{ij}|\).
Theorem 1
([17])
If \(A=[a_{ij}]\in \mathbb{C}^{n\times n}\) is SDD, then
Bound (1) is usually called Varah’s bound and works only for SDD matrices. Moreover, when the class of involved matrices is a wider subclass of H-matrices, such as doubly strictly diagonally dominant (DSDD) matrices, S-SDD matrices, weakly chained diagonally dominant matrices, Nekrasov matrices, S-Nekrasov matrices, and DZ-type matrices, upper bounds for \(\|A^{-1}\|_{\infty }\) are derived, which sometimes are tighter in the SDD case, see [3, 5, 7, 9, 10, 15, 16, 21] and the references therein. Recently, Cvetković et al. [6] presented two upper bounds for \(\|A^{-1}\|_{\infty }\) involved with \(\{P_{1},P_{2}\}\)-Nekrasov matrices, which are only dependent on the entries of the matrix A.
In this paper, we give a new upper bound for the infinity norm of the inverse of \(\{P_{1},P_{2}\}\)-Nekrasov matrices. It is shown by the comparison theorems that the new bound improves corresponding bounds of Cvetković et al. (2015) for \(\{P_{1},P_{2}\}\)-Nekrasov matrices and improves well-known Varah’s bound for strictly diagonally dominant matrices. The tested numerical examples show that the new bound is tighter than those derived recently.
2 Main results
First, some notation and definitions are listed. Given a matrix \(A=[a_{ij}]\in \mathbb{C}^{n\times n}\), denote
and
Next, we recall the concept of \(\{P_{1}, P_{2}\}\)-Nekrasov matrices.
Definition 1
([14])
A matrix \(A=[a_{ij}]\in \mathbb{C}^{n\times n}\) is called a Nekrasov matrix if, for each \(i\in N\),
Motivated by Definition 1, Cvetković et al. in [6] presented the following new subclass of H-matrices, called \(\{P_{1},P_{2}\}\)-Nekrasov matrices, which contains Nekrasov matrices.
Definition 2
([6])
Given two permutation matrices \(P_{1}\) and \(P_{2}\), a matrix \(A=[a_{ij}]\in \mathbb{C}^{n\times n}\), \(n\geq 2\), is called a \(\{P_{1},P_{2}\}\)-Nekrasov matrix if
where
with
in which \(h_{i}(P_{k}^{T}AP_{k})\), \(i\in N\), being defined as (4).
Remark here that if \(P_{1}=P_{2}=I\), where I is an identity matrix, then \(h^{P_{1}}(A)=h^{P_{2}}(A)=h(A)\), which implies that a Nekrasov matrix is a \(\{P_{1},P_{2}\}\)-Nekrasov matrix for \(P_{1}=P_{2}=I\). In addition, note that for any permutation matrix P, the matrix \(P^{T}AP\) has the same set of diagonal entries as does A and, moreover, the same set of row sums as does A. Hence, if A is an SDD matrix, then \(|a_{ii}|>r_{i}(A)>h_{i}^{P_{k}}(A)\) holds for all \(i\in N\), which means that an SDD matrix is a \(\{P_{1},P_{2}\}\)-Nekrasov matrix for any \(\{P_{1},P_{2}\}\).
Next, we recall two upper bounds for the infinity norm of the inverse of \(\{P_{1},P_{2}\}\)-Nekrasov matrices which are given by Cvetković et al. in [6].
Theorem 2
([6])
Given a set of permutation matrices \(\{P_{1},P_{2}\}\), let \(A=[a_{ij}] \in \mathbb{C}^{n\times n}\) be a \(\{P_{1},P_{2}\}\)-Nekrasov matrix. Then
and
where \(z^{P_{k_{i}}}(A)=P_{k_{i}}z(P_{k_{i}}^{T}AP_{k_{i}})=[z_{i} ^{P_{k_{i}}}(A),\ldots ,z_{n}^{P_{k_{i}}}(A)]^{T}\) with \(z(P_{k_{i}} ^{T}AP_{k_{i}})\) being defined as (3), \(h_{i}^{P_{1}}(A)\) and \(h_{i}^{P_{2}}(A)\) are given by Definition 2, and for each index i, the corresponding index \(k_{i}\in \{1,2\}\) is chosen in such a way that
In what follows, we give a new upper bound for the infinity norm of the inverse of \(\{P_{1},P_{2}\}\)-Nekrasov matrices. Before that, some lemmas and notation which will be used later are listed.
Given a matrix \(A=[a_{ij}]\in \mathbb{C}^{n\times n}\), by \(A=D-L- U\) we denote the standard splitting of A into its diagonal \((D)\), strictly lower \((-L)\), and strictly upper \((-U)\) triangular parts, and \(|A|=[|a_{ij}|]\).
Given a \(\{P_{1},P_{2}\}\)-Nekrasov matrix \(A=[a_{ij}]\in \mathbb{C} ^{n\times n}\), \(n\geq 2\), we recall two special matrices \(C\in \mathbb{C}^{n\times n}\) and \(\widetilde{C}\in \mathbb{C}^{n\times n}\) as follows:
where
and
with \(e_{i}=(0,\ldots ,1,\ldots ,0)^{T}\) and for each index i, the corresponding index \(k_{i}\in \{1,2\}\) is chosen in the same way given in Theorem 2.
Lemma 1
([6])
Let \(A=[a_{ij}]\in \mathbb{C}^{n\times n}\), \(n\geq 2\), be a \(\{P_{1},P_{2}\}\)-Nekrasov matrix, then the matrix \(I-C\) is an SDD matrix, where I is the identify matrix and C is defined as in (7).
Lemma 2
([1])
Let \(A=[a_{ij}]\in \mathbb{C}^{n\times n}\) be a nonsingular H-matrix. Then
Lemma 3
([6])
Given any \(A=[a_{ij}]\in \mathbb{C}^{n\times n}\), \(n\geq 2\), with \(a_{ii}\neq 0\) for all \(i\in N\), and given a permutation matrix \(P\in \mathbb{R}^{n\times n}\), then
where \(e=(1,1,\ldots ,1)^{T}\) and \(P^{T}AP=\widetilde{D}- \widetilde{L}-\widetilde{U}\) is the standard splitting of the matrix \(P^{T}AP\).
The following lemma will be used in the proof of Theorem 3.
Lemma 4
Let \(A=[a_{ij}]\in \mathbb{C}^{n\times n}\) with \(a_{ii}\neq 0\) for all \(i\in N\), and \(P\in \mathbb{R}^{n\times n}\) is a permutation matrix. Then
where \(z^{P}(A)=Pz(P^{T}AP)\) with \(z(P^{T}AP)\) being defined as (3), \(P^{T}AP=\widetilde{D}-\widetilde{L}-\widetilde{U}\) is the standard splitting of the matrix \(P^{T}AP\), and \(e=(1,1,\ldots ,1)^{T}\).
Proof
Let \(x:=(\widetilde{D}-\widetilde{L})^{-1}e=(x_{1},x_{2},\ldots ,x _{n})^{T}\). Then
i.e.,
By (8), we have
which implies that
Therefore,
Note that \(|\widetilde{D}|=P^{T}|D|P\) and \(P^{T}P=I\), we can see that
This completes the proof. □
Now, we give the main result of this paper by Lemmas 1, 2, 3, and 4.
Theorem 3
Let \(A=[a_{ij}]\in \mathbb{C}^{n\times n}\), \(n\geq 2\), be a \(\{P_{1},P _{2}\}\)-Nekrasov matrix. Then
where \(z_{i}^{P_{k_{i}}}(A)\) and \(h_{i}^{P_{k_{i}}}(A)\), \(i \in N\), \(k _{i}\in \{1,2\}\) are given by Theorem 2.
Proof
Since \(A=[a_{ij}]\in \mathbb{C}^{n\times n}\) is a \(\{P_{1},P_{2}\}\)-Nekrasov matrix, then from Lemma 1 we have
is an SDD matrix, where C is given by (7). By the proof of Theorem 3.1 (see[6]), we have that, for a fixed \(k\in \{1,2 \}\),
which implies that
where
Since a \(\{P_{1},P_{2}\}\)-Nekrasov matrix is an H-matrix, we have from Lemma 2 that
First, we estimate \(\|\triangle ^{-1}\widetilde{C}\|_{\infty }\). Because \(|D_{k_{i}}|-|L_{k_{i}}|\) for \(k_{i}\in \{1,2\}\) is an M-matrix, so we can take a positive diagonal matrix \(\triangle =\operatorname{diag}(\delta _{1}, \delta _{2},\ldots ,\delta _{n})\) with
Note that
where
It follows from (12) that
Next, we estimate \(\|B^{-1}\triangle \|_{\infty }\). Observe that \(B:=I-C\), where C is given by (7). Then, for each \(i\in N\), we have
By Lemma 1, we have B is an SDD matrix. Since \(\triangle ^{-1}\) is a positive diagonal matrix, it holds that \(\triangle ^{-1}B\) is also an SDD matrix. Hence, applying Varah’s bound (1), we have
By Lemma 4, we have
which together with (12) implies that
Hence,
where \(k_{i}\in \{1,2\}\) is chosen in such a way that
Now, the conclusion follows from (11), (13), and (14). □
The following comparison theorem shows that bound (9) of Theorem 3 is better than bounds (5) and (6) of Theorem 2 (bound (8) of Theorem 3.1 and bound (10) of Theorem 3.2 in [6]).
Theorem 4
Let \(A=[a_{ij}]\in \mathbb{C}^{n\times n}\), \(n\geq 2\), be a \(\{P_{1},P _{2}\}\)-Nekrasov matrix. Then
and
Furthermore, equality in (15) holds if and only if, for certain \(l\in N\), the following two conditions hold:
and
Similarly, equality in (16) holds if and only if, for certain \(l\in N\), the following two conditions hold:
and
Proof
It is easy to see that inequality in (15) holds, and the inequality in (16) also holds if we use the following relation:
Next, we prove that the case of equality in (16) holds if and only if (17) and (18) hold. Suppose that
Note that
Therefore,
Since
it follows from (21) that
which implies (17) holds, and thus (18) holds from (17) and (19).
Conversely, if conditions (17) and (18) hold for some \(l\in N\), then we have
this implies that the equality in (16) holds. The equality in (15) can also be proved in a similar way. The proof is completed. □
Since an SDD matrix is a \(\{P_{1},P_{2}\}\)-Nekrasov matrix, by Theorem 3, a new upper bound for \(\|A^{-1}\|_{\infty }\) when A is an SDD matrix can be obtained. As expected, the following theorem shows that this new bound works better than Varah’s bound of Theorem 1.
Theorem 5
Let \(A=[a_{ij}]\in \mathbb{C}^{n\times n}\) be an SDD matrix. Then, for any set of permutation matrices \(\{P_{1},P_{2}\}\),
Furthermore,
Proof
Since an SDD matrix is a \(\{P_{1},P_{2}\}\)-Nekrasov matrix for any permutation matrices \(P_{1}\) and \(P_{2}\), so (20) directly follows from Theorem 2. We next prove that (21) holds.
Let \(d:=d(A)e=|D|e\) and \(P_{k_{i}}^{T}AP_{k_{i}}=D_{k_{i}}-U_{k_{i}}-L _{k_{i}}\) be the standard splitting of the matrix \(P_{k_{i}}^{T}AP _{k_{i}}\) for \(k_{i}\in \{1,2\}\). Then, by Lemma 3, Lemma 4, and \(\langle P_{k_{i}}^{T}AP_{k_{i}}\rangle =|D_{k_{i}}|-|U_{k_{i}}|-|L _{k_{i}}|\), we have
which implies that
It is easy to see that, for a given permutation matrix \(P_{k_{i}}\), the matrix \(P_{k_{i}}^{T}AP_{k_{i}}\) has the same set of diagonal entries as does A and the same set of row (and column) sums as does A. Therefore,
which together with (22) implies that
This completes the proof. □
3 Numerical examples
In this section, we give the numerical example to show that bound (9) in Theorem 3 improves bounds (5) and (6) of Theorem 2, and Varah’s bound of Theorem 1.
Example 1
Consider the following matrices in [6]:
Obviously, \(A_{1}\) is an SDD matrix, and thus it is a \(\{P_{1},P _{2}\}\)-Nekrasov matrix for any set of permutations \(\{P_{1},P_{2}\}\). As reported in [6], \(A_{2}\) is a Nekrasov matrix and \(A_{3}\) is neither SDD nor Nekrasov matrix, but they are both \(\{P_{1},P_{2}\}\)-Nekrasov matrices for choosing identical permutation \(P_{1}\) and counteridentical permutation \(P_{2}\). Hence, by bound (1) of Theorem 1, bounds (5) and (6) of Theorem 2, and bound (9) of Theorem 3, we can compute the upper bounds for the infinity norm of the inverse of \(A_{i}\), \(i=1,2,3\), which are shown in Table 1 (in Table 1 we call bounds (5) and (6) \(\{P_{1},P_{2}\}\)-Nek I and \(\{P_{1},P_{2}\}\)-Nek II).
It can be seen from Table 1 that bound (9) in Theorem 3 is better than Varah’s bound for strictly diagonally dominant matrices, and it is also better than (5) and (6) in Theorem 2 (Theorem 3.1 and Theorem 3.2 in [6]) for \(\{P_{1},P_{2}\}\)-Nekrasov matrices.
4 Conclusions
In this paper, we presented a new upper bound for the infinity norm of the inverse of \(\{P_{1},P_{2}\}\)-Nekrasov matrices and proved that the new bound improves those bounds obtained in [6] for \(\{P_{1},P_{2}\}\)-Nekrasov matrices and well-known Varah’s bound for strictly diagonally dominant matrices. Numerical examples were included to illustrate the corresponding results.
References
Berman, A., Plemmons, R.J.: Nonnegative Matrices in the Mathematical Sciences. Academic Press, New York (1979)
Cvetković, L.: H-Matrix theory vs. eigenvalue localization. Numer. Algorithms 42, 229–245 (2006)
Cvetković, L., Dai, P.F., Doroslovačkic, K., Li, Y.T.: Infinity norm bounds for the inverse of Nekrasov matrices. Appl. Math. Comput. 219, 5020–5024 (2013)
Cvetković, L., Kostić, V., Bru, R., Pedroche, F.: A simple generalization of Gers̆gorin’s theorem. Adv. Comput. Math. 35, 271–280 (2011)
Cvetković, L., Kostić, V., Doroslovačkic, K.: Max-norm bounds for the inverse of S-Nekrasov matrices. Appl. Math. Comput. 218, 9498–9503 (2012)
Cvetković, L., Kostić, V., Doroslovačkic, N.: Generalizations of Nekrasov matrices and applications. Open Math. 13, 96–105 (2015)
Kolotilina, L.Y.: On bounding inverse to Nekrasov matrices in the infinity norm. Zap. Nauč. Semin. POMI 419, 111–120 (2013)
Kostć, V.R.: On general principles of eigenvalue localizations via diagonal dominance. Adv. Comput. Math. 41, 55–75 (2015)
Kostić, V.R., Cvetković, L., Cvetković, L.: Pseudospectra localizations and their applications. Numer. Linear Algebra Appl. 23, 356–372 (2016)
Li, C., Cvetković, L., Wei, Y., Zhao, J.X.: An infinity norm bound for the inverse of Dashnic–Zusmanovich type matrices with applications. Linear Algebra Appl. 565, 99–122 (2019)
Li, C., Dai, P.F., Li, Y.T.: New error bounds for linear complementarity problems of Nekrasov matrices and B-Nekrasov matrices. Numer. Algorithms 74(4), 997–1009 (2017)
Li, C., Li, Y.T.: Weakly chained diagonally dominant B-matrices and error bounds for linear complementarity problems. Numer. Algorithms 73(4), 985–998 (2016)
Li, C., Li, Y.T.: Note on error bounds for linear complementarity problems for B-matrices. Appl. Math. Lett. 57, 108–113 (2016)
Li, W.: On Nekrasov matrices. Linear Algebra Appl. 281, 87–96 (1998)
Li, W.: The infinity norm bound for the inverse of nonsingular diagonal dominant matrices. Appl. Math. Lett. 21, 258–263 (2008)
Morǎca, N.: Upper bounds for the infinity norm of the inverse of SDD and S-SDD matrices. J. Comput. Appl. Math. 206, 666–678 (2007)
Varah, J.M.: A lower bound for the smallest singular value of a matrix. Linear Algebra Appl. 11, 3–5 (1975)
Varga, R.S.: Matrix Iterative Analysis, 2nd revised and expanded edn. Springer Series in Computational Mathematics. Springer, Berlin (2000)
Wang, F.: Error bounds for linear complementarity problems of weakly chained diagonally dominant B-matrices. J. Inequal. Appl. 2017, 33 (2017)
Zhang, C.Y.: New Advances in Research on H-Matrices. Science Press, Beijing (2017)
Zhao, J., Liu, Q., Li, C., Li, Y.T.: Dashnic–Zusmanovich type matrices: a new subclass of nonsingular H-matrices. Linear Algebra Appl. 552, 277–287 (2018)
Acknowledgements
The authors would like to thank referees and the editor for their important comments and suggestions, which substantially improved the manuscript.
Funding
This work is partly supported by National Natural Science Foundations of China (31600299); the Scientific Research Program Funded by Shaanxi Provincial Education Department (18JK0044); the Scientific Research Program Funded by Yunnan Provincial Education Department (2019J0910); the Science and Technology Project of Baoji (2017JH2-21, 2017JH2-24); the Key Project of Baoji University of Arts and Sciences (ZK2017021, ZK16050).
Author information
Authors and Affiliations
Contributions
All authors contributed equally to this work. All authors read and approved the final manuscript.
Corresponding author
Ethics declarations
Competing interests
The authors declare that they have no competing interests.
Additional information
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
About this article
Cite this article
Wang, Y., Gao, L. An improvement of the infinity norm bound for the inverse of \(\{P_{1},P_{2}\}\)-Nekrasov matrices. J Inequal Appl 2019, 177 (2019). https://doi.org/10.1186/s13660-019-2134-3
Received:
Accepted:
Published:
DOI: https://doi.org/10.1186/s13660-019-2134-3