PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 101(115) (2017), 65–73 https://doi.org/10.2298/PIM1715065M

CHARACTERIZATION OF DIAGONALLY DOMINANT H-MATRICES

Nenad Morača

Abstract. We show that the diagonal dominance nonsingularity result of Shivakumar and Chew from 1974, and the diagonal dominance nonsingularity result of Farid from 1995, and the result of Huang on characterization of diagonally dominant H-matrices from 1995, all proven independently and in different contexts are, in fact, equivalent. We also offer the fourth and the fifth simpler equivalent conditions, for a diagonally dominant matrix to be an H-matrix.

1. Introduction

M- and H-matrices were introduced in 1937 in the seminal paper of Ostrowski [11]. By naming them M- and H-matrices, Ostrowski paid homage to his teacher Minkowski and to Hadamard, men who had inspired Ostrowski’s work in the matrix theory. M- and H-matrices have proven to be an exceptionally useful tool in linear algebra and numerical mathematics. They play fundamentally important role in the theory of iterative methods for solving systems of linear equations (see [1, Chapter 7] and [2]). For applications in the probability theory (Markov chains) see [1, Chapter 8], for applications in economics (input-output analysis) see [1, Chapter 9], and for applications in mathematical programming (linear complementarity problem) see [1, Chapter 10]. M- and H-matrices also play fundamentally important role in the localization of the eigenvalues of a given matrix (see [14] and [8]). Subclasses of M- and H-matrices admit various bounds for the norm of the matrix inverse, and thus also for the conditional number and the smallest singular value, (see [9,10,16]), which makes them a useful tool in various branches of numerical mathematics, for example numerical solving of differential equations.

One can find 50 equivalent definitions of the class of M-matrices in [1, Chapter 6]. Some additional equivalent definitions can be found in [15]. Varga assumes in [14, Appendix C, page 204] that there are more than 70 equivalent definitions of the class of M-matrices in the literature. H-matrices are a simple and natural generalization of the class of M-matrices and the class of strictly diagonally dominant (SDD) matrices (see the next section).

2010 Mathematics Subject Classification: 65F15; 65F99.

Key words and phrases: diagonal dominance, nonsingularity results, M-matrices, H-matrices, matrix digraph.

Supported by the Ministry of Education and Science, Republic of Serbia, through the project “Set Theory, Model Theory and Set-Theoretic Topology", Project No. 174006.

Communicated by Zoran Petrović.

The main result of this paper is contained in Theorem 3.1. There, the equivalence of the diagonal dominance nonsingularity result of Shivakumar and Chew from 1974 [12], and the diagonal dominance nonsingularity result of Farid from 1995 [4], and the result of Huang on characterization of diagonally dominant H-matrices from 1995 [7], all proven independently and in different contexts, is established. Also, two new and simpler characterizations of diagonally dominant H-matrices are obtained. All the results in this paper are formulated in terms of H-matrices, however it is easy to reformulate them in terms of the smaller but more well known class of M-matrices.

2. Preliminaries

Throughout the paper, for a matrix A = [a_{ij} ] ∈ ℂ^{n×n} , we use the following notation:

N : = {1, 2, …, n}, the set of all indices,
\overline{S} : = N ∖ S, the complement of S ⊆ N,
r_{i}(A) : = ∑_{j∈N∖{i}} |a_{ij} |, deleted ith row sum of the matrix A,
r_{i}^{S}(A) : = ∑_{j∈S∖{i}} |a_{ij} |, part of the previous sum, corresponding to the set S ⊆ N.

Obviously, for arbitrary nonempty proper subset S of N and for each index i ∈ N, we have

r_{i}(A) = r_{i}^{S}(A) + r\overline{S} ; i(A).

Let A|_{S^{2}} denote the principal submatrix of a matrix A, which corresponds to a set S of indices.

