however, the same is not true of generally diagonally dominant matrices

SCHUR COMPLEMENTS OF GENERALLY DIAGONALLY DOMINANT MATRICES AND A CRITERION FOR

IRREDUCIBILITY OF MATRICES^∗

CHENG-YI ZHANG^†, SHUANGHUA LUO^‡, CHENGXIAN XU^§, AND HONGYING JIANG^¶

Abstract. As is well known, the Schur complements of strictly or irreducibly diagonally dom- inant matrices are H−matrices; however, the same is not true of generally diagonally dominant matrices. This paper proposes some conditions on the generally diagonally dominant matrixAand the subset α⊂ {1,2, . . . , n} so that the Schur complement matrixA/α is anH−matrix. These conditions are then applied to decide whether a matrix is irreducible or not.

Key words. Schur complement, Diagonally dominant matrices,H−matrices; Irreducible, Re- ducible.

AMS subject classifications.15A15, 15F10.

1. Introduction. Recently, considerable interest appears in the work on the Schur complements of some families of matrices and several significant results are proposed. As is shown in [4], [5], [8], [2], [7], [10], [16] and [9], the Schur complements of positive semidefinite matrices are positive semidefinite (see, e.g., [16]); the same is true ofM−matrices, inverseM−matrices (see, e.g., [5]),H−matrices (see, e.g., [8]), diagonally dominant matrices (see, e.g., [2] and [7]), Dashnic-Zusmanovich matrices (see, e.g., [10]) and generalized doubly diagonally dominant matrices (see, e.g., [9]).