2.1. Matrix digraph, irreducibility and Frobenius normal form. For a given matrix A = [a_{ij} ] ∈ ℂ^{n×n} , we construct its directed graph 𝔾(A) in the following way (for more details see [14, Chapter 1, page 12]). The set of vertices of 𝔾(A) is {v_{1}, v_{2}, …, v_{n}}, consisting of any n distinct points. For any nonzero entry a_{ij} of A, connect the vertex v_{i} to the vertex v_{j} by means of a directed arc \overrightarrow{v_{i}v_{j}}, directed from the initial vertex v_{i} to the terminal vertex v_{j}. If a_{ii} ≠ 0, then \overrightarrow{v_{i}v_{i}} is a loop. A directed path in 𝔾(A) is a collection of abutting directed arcs \overrightarrow{v_{i_{0}} v_{i_{1}}}, \overrightarrow{v_{i_{1}} v_{i_{2}}}, …, \overrightarrow{v_{i_{k−1}} v_{i_{k}}}, connecting the initial vertex v_{i_{0}} to the terminal vertex v_{i_{k}} . The directed graph 𝔾(A) is strongly connected if, for each ordered pair v_{i} and v_{j} of vertices, there is a directed path in 𝔾(A) connecting the initial vertex v_{i} to the terminal vertex v_{j}.

We say that a matrix A ∈ ℂ^{n×n} , n ⩾ 2, is reducible if there exists a permutation matrix P ∈ ℝ^{n×n} and a positive integer r, with 1 ⩽ r < n, for which

P AP^{T} = [ \begin{matrix}A_{11} & A_{12} \\ O & A_{22} \end{matrix}]

where A_{1} ∈ ℂ^{r×r} and A_{2} ∈ ℂ^{(n−r)×(n−r)} . Otherwise, we say that A is irreducible. It is easy to prove that a matrix A is irreducible if and only if its directed graph 𝔾(A) is strongly connected.

For any matrix A ∈ ℂ^{n×n} , n ⩾ 2, there exists a permuation matrix P ∈ ℝ^{n×n} and a positive integer m, with 1 ⩽ m ⩽ n such that

P AP^{T} = [ \begin{matrix}R_{11} & R_{12} & ⋯ & R_{1m} \\ 0 & R_{22} & ⋯ & R_{2m} \\ ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & ⋯ & R_{mm} \end{matrix} ] ,

where each matrix R_{jj} , j ∈ {1, 2, …, m}, is either a 1 × 1 matrix, or an n_{j} × n_{j} irreducible matrix with n_{j} ⩾ 2. The above matrix is called the Frobenius normal form of A (see [14, Chapter 1, page 11]). Notice that the Frobenius normal form of A is not unique.

2.2. Diagonal dominance and nonsingularity results. We say that a matrix A ∈ ℂ^{n×n} , n ⩾ 2, is SDD (strictly diagonally dominant) if

|a_{ii} | > r_{i}(A) for all i ∈ N,

that it is DD (diagonally dominant) if

|a_{ii} | ⩾ r_{i}(A) for all i ∈ N,

and that it is DD+ if it is DD, and there exist i ∈ N such that |a_{ii} | > r_{i}(A). With T (A) we denote the set of indices of non-SDD rows of a matrix A,

T (A) := {i ∈ N | |a_{ii} | ⩽ r_{i}(A)}.

Since computing determinants is costly, easily checkable nonsingularity results are of interest in applied linear algebra. The following proposition contains the oldest and the simplest among such results, based on the diagonal dominance. It was proven independently by many mathematicians: Levy (1881), Desplanques (1887), Minkowski (1900) and Hadamard (1903).

Proposition 2.1. If a matrix A ∈ ℂ^{n×n} , n ⩾ 2, is SDD, then A is nonsingular.

In 1931 Geršgorin proved in his seminal paper on eigenvalue localization [6] that DD+ matrices are nonsingular. However, the statement turned out to be incorrect. For example, the matrix A = [ \begin{matrix}1 & 0 \\ 0 & 0 \end{matrix} ] is DD+ and singular. The mistake was corrected in 1949 by Taussky [13] by using the notion of irreducibility.

Proposition 2.2. If a matrix A ∈ ℂ^{n×n} , n ⩾ 2, is irreducible and DD+, then A is nonsingular.

In 1974 Shivakumar and Chew gave the following extension of both Proposition 2.1 and Proposition 2.2.

Proposition 2.3. Let A = [a_{ij} ] ∈ ℂ^{n×n} , n ⩾ 2, be a DD matrix such that T (A) = ∅, or for each i_{0} ∈ T (A) there exists a nonzero elements chain of the form a_{i_{0} i_{1}} , a_{i_{1} i_{2}} , …, a_{i_{r−1} i_{r}} , with i_{r} ∈ \overline{T (A)}. Then A is nonsingular.

The nonzero elements chains of A, means that from every i ∈ T (A) there exists a path to some j ∈ \overline{T (A)}in the directed graph 𝔾(A), associated to the matrix A.

Before stating Farid’s result, we need the following definition.

Definition 2.1. Let A = [a_{ij} ] ∈ ℂ^{n×n} , n ⩾ 2, and let S be a proper subset of N. We say that the set S is interwoven for the matrix A if |S| ⩽ 1, or |S| = s > 1 and there exist different numbers p_{1}, p_{2}, …, p_{s−1} ∈ S, as well as numbers q_{1}, q_{2}, …, q_{s−1} (not obligatory different), such that q_{1} ∈ \overline{S}, a_{p_{1} q_{1}} ≠ 0 and q_{i} ∈ \overline{S} ∪ \{p_{1}, p_{2}, …, p_{i−1} \}, a_{p_{i} q_{i}} ≠ 0, for every i ∈ \{2, 3, …, s − 1\}.

Farid independently obtained the following extension of both Proposition 2.1 and Proposition 2.2 in 1995 [4].

Proposition 2.4. Let A = [a_{ij} ] ∈ ℂ^{n×n} , n ⩾ 2, be a DD matrix with nonzero diagonal entries, such that T (A) is an interwoven set of indices for A. Then A is nonsingular.

2.3. M- and H-matrices. We shall say that a matrix A = [a_{ij} ] ∈ ℝ^{n×n} has the L-form if a_{ii} > 0 for i ∈ N and a_{ij} ⩽ 0 for i, j ∈ N, i ≠ j.

Definition 2.2. A matrix A which has the L-form is an M-matrix if it is nonsingular and A^{−1} is a nonnegative matrix.

Given any A ∈ ℂ^{n×n} , let M(A) = [α_{ij} ] ∈ ℝ^{n×n} denote its comparison matrix, i.e.,

α_{ii} : = |a_{ii} |, for all i ∈ N,
α_{ij} : = −|a_{ij} |, for all i, j ∈ N, i ≠ j.

Definition 2.3. A matrix A ∈ ℂ^{n×n} is an H-matrix if its comparison matrix M(A) is an M-matrix.

Therefore, H-matrices are a generalization of M-matrices, and we have that A is an H-matrix if and only if A^{T} is. The following characterization shows that H-matrices are also a generalization of SDD matrices.

Proposition 2.5. A matrix A ∈ ℂ^{n×n} is an H-matrix if and only if there exists a nonsingular diagonal matrix D such that AD is an SDD matrix.

As a consequnce, we obtain that H-matrices are nonsingular, and that each H-matrix has at least one SDD row (and column). The nonsingularity result of Taussky (Proposition 2.2) can actually be strengthened.

Proposition 2.6. If a matrix A ∈ ℂ^{n×n} , n ⩾ 2, is irreducible and DD+, then A is an H-matrix.

Proof. If A is an irreducible DD+ matrix, let M(A) = D − B, where D = diag(|a_{11}|, |a_{22}|, …, |a_{nn} |). Then B ⩾ 0, and D > 0 because irreducible DD+ matrices have nonzero diagonal entries.We have that D^{−1} B ⩾ 0 and that ρ(D^{−1} B)<1 . Assume contrary, that ρ(D^{−1} B) ⩾ 1 and take eigenvalue λ ∈ σ(D^{−1} B) such that |λ| ⩾ 1. Then det(λD − B) = 0, and λD − B is irreducible DD+, which is a contradiction with Proposition 2.2. Since ρ(D^{−1} B) < 1, the matrix I − D^{−1} B is nonsingular and (I − D^{−1} B)^{−1} = ∑ _{k=0}^{∞} (D^{−1} B)^{k} ⩾ 0. Then