Since M−matrices, Dashnic-Zusmanovich matrices, strictly generalized doubly diagonally dominant matrices and strictly or irreducibly diagonally dominant ma- trices are all H−matrices (see, e.g., [1, pp. 132-161], [10], [9] and [12, p. 92), so are their Schur complements. This very property has been repeatedly used for the convergence of the Gauss-Seidel iterations and stability of Gaussian elimination in

∗Received by the editors March 27, 2008. Accepted for publication January 7, 2008. Handling Editor: Joao Filipe Queiro.

†Department of Mathematics, School of Science, Xi’an Jiaotong University, Xi’an, Shaanxi 710049, P.R. China (zhangchengyi₋[email protected]).

‡Department of Mathematics, School of Science, Lanzhou University of Technology, Lanzhou, 730050, P.R. China (iwantfl[email protected]).

§SKLMSE Lab and Department of Mathematics, School of Science, Xi’an Jiaotong University, Xi’an, 710049, P.R. China ([email protected]). The work of this author was supported by the National Natural Science Foundation of China (10671152).

¶School of Civil Engineering, Lanzhou University of Technology, Lanzhou, 730050, P.R. China.

The work of this author was supported by the Special Foundation of Lanzhou University of Tech- nology (SB04200701).

69

numerical analysis (see, e.g., [6, pp.58], [3, pp. 508], [13, pp. 122-123] and [14, pp.

281-330]). However, for generally diagonally dominant matrices, their Schur comple- ments are not necessarilyH−matrices. But, it is found that for a diagonally dominant matrix which is not a strictly or irreducibly diagonally dominant matrix, its Schur complement can be anH−matrix. Thus, there arises an open problem: how do we decide whether the Schur complements of generally diagonally dominant matrices are H−matrices or not?

In this paper some conditions on the generally diagonally dominant matrix A and the subsetα⊂N will be proposed such that the Schur complement matrixA/α is an H−matrix. These conditions are then applied to decide whether a matrix is irreducible or not.

The paper is organized as follows. Some notation and preliminary results about special matrices are given in Section 2. Some lemmas are presented in Section 3.

The main results of this paper are given in Section 4, where we give some conditions such that the Schur complement of a generally diagonally dominant matrix is an H−matrix. These results are applied to determine the irreducibility of a matrix.

Conclusions are given in Section 5.

2. Preliminaries. In this section we present some notions and preliminary re- sults about special matrices that are used in this paper.

C^m×n(R^m×n) will be used to denote the set of allm×ncomplex (real) matrices.

LetA= (a_ij)∈R^m×n andB = (b_ij)∈R^m×n, we writeA≥B, ifa_ij ≥b_ij holds for alli= 1,2,· · ·, m, j= 1,2,· · ·, n. A matrixA= (a_ij)∈R^n×n is called aZ−matrix ifa_ij ≤0 fori =j, i, j = 1,2,· · ·, n. We will use Z_n to denote the set of alln×n Z−matrices. A matrix A = (a_ij) ∈ R^n×n is called an M−matrix if A ∈ Z_n and A⁻¹≥0. M_n will be used to denote the set of alln×n M−matrices.

For a given matrix A = (a_ij) ∈ C^n×n, the comparison matrixµ(A) = (µ_ij) is given by

µ_ij =

|a_ii|, if i=j,

−|a_ij|, if i=j.

It is clear that µ(A) ∈ Z_n for a matrix A ∈ C^n×n. A matrix A ∈ C^n×n is called H−matrixifµ(A)∈M_n. H_n will denote the set of alln×n H−matrices.

For n ≥ 2, an n×n complex matrix A is reducible if there exists an n×n permutation matrixP such that

P AP^T =

A₁₁ A₁₂ 0 A₂₂

, (2.1)

where A₁₁ is anr×rsubmatrix and A₂₂ is an (n−r)×(n−r) submatrix, where 1≤r < n. If no such permutation matrix exists, thenAis calledirreducible. IfAis a 1×1 complex matrix, thenAis irreducible if its single entry is nonzero, and reducible otherwise.

Let|α|denote the cardinality of the setα⊆N. For nonempty index setsα, β⊆ N,A(α, β) is the submatrix ofA∈C^n×n with row indices inαand column indices in β. The submatrix A(α, α) is abbreviated to A(α). Let α⊂N, α =N−α, and A(α) be nonsingular. Then, the matrix

A/α=A/A(α) =A(α)−A(α, α)[A(α)]⁻¹A(α, α) (2.2)

is called the Schur complement of A with respect toA(α), where indices in bothα andα are arranged with increasing order.

Definition 2.1. LetA∈C^n×n,N ={1,2,· · ·, n}, and define sets

J(A) =



i| |a_ii| ≥ ⁿ

j=1,j=i

|a_ij|, i∈N



(2.3)  and

K(A) =



i| |aii|>

n j=1,j=i

|aij|. i∈N



(2.4) 

If J(A) = N, A is called diagonally dominant by row. IfA is diagonally dominant by row with K(A) = N, A is called strictly diagonally dominant by row. If A is irreducible and diagonally dominant by row with K(A)=∅, Ais called [irreducibly diagonally dominant by row. If A is diagonally dominant withJ(A)∩K(A) = ∅, A is calleddiagonally equipotent by row.

D_n, SD_n, ID_nandDE_n will be used to denote the sets ofn×nmatrices which are diagonally dominant by row, strictly diagonally dominant by row, irreducibly diagonally dominant by row and diagonally equipotent by row, respectively.

Remark 2.2. LetA= (a_ij)∈D_n andα=N−α ⊂N. IfA(α) is a diagonally equipotent principal submatrix ofA, then the following hold:

• A(α, α) = 0;

• A(i₁) = (a_i1i1) being diagonally equipotent impliesa_i1i1 = 0.

Remark 2.2 implies the following lemmas.

Lemma 2.3. If a matrixA∈D_n has a diagonally equipotent principal submatrix A(α) for α⊂N, thenA is reducible.

Lemma 2.4. If A∈SD_n∪ID_n, thenA∈H_n and is nonsingular.

Definition 2.5. A directed graph or digraph Γ is an ordered pair Γ := (V, E) that is subject to the following conditions: (i) V is a set whose elements are called vertices or nodes; (ii) E is a set of ordered pairs of vertices, called directed edges, arcs, or arrows. Let A ∈ C^n×n, where n < +∞. Then, we define the digraph Γ(A) of A as the directed graph with vertex set V = {1,2,· · ·, n} and edge set E={(i, j)|i, j∈V, i=j},where (i, j)∈Eis an edge of Γ(A) connecting the vertex ito the vertexjifa_ij = 0, i=j. Clearly, Γ(A) is a finite directed graph without loops and multiple edges. A digraph Γ(A) is calledstrongly connectedif for any ordered pair of verticesiandj, there exists a directed path (i, i₁),(i₁, i₂),· · ·,(i_r−1, j) connecting iandj.

Lemma 2.6. A∈C^n×n is irreducible if and only if its digraph Γ(A) is strongly connected.

Definition 2.7. GivenA= (a_ij)∈C^n×n, we define the matrix π(A) = (m_ij)∈R^n×n,

where

m_ij =











−|a_ij|, a_ij= 0 and i > j,

|a_ij|, a_ij= 0 and i < j, _n

j=1,j=i|aij|, i=j,

0, otherwise.

(2.5)

According to Definition 2.5and 2.7, it is clear that Γ(π(A)) = Γ(A).

(2.6)

Lemma 2.8. A∈C^n×n is irreducible if and only ifπ(A)is irreducible.

Proof. It follows from Lemma 2.6 and (2.6) that the conclusion of this lemma is true.

3. Some lemmas. In this section, some lemmas concerning several properties of diagonally dominant matrices and the Schur complements of matrices will be pre- sented. They will be of use in the sequel.

Lemma 3.1. (see [15]) A matrix A ∈ D_n is singular if and only if the matrix A has at least either one zero principal submatrix or one irreducible and diagonally equipotent principal submatrix A_k =A(i₁, i₂,· · ·, i_k),1 < k≤n, which satisfies con- dition that there exists ak×k unitary diagonal matrixU_k such that

U_k⁻¹D_A⁻¹_kA_kU_k =µ(D⁻¹_AkA_k), (3.1)

whereD_Ak=diag(a_i1i1, a_i2i2,· · ·, a_ikik).

Lemma 3.2. Let A ∈D_n. Then A is singular if and only if A has at least one singular principal submatrix.

Proof. Necessity is obvious since A is a principal submatrix of itself. For suf- ficiency, suppose that A(i₁, i₂,· · ·, i_k) is a singular principal submatrix of A where 1≤k≤n. Then it follows from the necessity of Lemma 3.1 that there exists a zero principal submatrix or a singular irreducible diagonally equipotent principal subma- trix B = A(j₁, j₂,· · ·, j_k)(1 < k ≤ k) in A(i₁, i₂,· · ·, i_k), which satisfies condition (3.1). Obviously, B is also a singular equipotent principal submatrix of A which satisfies condition (3.1). So it follows from Lemma 3.1 thatAis singular.

Lemma 3.3. (see [15])Given a matrixA∈R^n×n, ifA∈D_n and is nonsingular, then A has |J+(A)| eigenvalues with positive real part and |J−(A)| eigenvalues with negative real part, whereJ₊(A) ={i|a_ii >0, i∈N}, J₋(A) ={i|a_ii<0, i∈N}.

Lemma 3.4. (see [1]) Let A∈Z_n. Then A∈M_n if and only if the real part of each eigenvalue ofA is positive.

Lemma 3.5. LetA∈D_n.ThenA∈H_nif and only ifAhas neither zero principal submatrices nor irreducibly diagonally equipotent principal submatrices.

Proof. First we prove sufficiency. Assume thatA has neither zero principal sub- matrices nor irreducibly diagonally equipotent principal submatrices. Then neither doesµ(A). Sinceµ(A) has no zero principal submatrices andµ(A)∈D_nforA∈D_n, it follows from Lemma 3.1 thatµ(A) is singular if and only ifµ(A) has at least one irre- ducible and diagonally equipotent principal submatrixA_k =A(i₁, i₂,· · ·, i_k),1< k≤ nsatisfying condition (3.1). But,µ(A) has not any irreducibly diagonally equipotent principal submatrices. Consequently, µ(A) is nonsingular. Again, following Lemma 3.3, the real part of each eigenvalue of µ(A) is positive. Therefore, Lemma 3.4 indi- cates thatµ(A)∈M_n, i.e.,A∈H_n.

Next, necessity can be proved by contradiction. SupposeA has either one zero principal submatrix or one irreducibly diagonally equipotent principal submatrix. So doesµ(A). Such principal matrix is assumed as µ(A_k), whereA_k is either one zero principal submatrix or one irreducibly diagonally equipotent principal submatrix ofA.

Then it follows from of Lemma 3.1 thatµ(A) is singular. According to the definition of M−matrix,µ(A) is not an M−matrix. This shows thatA is not an H−matrix, which contradictsA∈H_n. Thus, necessity is true, which completes the proof.

Lemma 3.6. (see [11]) LetA∈C^n×n be partitioned as

A=

a₁₁ A₁₂ A₂₁ A₂₂

,

whereA₂₁= (a₂₁, a₃₁,· · ·, a_n1)^T andA₁₂= (a₁₂, a₁₃,· · ·, a_1n). IfA₂₂is nonsingular, then

det A

det A₂₂ =a₁₁−(a₁₂, a₁₃,· · ·, a_1n)[A₂₂]⁻¹



 a₂₁

... a_n1



.

Lemma 3.7. (see [1,4])IfA∈D_n∩Z_nwitha_ii≥0for alli∈N, thendet A≥0.

Furthermore, ifA∈D_n∩M_n, thendet A >0.

Lemma 3.8. Given an irreducible matrix A = (a_ij) ∈ Z_n with a_ii ≥ 0 for all i∈N and a set α⊂N, ifA∈DE_n, thenA/α∈DE_n−|α|∩Z_n−|α|.

Proof. SinceA∈DE_nis irreducible andα⊂N,A(α)∈H_|α|. Otherwise, Lemma 3.5shows thatA(α) has a zero principal submatrix or diagonally equipotent principal submatrix, say A(γ) for γ ⊆ α. Then, A(γ) is also a zero principal submatrix or diagonally equipotent principal submatrix ofA. It then follows from Lemma 2.3 that A is reducible which contradicts the irreducibility of A. Thus, A(α) ∈ H_|α|. Since A = (a_ij)∈Z_n with a_ii ≥0 for alli ∈N,A(α) = (a_ij)∈ Z_|α| with a_ii ≥0 for all i ∈ α. As a result, A(α) ∈ M_|α| and consequently [A(α)]⁻¹ ≥ 0. Therefore, A/α exists. Supposeα={i1, i₂,· · ·, i_k},α =N −α={j1, j₂,· · ·, j_m}, k+m=n. Let A/α = (a_jl,jt)_m×m. According to definition (2.2) of the matrix A/α, we have the off-diagonal entries of the Schur complement matrixA/α,

a_jl,jt = a_jl,jt−





(a_jl,i1, a_jl,i2,· · ·, a_jl,ik)[A(α)]⁻¹





 a_i1,jt a_i2,jt

... a_ik,jt













= −





|a_jl,jt|+ (|a_jl,i1|,· · ·,|a_jl,ik|)[A(α)]⁻¹







|ai1,jt|

|a_i2,jt| ...

|aik,jt|











≤0,

l=t, l, t= 1,2,· · ·, m (3.2)

which showsA/α∈Z_n−|α|, and the diagonal entries (obtained by Lemma 3.6)

a_jl,jl = a_jl,jl−





(a_jl,i1, a_jl,i2,· · ·, a_jl,ik)[A(α)]⁻¹





 a_i1,jl a_i2,jl

... a_ik,jl













= det C_l

det A(α), l= 1,2,· · ·, m, (3.3)

where

C_l=

a_jl,jl h s A(α)

(k+1)×(k+1),

s= (a_i1,jl,· · ·, a_ik,jl)^T, h= (a_jl,i1,· · ·, a_jl,ik).

SinceC_lis a (k+ 1)×(k+ 1) principal submatrix ofA,C_l∈D_k+1∩Z_k+1 with all its diagonal entries being nonnegative and it follows from Lemma 3.7 that det C_l ≥0.

In the same way,det A(α)>0. Thus,

a_jl,jl = det C_l det A(α) ≥0.

Therefore,

|a_jl,jl| = |ajl,jl| −





(|ajl,i1|,· · ·,|ajl,ik|)[A(α)]⁻¹







|a_i1,jl|

|ai2,jl| ...

|a_ik,jl|











≥0,

l= 1,2,· · ·, m.

(3.4)

Since A ∈ Z_n with a_ii ≥0 for all i ∈ N and [A(α)]⁻¹ ≥ 0, using (3.2), (3.4) and Lemma 3.6, we have

|a_jl,jl| − ^m

i=1,i=l|a_jl,ji|=

a_jl,jl−(a_jl,i1,· · ·, a_jl,ik)[A(α)]⁻¹





 a_i1,jl a_i2,jl

... a_ik,jl







− ^m

i=1,i=l





a_jl,ji−(a_jl,i1,· · ·, a_jl,ik)[A(α)]⁻¹





 a_i1,ji a_i2,ji

... a_ik,ji













= |a_jl,jl| − ^m

i=1,i=l|a_jl,ji|

−^m

i=1





(|a_jl,i1|,|a_jl,i2|,· · ·,|a_jl,ik|)|[A(α)]⁻¹|







|a_i1,ji|

|a_i2,ji| ...

|a_ik,ji|













= detB_l

det A(α), l= 1,2,· · ·, m, (3.5)

where

B_l=



 |ajl,jl| − ^m

i=1,i=l|ajl,ji| h^T

g A(α)





(k+1)×(k+1),

g= (−

m i=1

|ai1,ji|,· · ·,− m i=1

|aik,ji|)^T, h= (−|a_jl,i1|,· · ·,−|a_jl,ik|)^T.

It is clear thatB_l∈Z_k+1. SinceA∈DE_n, we have

|a_jl,jl| − ^m

i=1,i=l

|a_jl,ji|= k t=1

|a_jl,it|.

(3.6)

and

|a_ir,ir|= k t=1,t=r

|a_ir,it|+ m

i=1

|a_ir,ji|, r= 1,2,· · ·, k.

(3.7)

Equalities (3.6) and (3.7) indicateB_l∈DE_k+1. SinceB_l∈DE_k+1∩Z_k+1, it follows from Lemma 3.1 thatB_lis singular anddet B_l= 0. SinceA(α)∈D_|α|∩M_|α|, Lemma 3.7 givesdet A(α)>0. Thus, by (3.5), we have

|a_jl,jl| − ^m

i=1,i=l

|a_jl,ji|= detB_l det A(α) = 0 and thus

|a_jl,jl|= m i=1,i=l

|a_jl,ji|, l= 1,2,· · ·, m, (3.8)

which showsA/α∈DE_m. This completes the proof.

Lemma 3.9. (see [16]) Given a matrix A = (a_ij) ∈ C^n×n and two diagonal matrices E =diag(e₁,· · ·, e_n) and F =diag(f₁,· · ·, f_n) with e_i = 0 and f_i = 0 for all i ∈N. Assume B =EAF andα=N −α ⊂N. If A(α) is nonsingular, then B/α=E_α(A/α)F_α,whereα=N−α={j₁,· · ·, j_m},E_α =diag(e_j1,· · ·, e_jm)and F_α =diag(f_j1,· · ·, f_jm).

Lemma 3.10. (see [7]) Given a matrix A ∈ D_n and a set α ⊂ N, if A(α) is nonsingular, thenA/α∈D_n−|α|.

Lemma 3.11. (see [8])Let A∈H_n andα⊂N. ThenA/α∈H_n−|α|.

Lemma 3.12. Let an irreducible matrix A∈D_n. Then for eachα⊂N,A/α∈ DE_n−|α| if and only ifA is singular.

Proof. Sufficiency will be proved firstly. Assume thatAis singular. SinceA∈D_n is irreducible,a_ii = 0 fori= 1,2,· · ·, nand Lemma 3.1 yields that there exists an×n unitary diagonal matrixU =diag(u₁,· · ·, u_n) such that

D⁻¹A=U µ(D⁻¹A)U⁻¹∈DE_n, (3.9)

where D =diag(a₁₁, a₂₂,· · ·, a_nn). Let B = D⁻¹A ∈DE_n, then B =U µ(B)U⁻¹. According to Lemma 3.9, we have

B/α=U_α[µ(B)/α]U_α⁻¹ , (3.10)

whereα =N−α={j₁,· · ·, j_m}and U_α =diag(u_j1,· · ·, u_jm). SinceB =D⁻¹A∈ DE_n,µ(B)∈DE_n. It then follows from Lemma 3.8 thatµ(B)/α∈DE_n−|α|. Since U_α is an m×m unitary diagonal matrix, (3.10) implies B/α ∈ DE_n−|α|. As is assumed,A=DB. Thus, Lemma 3.9 gives that

A/α=D_α[B/α], (3.11)

where D_α = diag(d_j1,· · ·, d_jm). Since B/α ∈ DE_n−|α|, (3.11) implies A/α ∈ DE_n−|α|, which completes sufficiency.

Next, we will prove necessity by contradiction. Assume thatA∈D_nis nonsingu- lar. IfA∈H_n, Lemma 3.10 and Lemma 3.11 showA/α∈D_n−|α|∩H_n−|α|. It follows from Lemma 3.5thatA/α /∈DE_n−|α|, which shows that the assumption is not true.

Thus,Ais singular.

If A /∈ H_n but A ∈ D_n is irreducible, Lemma 3.5indicates A ∈ DE_n is irre- ducible. Again, since A ∈ DE_n is nonsingular, a_ii = 0 for i = 1,2,· · ·, n and Lemma 3.1 implies that there is not any n×n unitary diagonal matrix U such that (3.9) holds. Without loss of generality, let D = I. Then D⁻¹A =A ∈ DE_n and U⁻¹D⁻¹AU =U⁻¹AU /∈Z_n for alln×nunitary diagonal matrix U. Suppose α={i₁, i₂,· · ·, i_k},α =N−α={j₁, j₂,· · ·, j_m}, k+m=n. LetA/α= (a_jl,jt)_m×m. SinceA∈DE_nis irreducible andα⊂N, it follows from the proof of Lemma 3.8 that A(α)∈H_|α|. As a result, [µ(A(α))]⁻¹≥0. SinceU⁻¹D⁻¹AU =U⁻¹AU /∈Z_nfor all n×nunitary diagonal matrixU, there exists at least onel, l= 1,2,· · ·, msuch that

(3.5) becomes

|a_jl,jl| − ^m

i=1,i=l|a_jl,ji|=

a_jl,jl−(a_jl,i1,· · ·, a_jl,ik)[A(α)]⁻¹





 a_i1,jl a_i2,jl

... a_ik,jl







− ^m

i=1,i=l





a_jl,ji−(a_jl,i1,· · ·, a_jl,ik)[A(α)]⁻¹





 a_i1,ji a_i2,ji

... a_ik,ji













> |a_jl,jl| − ^m

i=1,i=l|a_jl,ji|

−^m

i=1





(|a_jl,i1|,|a_jl,i2|,· · ·,|a_jl,ik|)[µ(A(α))]⁻¹







|a_i1,ji|

|a_i2,ji| ...

|a_ik,ji|













= detC_l det µ[A(α)], (3.12)

where

C_l=



 |a_jl,jl| − ^m

i=1,i=l|a_jl,ji| h^T

g µ[A(α)]





(k+1)×(k+1),

g= (−^m

i=1

|a_i1,ji|,· · ·,−^m

i=1

|a_ik,ji|)^T, h= (−|a_jl,i1|,· · ·,−|a_jl,ik|)^T.

It is clear that C_l ∈ Z_k+1. Since A ∈ DE_n, we have that (3.6) and (3.7) hold.

Equalities (3.6) and (3.7) indicateC_l∈DE_k+1. SinceC_l∈DE_k+1∩Z_k+1, it follows from Lemma 3.1 thatC_lis singular anddet B_l= 0. SinceA(α)∈H_|α|,µ[A(α)]∈M_|α|

and Lemma 3.7 givesdet µ[A(α)]>0. Thus, by (3.12), we have

|a_jl,jl| − ^m

i=1,i=l

|a_jl,ji|> detB_l det A(α) = 0 and thus there exists at least onel, l= 1,2,· · ·, msuch that

|a_jl,jl|>

m i=1,i=l

|a_jl,ji| (3.13)

which showsA/α /∈DE_n−|α|. Therefore, the assumption is not true andAis singular.

This completes necessity.

Lemma 3.13. Let A∈D_n. Then A is nonsingular if and only ifA(α)and A/α are both nonsingular for eachα⊂N.

Proof. Assumeα =N−α. Since Ais nonsingular, it follows from Lemma 3.2 thatA(α) is nonsingular for eachα⊂N. Thus,A/αexists for eachα⊂N and there exists ann×npermutation matrixP such that

B=P^TAP =

A(α) A(α, α) A(α, α) A(α)

.

LetP₁=

I_|α| 0

−A(α, α)[A(α)]⁻¹ I_|α|

, P₂=

I_|α| −[A(α)]⁻¹A(α, α)

0 I_|α|

, whereI_|α|andI_|α|are the|α|×|α|identity matrix and the|α|×|α|identity matrix, respectively. Then, the product

P₁BP₂ = P₁P^TAP P₂

=

A(α) 0

0 A(α)−A(α, α)[A(α)]⁻¹A(α, α)

=

A(α) 0

0 A/α

. (3.14)

As P,P₁ , P₂ and A are all nonsingular, so is P₁BP₂. Again, A(α) is nonsingular, thenA/αis nonsingular from (3.14).

IfA(α) andA/αare nonsingular, thenP₁BP₂=P₁P^TAP P₂is nonsingular from (3.14). So isA.

Lemma 3.14. Given an n×n matrix A ∈C^n×n and two setsα, α satisfying α⊂N and α =N−α, assume that A(α)is nonsingular and there exists an n×n permutation matrix P such that

P AP^T =







A₁₁ A₁₂ · · · A_1s 0 A₂₂ · · · A_2s ... ... . .. ... 0 0 · · · A_ss





, (3.15)

where A_ii is irreducible, A_ij = A(α_i, α_j) is the submatrix of A for i, j = 1,2,· · ·, s (1 ≤ s ≤ n), with row indices in α_i and column indices in α_j, _s

j=1α_j = N and α_i∩α_j =∅ for i=j. If A/αis irreducible, then for some i, i= 1,2,· · ·, s,α ⊆α_i andA/α= [A(α_i)]/η, whereη =α_i−α.

Proof. IfA is irreducible, then A₁₁ = A(α₁) = A. As a result, α₁ =N, η = α₁−α =N−α =α. HenceA/α= [A(α₁)]/η. The conclusion of this lemma is true.

IfAis reducible, then 2≤s≤n. For this case, the conclusion of this lemma will be proved by contradiction. Assume that the conclusion of this lemma is not true,

that is,α⊆α_i doesn’t hold for anyi, i= 1,2,· · ·, s. Then, letα =_s

j=1β_j, where

∅ ⊆β_j ⊆α_j forj = 1,2,· · ·, sand the number of nonempty setβ_j is at least equal to 2. Letγ_j =α_j−β_j forj= 1,2,· · ·, s, then

α=N−α= s j=1

α_j−^s

j=1

β_j= s j=1

γ_j. Then there exists ann×npermutation matrixP₁ such that

C=P₁P AP^TP₁^T = P₁







A₁₁ A₁₂ · · · A_1s 0 A₂₂ · · · A_2s ... ... . .. ... 0 0 · · · A_ss





P₁^T

=







A(α₁) A(α₁, α₂) · · · A(α₁, α_s) 0 A(α₂) · · · A(α₂, α_s)

... ... . .. ...

0 0 · · · A(α_s)





, (3.16)

whereA(αi, αj) =

"

A(γi, γj) A(γi, βj) A(βi, γj) A(βi, βj)

#

, i < jandA(αi) =

"

A(γi) A(γi, βi) A(βi, γi) A(βi)

#

fori, j= 1,2,· · ·, s. Therefore, there exists ann×npermutation matrixQsuch that QCQ^T =QP₁P AP^TP₁^TQ^T =

A(α) A(α, α) A(α, α) A(α)

, (3.17)

where

A(α) =







A(γ₁) A(γ₁, γ₂) · · · A(γ₁, γ_s) 0 A(γ₂) · · · A(γ₂, γ_s)

... ... . .. ...

0 0 · · · A(γ_s)





,

A(α) =







A(β₁) A(β₁, β₂) · · · A(β₁, β_s) 0 A(β₂) · · · A(β₂, β_s)

... ... . .. ...

0 0 · · · A(β_s)





,

A(α, α) =







A(β₁, γ₁) A(β₁, γ₂) · · · A(β₁, γ_s) 0 A(β₂, γ₂) · · · A(β₂, γ_s)

... ... . .. ... 0 0 · · · A(β_s, γ_s)





,

A(α, α) =







A(γ₁, β₁) A(γ₁, β₂) · · · A(γ₁, β_s) 0 A(γ₂, β₂) · · · A(γ₂, β_s)

... ... . .. ... 0 0 · · · A(γ_s, β_s)





. (3.18)

Direct computation yields

A/α = A(α)−A(α, α)[A(α)]⁻¹A(α, α)

=







[A(α₁)]/γ₁ ∗ · · · ∗

0 A[A(α₂)]/γ₂ · · · ∗

... ... . .. ...

0 0 · · · [A(α_s)]/γ_s





, (3.19)

where ∗ denotes some unknown matrices. The equality (3.19) shows that A/α is reducible. This contradicts the irreducibility of A/α. Therefore, the assumption is incorrect and the conclusion of this lemma is true.

4. Main results. The main theorems of this paper are presented in this sec- tion. They concern when a Schur complement of a diagonally dominant matrix is an H−matrix. Then these theorems are applied to decide whether a matrix is an irreducible matrix or not.

Theorem 4.1. Let A ∈ DE_n be nonsingular. Then A/α ∈ H_n−|α| for each α⊂N if and only ifA is irreducible.

Proof. Sufficiency will be proved firstly. Assume that A is irreducible. Since A ∈ DE_n ⊆ D_n is nonsingular, it follows from Lemma 3.10 and Lemma 3.12 that A/α∈D_n−|α|, butA/α /∈DE_n−|α|. It follows that sufficiency can be proved by the following two cases.

Case (i). If A/α is irreducible, then A/α ∈ID_n−|α|. Lemma 2.4 yields A/α ∈ H_n−|α|for eachαN which completes the sufficiency of this theorem.

Case (ii). If A/α is reducible, there exists an |α| × |α| permutation matrix P such that

P[A/α]P^T =P[A(α )]P^T =









A₁₁ A₁₂ · · · A_1s 0 A₂₂ · · · A_2s ... ... . .. ... 0 0 · · · A_ss







, (4.1)

whereA_ii is irreducible fori= 1,2,· · ·, s(s≥2),and correspondingly,

P[A(α)]P^T =







A₁₁ A₁₂ · · · A_1s A₂₁ A₂₂ · · · A_2s ... ... . .. ... A_s1 A_s2 · · · A_ss





, (4.2)

P[A(α, α)] =

A₁₀ A₂₀ · · · A_s0 ^T, (4.3)