M^{−1} (A) = (D − B)^{−1} = (I − D^{−1} B)^{−1} D^{−1} ⩾ 0,

which means that M(A) is an M-matrix, that is A is an H-matrix. □

Since it is costly to check whether a given matrix is an H-matrix or not, easily checkable subclasses of the class of H-matrices are of interest in applied linear algebra.

2.4. S-SDD matrices. The class of S-SDD matrices is a subclass of Hmatrices introduced independently by Gao and Wang in 1992 [5], and by Cvetković, Kostić and Varga in 2004 [3, 14]. We use notation from [3, 14].

Definition 2.4. Given any matrix A = [a_{ij} ] ∈ ℂ^{n×n} , n ⩾ 2, and given any nonempty proper subset S of N, then A is an S-strictly diagonally dominant (S-SDD) if

(i) |a_{ii} | > r_{i}^{S}(A) for all i ∈ S,
(ii) (|a_{ii} | − r_{i}^{S}(A))(|a_{jj} | − r\overline{S} ; j(A)) > r\overline{S} ; i(A)r_{j}^{S}(A) for all i ∈ S, j ∈ \overline{S}.

We say that a matrix A ∈ ℂ^{n×n} , n ⩾ 2, is S-SDD, if there exists a nonempty proper subset S of N, such that A is S-SDD.

The intersection of classes of DD and S-SDD matrices has a very simple characterization.

Proposition 2.7. Let A = [a_{ij} ] ∈ ℂ^{n×n} , n ⩾ 2, be a DD matrix. Then, A is an S-SDD if and only if T (A) = ∅, or A|_{T (A)^{2}} is an SDD matrix.

As a consequence, we conclude that if a matrix A is DD, such that T (A) = ∅, or A|_{T (A)^{2}} is an SDD matrix, then A is an H-matrix. We strengthen this result in Theorem 3.1.

2.5. S-H matrices. The class of S-H matrices is a subclass of H-matrices introduced by Huang in 1995 [7]

Definition 2.5. Given any matrix A = [a_{ij} ] ∈ ℂ^{n×n} , n ⩾ 2, and given any nonempty proper subset S of N, (S = {i_{1}, i_{2}, …, i_{k}}), then A is an S-H matrix if

(i) A|_{S^{2}} is an H-matrix,
(ii) ∥M^{−1} (A|_{S^{2}} ) · r\overline{S}(A)∥_{∞} < min_{j∈\overline{S}} \frac{|a_{jj} | − r\overline{S} ; j(A)}{r_{j}^{S}(A)} ,

where r\overline{S}(A) := [r\overline{S} ; i_{1} (A) r\overline{S} ; i_{2} (H) ⋯r\overline{S} ; i_{k} (A)]^{T}, \frac{a}{0} := ±∞ (depending on the sign of a ≠ 0) and \frac{0}{0} := 0.

We say that a matrix A ∈ ℂ^{n×n} , n ⩾ 2, is an S-H matrix, if there exists a nonempty proper subset S of N such that A is an S-H matrix.

The following characterization of diagonally dominant H-matrices is proven by Huang [7].

Proposition 2.8. Let A = [a_{ij} ] ∈ ℂ^{n×n} , n ⩾ 2, be a DD matrix. Then A is an H-matrix if and only if T (A) = ∅, or A is a T (A)-H matrix, i.e.,

(2.1)

(i) A|_{T (A)^{2}} is an H-matrix,
(ii) ∥M^{−1} (A|_{T (A)^{2}} ) · r\overline{T (A)}(A)∥_{∞} < min_{j∈\overline{T (A)}} \frac{|a_{jj} | − r\overline{T (A)} ; j(A)}{r_{j}^{T (A)}(A)} ,

We shall simplify that characterization in Theorem 3.1 by showing that condition (2.1ii) is surplus.

3. Main result

The main result of the paper is the following theorem. The condition (b) is obtained by Shivakumar and Chew in 1974, the condition (c) by Farid in 1995, and the condition (d) by Huang in 1995. The conditions (e) and (f) are new.

Theorem 3.1. Let A = [a_{ij} ] ∈ ℂ^{n×n} , n ⩾ 2, be a diagonally dominant (DD) matrix. Then the following conditions are equivalent:

(a) A is an H-matrix.

(b) T (A) = ∅, or for each i_{0} ∈ T (A) there exists a nonzero elements chain of the form a_{i_{0} i_{1}} , a_{i_{1} i_{2}} , …, a_{i_{r−1} i_{r}} , with i_{r} ∈ \overline{T (A)}.

(c) A has nonzero diagonal entries and T (A) is an interwoven set of indices for A.

(d) T (A) = ∅, or A is a T (A)-H matrix, i.e.,

(i) A|_{T (A)^{2}} is an H-matrix,
(ii) ∥M^{−1} (A|_{T (A)^{2}} ) · r\overline{T (A)}(A)∥_{∞} < min_{j∈\overline{T (A)}} \frac{|a_{jj} | − r\overline{T (A)} ; j(A)}{r_{j}^{T (A)}(A)} ,

(e) T (A) = ∅ or A|_{T (A)^{2}} is an H-matrix.

(f) For each nonempty M ⊆ T (A) we have that A|_{M^{2}} is a DD+ matrix.

Before the proof of the theorem, let us first prove the following lemma.

Lemma 3.1. Let A = [a_{ij} ] ∈ ℂ^{n×n} , n ⩾ 2, be a DD matrix such that T (A) ≠ ∅. If A|_{T (A)^{2}} is SDD by columns, then A is an H-matrix.

Proof. A has to be DD+ matrix, otherwise we easily obtain contradiction. If A is irreducible, then from Proposition 2.6 we conclude that it is an H-matrix. If it is reducible, then there exists a permutation matrix P, such that F = P AP^{T} is the Frobenius normal form of the matrix A

F = [ \begin{matrix}R_{11} & R_{12} & ⋯ & R_{1m} \\ 0 & R_{22} & ⋯ & R_{2m} \\ ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & ⋯ & R_{mm} \end{matrix} ] ,

where each matrix R_{jj} , j ∈ {1, 2, …, m} is either a 1 × 1 matrix, or an n_{j} × n_{j} irreducible matrix with n_{j} ⩾ 2. If R_{jj} = [a_{kk}] for some j ∈ {1, 2, …, m} and k ∈ N, then a_{kk} ≠ 0, because A|_{T (A)^{2}} is SDD by columns, which implies that A has nonzero diagonal entries. If R_{jj} is an n_{j} × n_{j} irreducible matrix with n_{j} ⩾ 2, for some j ∈ {1, 2, …, m}, then R_{jj} = A|_{N_{j}^{2}} for some N_{j} ⊂ N such that |N_{j} | = n_{j}. Since A is DD, R_{jj} is also DD, and let us assume that it is not DD+. Then N_{j} ⊆ T (A), which implies that R_{jj} is SDD by columns. A contradiction with the fact that it is DD which is not DD+. Hence, we have that R_{jj} is DD+. Now from Proposition 2.6 we conclude that R_{jj} is an H-matrix, for every j ∈ {1, 2, …, m}. By Proposition 2.5 there exist diagonal matrices D_{j} > 0 such that R_{jj} D_{j} is an SDD matrix for every j ∈ {1, 2, …, m}. Since the diagonal matrices c_{j} D_{j} have the same property for arbitrary positive real numbers c_{j}, j ∈ {1, 2, …, m}, we can easily construct a diagonal matrix D > 0 such that F D is an SDD matrix. By Proposition 2.5 F is an H-matrix, or equivalently A is an H-matrix. □

And now the proof of the main theorem follows.

Proof. (b) ⇒ (a) Analogously to the proof of Proposition 2.6.

(c) ⇒ (a) Analogously to the proof of Proposition 2.6.

(b) ⇒ (c) Since A is a DD matrix, it can be easily shown that then A has nonzero diagonal entries. If |T (A)| ⩽ 1, then the statement holds trivially, so let us assume that |T (A)| = t > 1. Let i ∈ T (A) be such that the shortest path in G(A) from i to some j ∈ \overline{T (A)} is of length l (with l being maximal with such property). Let us put all t indices from T (A) in l sets N_{i}, i ∈ {1, 2, …, l}. We put in N_{1} those indices for which the shortest path to some j ∈ \overline{T (A)} is of length 1, in N_{2} those for which such path is of length 2, and so on. Numbers p_{1}, p_{2}, …, p_{t−1} ∈ T (A) are chosen in such way that {p_{1}, …, p_{k_{1}} } = N_{1}, {p_{k_{1} +1} , …, p_{k_{2}} } = N_{2},…,{p_{k_{m−1} +1} , …, p_{t−1} } ⊆ N_{m}, m ∈ {l − 1, l}. For every p_{i} ∈ T (A), we choose an arbitrary shortest path to some j ∈ \overline{T (A)}and then choose q_{i} to be the first index after p_{i} on that path. It can now be easily shown with the given choice of numbers p_{i}, q_{i}, i ∈ {1, 2, …, t − 1}, that the set T (A) is interwoven for the matrix A.

(c) ⇒ (b) By the assumption A has nonzero diagonal entries. If |T (A)| ⩽ 1, the statement trivially holds, so let us assume that |T (A)| = t > 1. By assumption, there exist different numbers p_{1}, p_{2}, …, p_{t−1} ∈ T (A), as well as numbers q_{1}, q_{2}, …, q_{t−1} (not obligatory different), such that q_{1} ∈ \overline{T (A)}, a_{p_{1} q_{1}} ≠ 0 and q_{i} ∈ \overline{T (A)}∪ \{p_{0}, p_{2}, …, p_{i−1} \}, a_{p_{i} q_{i}} ≠ 0, for every i ∈ \{2, 3, …, t − 1\}. By using induction, we shall prove that for every n ∈ {1, 2, …, t − 1}, there exists a path in G(A) from p_{n} to some j ∈ \overline{T (A)}. If n = 1, the statement is true for j = q_{1} ∈ \overline{T (A)}. Let us now assume that it is true for all i ∈ \{1, 2, …, n − 1\}, where n ⩽ t − 1, and let us prove that it is then true for n also. We know that there exist q_{n} ∈ \overline{T (A)}∪ \{p_{1}, p_{2}, …, p_{n−1} \} such that a_{p_{n} q_{n}} ≠ 0. If q_{n} ∈ \overline{T (A)}, then we can take j = q_{n}, else q_{n} = p_{i} for some i ∈ {1, 2, …, n − 1}. Since by inductive hypothesis there exists a path in G(A) from p_{i} to some j ∈ \overline{T (A)}, then there also exists a path from p_{n} to that j ∈ \overline{T (A)}. Let T (A) ∖ \{p_{1}, p_{2}, …, p_{t−1} \} = \{i\}. Since a_{ii} ≠ 0 and r_{i}(A) = |a_{ii} | > 0, there exists k ∈ N ∖ \{i\} such that a_{ik} ≠ 0. If k ∈ \overline{T (A)}, then we have a path from i to k ∈ \overline{T (A)}, else k ∈ T (A) ∖ \{i\} = \{p_{1}, p_{2}, …, p_{t−1} \}, i.e., k = p_{l} for some l ∈ {1, 2, …, t − 0}. Since we have proven that there exists a path in G(A) from p_{l} to some j ∈ \overline{T (A)}, then there also exists a path from i to that j ∈ \overline{T (A)}. Hence, we have proven that for every i ∈ T (A), there exists a path in G(A) to some j ∈ \overline{T (A)}.

(a) ⇔ (d) This is Proposition 2.8.

(d) ⇒ (e) This is trivial.

(e) ⇒ (a) If T (A) = ∅, A is SDD and therefore an H-matrix. So let us assume that T (A) ≠ ∅, and that A|_{T (A)^{2}} is an H-matrix. Then A has to be DD+ because H-matrices have at least one SDD row. Also, A|_{T (A)^{2}}^{T} is an H-matrix, therefore there exists a diagonal matrix D_{1} > 0 such that A|_{T (A)^{2}}^{T} D_{1} is an SDD matrix. Let D > 0 be a diagonal matrix such that D|_{T (A)^{2}} = D_{1} and D|\overline{T (A)}^{2} = diag(1, 1, …, 1). With B = DA, we have that B is DD+, T (A) = T (B) and B|_{T (B)^{2}} is SDD by columns. From Lemma 3.1, we conclude that B is an H-matrix, or equivalently A is an H-matrix.

(a) ⇒ (c) Let A be a diagonally dominant H-matrix such that |T (A)|>1. Since A is an H-matrix, it has nonzero diagonal entries. For the sake of simplicity of the proof, let us take indices of elements of the submatrix A|_{T (A)^{2}} the same as they were in the matrix A, i.e., they are all from T (A). It follows from (a) ⇔ (e) that A_{1} = A|_{T (A)^{2}} is an H-matrix. If |T (A_{1})| ⩽ 1, then we can take for p_{1}, p_{2}, …, p_{t−1} , where t = |T (A)|, some t − 1 different numbers from T (A) ∖ T (A_{1}). Then for each such p_{i}, there exist q_{i} ∈ \overline{T (A)} such that a_{p_{i} q_{i}} ≠ 0, i ∈ {1, 2, …, t − 1}. If |T (A_{1})| > 1, then we choose p_{1}, p_{2}, …, p_{k_{1}} ∈ T (A), such that T (A) ∖ T (A_{1}) = \{p_{1}, p_{2}, …, p_{k_{1}} \}. For each such p_{i}, there exist q_{i} ∈ \overline{T (A)}, such that a_{p_{i} q_{i}} ≠ 0, i ∈ {1, 2, …, k_{1}}. Now it follows that A_{2} = A_{1}|_{T (A_{1} )^{2}} is an H-matrix. If |T (A_{2})| ⩽ 1, then we can take for p_{k_{1} +1} , p_{k_{1} +2} , …, p_{t−1} , some t − k_{1} − 1 different numbers from T (A_{1}) ∖ T (A_{2}). Then for each such p_{i}, there exists q_{i} ∈ {p_{1}, p_{2}, …, p_{k_{1}} }, such that a_{p_{i} q_{i}} ≠ 0, i ∈ {k_{1} + 1, k_{1} + 2, …, t − 1}. If |T (A_{2})| > 1, then we choose p_{k_{1} +1} , p_{k_{1} +2} , …, p_{k_{2}} ∈ T (A), such that T (A_{1}) ∖ T (A_{2}) = {p_{k_{1} +1} , p_{k_{1} +2} , …, p_{k_{2}} }. For each such p_{i}, there exist q_{i} ∈ {p_{1}, p_{2}, …, p_{k_{1}} }, such that a_{p_{i} q_{i}} ≠ 0, i ∈ {k_{1} + 1, k_{1} + 2, …, k_{2}}. We continue this procedure. Since {|T (A_{i})|}_{i} is a decreasing sequence of natural numbers, after a finite number of steps, we get that |T (A_{m})| ⩽ 1. Then we take for p_{k_{m−1} +1} , p_{k_{m−1} +2} , …, p_{t−1} , some t − k_{m−1} − 1 different numbers from T (A_{m−1} ) ∖ T (A_{m}). Then for each such p_{i}, there exist q_{i} ∈ {p_{k_{m−2} +1} , p_{k_{m−2} +2} , …, p_{k_{m−1}} }, such that a_{p_{i} q_{i}} ≠ 0, i ∈ {k_{m−1} + 1, k_{m−1} + 2, …, t − 1}. Thus, we have constructed different numbers p_{1}, p_{2}, …, p_{t−1} ∈ T (A), as well as numbers q_{1}, q_{2}, …, q_{t−1} (not obligatory different), such that q_{1} ∈ \overline{T (A)}, a_{p_{1} q_{1}} ≠ 0 and q_{i} ∈ \overline{T (A)}∪ \{p_{1}, p_{2}, …, p_{i−1} \}, a_{p_{i} q_{i}} ≠ 0, for every i ∈ {2, 3, …, t − 1}. Hence, T (A) is an interwoven set of indices for the matrix A.

(a) ⇒ (f) By Proposition 2.5 there exists a diagonal matrix D > 0 such that AD is an SDD matrix. Then (AD)|_{M^{2}} = A|_{M^{2}} D|_{M^{2}} is also an SDD matrix as the principal submatrix of an SDD matrix. Hence, A|_{M^{2}} (which is DD) is an H-matrix, and thus has at least one SDD row.

(f) ⇒ (a) We prove the contraposition. Assume that A is not an H-matrix. If A is not DD+, then M = T (A) = N, else from (a) ⇔ (e) it follows that A_{1} = A|_{T (A)^{2}} is not an H-matrix. For the sake of simplicity of the proof, let us take indices of elements of the submatrix A|_{T (A)^{2}} the same as they were in the matrix A, i.e., they are all from T (A). If A_{1} is not DD+, then M = T (A), else it follows that A_{2} = A_{1}|_{T (A_{1} )^{2}} = A|_{T (A_{1} )^{2}} is not an H-matrix. By continuing this procedure, we get in a finite number of steps that A|_{M^{2}} is not DD+ for some M ⊆ T (A), |M| ⩾ 2 else we finish with 1 × 1 matrix A|_{T (A_{k})^{2}} , which is not an H-matrix, i.e., A|_{T (A_{k})^{2}} = [0]. In that case, we take M = T (A_{k}). □

Acknowledgments. The author would like to thank the anonymous referee for useful comments and remarks that have substantially improved the paper.

References

1. A. Berman, R. J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, Classics Appl. Math. 9, SIAM, Philadelphia, 1994.

2. Lj. Cvetković, Convergence theory for relaxation methods to solve systems of equation, MB-5 PAMM, Technical University of Budapest, 1998.

3. Lj. Cvetković, V. Kostić, R. S. Varga, A new Geršgorin-type eigenvalue inclusion set, ETNA, Electron. Trans. Numer. Anal., 18 (2004), 73–80.

4. F. O. Farid, Criteria for invertibility of diagonally dominant matrices, Linear Algebra Appl. 215 (1995), 63–93.

5. Y. M. Gao, X. H. Wang, Criteria for generalized diagonally dominant and M-matrices, Linear Algebra Appl. 268 (1992), 257–268.

6. S. A. Geršgorin, Über die Abgrenzung der Eigenwerte einer Matrix, Izv. Akad. Nauk SSSR Ser. Mat. 1 (1931), 749–754.

7. T. Z. Huang, A note on generalized diagonally dominant matrices, Linear Algebra Appl. 225 (1995), 237–242.

8. N. Morača, H-matrice i lokalizacija spektra, Diplomski rad, Prirodno-matematički fakultet u Novom Sadu (2006).

9. , Upper bounds for the infinity norm of the inverse of SDD and S-SDD matrices, J. Comput. Appl. Math. 206 (2007), 666–678.

10. , Bounds for norms of the matrix inverse and the smallest singular value, Linear Algebra Appl. 429 (2008), 2589–2601.

11. A. M. Ostrowski, Über die Determinanten mit überwiegender Hauptdiagonale, Comment Math. Helv. 10 (1937), 69–96.

12. P. N. Shivakumar, K. H. Chew, A sufficient condition for nonvanishing of determinants, Proc. Am. Math. Soc. 43 (1974), 63–66.

13. O. Taussky, A recurring theorem on determinants, Am. Math. Mon. 56 (1949), 672–676.

14. R. S. Varga, Geršgorin and His Circles, Springer–Verlag, Berlin, 2004.

15. , On recurring theorems on diagonal dominance, Linear Algebra Appl. 13 (1976), 1–9.

16. , On diagonal dominance arguments for bounding ∥A^{−1} ∥, Linear Algebra Appl. 14 (1976), 211–217.

Department of Mathematics and Informatics (Received 17 10 2015) Faculty of Sciences (Revised 24 10 2016) University of Novi Sad Novi Sad, Serbia

 nenad.moraca@dmi.uns.ac.rs