# Error bounds for linear complementarity problems of DB-matrices

## Error bounds for linear complementarity problems of DB-matrices

Linear Algebra and its Applications 434 (2011) 830–840 Contents lists available at ScienceDirect Linear Algebra and its Applications journal homepag...

Linear Algebra and its Applications 434 (2011) 830–840

Contents lists available at ScienceDirect

Linear Algebra and its Applications journal homepage: www.elsevier.com/locate/laa

Error bounds for linear complementarity problems of DB-matrices聻 Ping-Fan Dai Department of Mathematics and Computer Science, Sanming University, Sanming, Fujian 365004, PR China

A R T I C L E

I N F O

A B S T R A C T

Doubly B-matrices (DB-matrices), which properly contain B-matrices, are introduced by Peña (2003) [2]. In this paper we present error bounds for the linear complementarity problem when the matrix involved is a DB-matrix and a new bound for linear complementarity problem of a B-matrix. The numerical examples show that the bounds are sharp. © 2010 Elsevier Inc. All rights reserved.

Article history: Received 11 May 2010 Accepted 27 September 2010 Available online 2 November 2010 Submitted by M. Tsatsomeros Keywords: Error bounds Linear complementarity problem DB-matrix B-matrix H-matrix P-matrix

1. Introduction A real square matrix A is called a B-matrix if it is the matrix with positive row sums and all its off-diagonal elements bounded above by their corresponding row means (see [1]), i.e. for all i = 1, . . . , n, n  k =1

aik

> 0 and

A real matrix A aii 聻

n 1 

n k =1

aik

> aij ,

∀i = / j.

= (aij ) ∈ Rn×n with diagonal elements satisfying

> ri+ ∀i ∈ {1, . . . , n}

This work is supported by the Science Foundation of the Education Department of Fujian Province (JB09228) and the Science

P.-F. Dai / Linear Algebra and its Applications 434 (2011) 830–840

831

is a doubly B-matrix (DB-matrix) if, for all i = / j (i, j ∈ {1, . . . , n}), ⎛ ⎞⎛ ⎞       +  + + + ajj − rj > ⎝ ri − aik ⎠ ⎝ rj − ajk ⎠ , aii − ri k= /i

k= /j

+

where ri = max{0, aij |∀j = / i} (see [2]). A real square matrix A is called a P-matrix if all its principal minors are positive. It is shown in [2] that a DB-matrix is a P-matrix. The linear complementarity problem, abbreviated LCP, is to ﬁnd a vector z ∈ Rn such that z  0,

Mz

+ q  0, (Mz + q)T z = 0

(1.1) n× n

and q ∈ R . Many applications for or to show that no such vector z exists, where M = (mij ) ∈ R (1.1) can be found in [3–5], respectively. M is a P-matrix if and only if the LCP(M, q) has a unique solution for any q (see [4]). Error bounds for LCP have been given in [6–10,14]. Structured matrices can lead to nice properties of the corresponding linear complementarity problems. For instance, in [6], García-Esnaola et al. give error bounds for linear complementarity problem for B-matrices. Motivated by [6], in this paper, we present error bounds for DB-matrices linear complementarity problems. Since DB-matrices properly contain B-matrices, we get a generalization of [6] and obtain a new bound for LCP of a B-matrix (see Remark 3.2). The numerical examples show that the bounds are sharp. n

2. Preliminaries Let us introduce some basic notations. Let N := {1, . . . , n}. Given a set S, |S | denote the cardinal number of S. A Z-matrix is a matrix whose off-diagonal elements are nonpositive and a nonsingular Mmatrix is a Z-matrix with nonnegative inverse. Let A = (aij ), i, j ∈ N, be a real matrix. The comparison matrix A = (cij ) is deﬁned by setting cii

= |aii |, cij = −|aij |, i = / j, i, j ∈ N .

If A is an M-matrix, then A is called an H-matrix. From now on, we shall use the following notation: for each i, j  |aij |. Ri (A) :=

∈ N,

i= /j

A matrix A is strictly diagonally dominant if |aii | > Ri (A), i ∈ N and strictly doubly diagonally dominant if |aii ||ajj | > Ri (A)Rj (A), ∀ i = / j, i, j ∈ N. A strictly doubly diagonally dominant matrix is nonsingular (see Theorem 3.6.6 of [11]) and an H-matrix (see [12]). For each real square matrix M = (mij ), i, j ∈ N, let ri

= max{0, mij |∀j = / i},

we can write M as M

= B+ + C,

where B+

=

m11 − r1 ⎜m21 − r2 ⎜ ⎜ .. ⎝ . mn1

− rn

− r1 − r2 .. . mn2 − rn

m12 m22

··· ··· ..

.

···

− r1 ⎞ − r2 ⎟ ⎟ ⎟, .. ⎠ . mnn − rn

m1n m2n

C

=

r1 ⎜r2 ⎜ ⎜. ⎝ .. rn

··· ··· ..

.

···

⎞ r1 r2 ⎟ ⎟ . .. ⎟ .⎠

(2.1)

rn

Obviously, B+ is a Z-matrix and C is a nonnegative matrix of rank 1. We need the following auxiliary result. Lemma 2.1. Let M = (mij ) ∈ Rn×n , and let M = B+ + C, B+ , C be as in (2.1). If M is a DB-matrix, then B+ is a strictly doubly diagonally dominant matrix with positive diagonal elements and an M-matrix, too.

832

P.-F. Dai / Linear Algebra and its Applications 434 (2011) 830–840

Proof. It follows from the deﬁnition of doubly B-matrix that B+ is a strictly doubly diagonally dominant matrix with positive diagonal elements. Taking into account that a strictly doubly diagonally dominant matrix is a nonsingular H-matrix, one can get that B+ is an H-matrix with positive diagonal elements. Since B+ is a Z-matrix, B+ is also a nonsingular M-matrix.  Pan and Chen give an upper bounds, which are used as proof of our main results, for the inﬁnity norm of the inverse of strictly doubly diagonally dominant matrix in [13] as follows. Lemma 2.2. Let M = (mij ) ∈ Rn×n be a strictly doubly diagonally dominant matrix, Q := {i ∈ N ||mii | > Ri (M )}, |mj1 j1 | − Rj1 (M ) = mini∈Q {|mii | − Ri (M )}, J (M ) := {i ∈ Q ||mii | − Ri (M ) = |mj1 j1 | − Rj1 (M )},

|mjj | + Ri (M ) , i, j ∈ N, |mii ||mjj | − Ri (M )Rj (M ) then the following results hold. α(j, i) :=

(1) M −1 ∞  max j=/ i, α(j, i). i,j∈N

(2) If Q = N, i.e., M be a strictly diagonally dominant matrix, it holds that max α(j, i) j= / i, i,j∈N

= max α(j, j1 )  j= / j1 , j1 ,j∈N

1 minj∈N {|mjj | − Rj (M )}

,

equality holds if and only if one of the following conditions holds. a. |J (M )|  2; b. J (M ) = {j1 } and Rj1 (M )

= 0.

/ N, i.e., there exists i0 ∈ N − Q such that |ai0 i0 |  Ri0 (M ), then it follows that (3) If Q = max α(j, i) j= / i, i,j∈N

⎧ ⎨

⎫ ⎬

= max ⎩max α(j, i0 ), max α(j, j1 ) . j ∈Q

In particular, if |J (M )|  2, it holds that  max α(j, i) j= / i, i,j∈N

j= / j1 , j ∈Q

= max max α(j, i0 ), j ∈Q



1 minj∈Q {|mjj | − Rj (M )}

.

Since a DB-matrix M is a P-matrix, we can apply M to the third inequality of Theorem 2.3 of [8] and obtain

x − x∗ ∞  max n (I − D + DM )−1 ∞ r (x)∞ , d∈[0,1]

where x∗ is the solution of the LCP(M, q), r (x) := min{x, Mx + q}, D = diag(di ) with 0  di  1, and the min operator denotes the componentwise minimum of two vectors. 3. Main results In this section, we provide the bounds for maxd∈[0,1]n (I − D + DM )−1 ∞ when M is an n × n DB-matrix. The bounds can be calculated with O(n2 ) elementary operations. Theorem 3.1. On the assumption that M be as in (2.1). Let

β1 (j, i) =

bjj bii bjj

− Ri (B+ )Rj (B+ )

,

= (mij ) is an n × n DB-matrix and let B+ =: (bij ), i, j ∈ N, C β2 (i) =

Ri (B+ ) bii

,

P.-F. Dai / Linear Algebra and its Applications 434 (2011) 830–840

833

:= {i ∈ N ||bii | > Ri (B+ )}, |bj1 j1 | − Rj1 (B+ ) = mini∈Q {|bii | − Ri (B+ )}, − Ri (B+ ) = |bj1 j1 | − Rj1 (B+ )}. Then the following results hold.

J (B+ )

Q

:= {i ∈ Q | |bii |

(1) It holds that max

d∈[0,1]n

(I − D + DM )−1 ∞ ⎛

⎧ ⎨

⎫ ⎬

⎧ ⎨

⎫⎞

⎬ β2 (i) (n − 1) ⎝max max β1 (j, i), 1 + max max , max β2 (i) ⎠ . ⎩ j=/ i, ⎭ ⎩ j=/ i, bjj − β2 (i)Rj (B+ ) i∈N ⎭ i,j∈N i,j∈N

(2) If M is a B-matrix, then it follows that max

d∈[0,1]n

where

(I − D + DM )−1 ∞ (n − 1)η, ⎧ ⎨

⎧ ⎨

⎫ ⎬

⎬ β2 (j1 ) η = max ⎩max β1 (j, j1 ), 1 + max max , β2 (j1 ) . + ⎩ ⎭ ⎭ j= / j1 , j= / j1 , b − β (j )R (B ) jj 2 1 j j ∈N j ∈N

(3) If M is not a B-matrix, there exists i0 ∈ N − Q such that bi0 i0  Ri0 (B+ ), and then it holds that max

d∈[0,1]n

(I − D + DM )−1 ∞ (n − 1) max{η1 , η2 },

where 





⎧ ⎨

⎫ ⎬

⎧ ⎨



β2 (i0 ) η1 = max max β1 (j, i0 ), 1 + max max , β2 (i0 ) , j ∈Q j∈Q bjj − β2 (i0 )Rj (B+ ) ⎫

⎬ β2 (j1 ) η2 = max ⎩max β1 (j, j1 ), 1 + max ⎩max , β2 (j1 ) . ⎭ ⎭ j= / j1 , j= / j1 , b − β (j )R (B+ ) jj 2 1 j j ∈Q j ∈Q In particular, if |J (B+ )|  2, it holds that max

d∈[0,1]n

−1

(I − D + DM )



∞ (n − 1) max η1 ,



1

 min minj∈Q {bjj



− Rj (B+ )}, 1

.

 := I − D + DM is a DB-matrix for Proof. We ﬁrstly verify (1). It is straightforward to check that M each diagonal matrix D = diag(di ) with 0  di  1. Note that M = B+ + C , with B+ and C given in (2.1), then we can write  M

= I − D + DM = I − D + D(B+ + C ) = (I − D + DB+ ) + DC .

(3.1)

It follows from Lemma 2.1 that B+ is a strictly doubly diagonally dominant matrix with positive diagonal

elements. Then it is straightforward to check that  B = (bˆ ij ) := I − D + DB+ is also a strictly doubly  = diagonally dominant matrix with positive diagonal elements. Due to (3.1), M B+ C, where  C := DC, and as  B is nonsingular, we can write  −1 M

C ))−1 = (I +  C )−1 B(I +  B −1  B −1  B −1 = (

and thus  −1 ∞  (I +  M C )−1 ∞  B −1  B−1 ∞ .

(3.2)

Now, we ﬁrst consider the upper bound for  B−1 ∞ . Since  B is a strictly doubly diagonally dominant matrix with positive diagonal elements, then by Lemma 2.2, we have

834

P.-F. Dai / Linear Algebra and its Applications 434 (2011) 830–840

 B−1 ∞  max j= / i, i,j∈N

i.e., for di , dj

bˆ jj bˆ ii bˆ jj

+ Ri ( B)

− Ri ( B)Rj ( B)

,

∈ [0, 1],

 B−1 ∞  max j= / i, i,j∈N

where

+ dj bjj + di Ri (B+ ) = max γ (j, i), j= / i, (1 − di + di bii )(1 − dj + dj bjj ) − di Ri (B+ )dj Rj (B+ ) i,j∈N 1 − dj

(3.3)

+ dj bjj + di Ri (B+ ) , i, j ∈ N . (1 − di + di bii )(1 − dj + dj bjj ) − di Ri (B+ )dj Rj (B+ ) 1 − dj

γ (j, i) :=

∈ N be such that γ (j∗ , i∗ ) = max γ (j, i).

Let i∗ , j∗

(3.4)

j= / i, i,j∈N

Then

+ dj∗ bj∗ j∗ + di∗ Ri∗ (B+ ) (1 − di∗ + di∗ bi∗ i∗ )(1 − dj∗ + dj∗ bj∗ j∗ ) − di∗ Ri∗ (B+ )dj∗ Rj∗ (B+ ) 1 − d j∗ + d j ∗ b j∗ j∗ = (1 − di∗ + di∗ bi∗ i∗ )(1 − dj∗ + dj∗ bj∗ j∗ ) − di∗ Ri∗ (B+ )dj∗ Rj∗ (B+ ) di∗ Ri∗ (B+ ) + (1 − di∗ + di∗ bi∗ i∗ )(1 − dj∗ + dj∗ bj∗ j∗ ) − di∗ Ri∗ (B+ )dj∗ Rj∗ (B+ ) = f (dj∗ , di∗ ) + g (di∗ , dj∗ ), 1 − d j∗

γ (j∗ , i∗ ) =

where di∗ , dj∗

∈ [0, 1],

+ d j∗ b j∗ j∗ , (1 − di∗ + di∗ bi∗ i∗ )(1 − dj∗ + dj∗ bj∗ j∗ ) − di∗ Ri∗ (B+ )dj∗ Rj∗ (B+ ) di∗ Ri∗ (B+ ) . g (di∗ , dj∗ ) = (1 − di∗ + di∗ bi∗ i∗ )(1 − dj∗ + dj∗ bj∗ j∗ ) − di∗ Ri∗ (B+ )dj∗ Rj∗ (B+ ) f (dj∗ , di∗ )

1 − dj∗

=

Observe that f (dj∗ , di∗ )  max f (dj , di∗ ) dj ∈[0,1]

= max

dj ∈[0,1]

=

1 d

(1 − di∗ + di∗ bi∗ i∗ ) − di∗ Ri∗ (B+ ) 1−dj +dj j bj

∗ j∗

1

(1 − di∗ + di∗ bi∗ i∗ ) − di∗ Ri∗ (B+ ) bj 1j Rj∗ (B+ ) ∗∗

=

1 − di∗

 max

di ∈[0,1]

1





+ di∗ bi∗ i∗ − Ri∗ (B+ ) bj 1j Rj∗ (B+ ) ∗∗

1 − di



1

.

+ di bi∗ i∗ − Ri∗ (B+ ) bj 1j Rj∗ (B+ ) ∗∗

For 1 − di



1

,

+ di bi∗ i∗ − Ri∗ (B+ ) bj 1j Rj∗ (B+ ) ∗∗

Rj∗ (B+ )

(3.5)

P.-F. Dai / Linear Algebra and its Applications 434 (2011) 830–840

835

we consider the function

ϕ(x) = For x

1 1 − x + xa

,

a

> 0.

(3.6)

∈ [0, 1], ϕ(x) > 0, and ϕ (x)  0 if a < 1 otherwise ϕ (x)  0. Thus we get 

max

x∈[0,1]

ϕ(x) =

a < 1; a  1.

1 , a

1,

(3.7)

This, together with B+ being strictly doubly diagonally dominant matrix with positive diagonal entries, implies f (dj∗ , di∗ )  max

di ∈[0,1]



1 − di

= max

1





+ di bi∗ i∗ − Ri∗ (B+ ) bj 1j Rj∗ (B+ ) ∗∗



b j ∗ j∗

b i∗ i ∗ b j∗ j∗

− Ri∗ (B+ )Rj∗ (B+ )

,1

.

(3.8)

On the other hand, g (di∗ , dj∗ )  max g (di , dj∗ ) di ∈[0,1]

= max

di ∈[0,1]

di Ri∗ (B+ )

(1 − di + di bi∗ i∗ )(1 − dj∗ + dj∗ bj∗ j∗ ) − di Ri∗ (B+ )dj∗ Rj∗ (B+ ) Ri∗ (B+ )

= max  1 di ∈[0,1]

=

di



− 1 + bi∗ i∗ (1 − dj∗ + dj∗ bj∗ j∗ ) − Ri∗ (B+ )dj∗ Rj∗ (B+ ) Ri∗ (B+ )

+ dj∗ bj∗ j∗ ) − Ri∗ (B+ )dj∗ Rj∗ (B+ ) Ri∗ (B+ )  max dj ∈[0,1] bi i (1 − dj + dj bj j ) − Ri (B+ )dj Rj (B+ ) ∗∗ ∗∗ ∗ ∗ bi∗ i∗ (1 − dj∗

= max

dj ∈[0,1]

1 − dj



Ri∗ (B+ ) bi∗ i∗

.

R i∗ ( B + ) Rj∗ (B+ ) bi∗ i∗

+ d j b j∗ j∗ −

By (3.6), (3.7) and B+ being strictly doubly diagonally dominant matrix with positive diagonal entries, this implies g (di∗ , dj∗ )  max

dj ∈[0,1]



= max

1 − dj



Ri∗ (B+ ) bi∗ i∗

+ d j b j∗ j∗ − Ri∗ (B+ )

b i ∗ i∗ b j∗ j∗



Ri∗ (B+ ) Rj∗ (B+ ) bi∗ i∗

− Ri∗ (B+ )Rj∗ (B+ )

,

Ri∗ (B+ )



b i∗ i∗

Therefore, it follows from (3.5), (3.8), (3.9) and i∗ , j∗ ∈ N that   b j ∗ j∗ γ (j∗ , i∗ )  max ,1 bi∗ i∗ bj∗ j∗ − Ri∗ (B+ )Rj∗ (B+ )   Ri∗ (B+ ) Ri∗ (B+ ) + max , bi∗ i∗ bj∗ j∗ − Ri∗ (B+ )Rj∗ (B+ ) b i∗ i∗

.

(3.9)

836

P.-F. Dai / Linear Algebra and its Applications 434 (2011) 830–840

 max

⎧ ⎨ max

j= / i, i,j∈N

⎫ ⎬

bjj

,1 − Ri (B+ )Rj (B+ ) ⎭

bii bjj

(3.10)

⎫ Ri (B+ ) ⎬ + max ⎩max , max . j= / i, b b − R (B+ )R (B+ ) i∈N bii ⎭ ii jj i j ⎧ ⎨

Ri (B+ )

i,j∈N

B−1 ∞ as follows: Hence, by (3.3), (3.4) and (3.10) we have an upper bound for  ⎧ ⎫ ⎨ ⎬ bjj  B−1 ∞  max max ,1 ⎩ j=/ i, bii bjj − Ri (B+ )Rj (B+ ) ⎭ i,j∈N

⎧ ⎨ + max ⎩max j= / i, b b ii jj i,j∈N

⎫ Ri (B+ ) ⎬ . , max − Ri (B+ )Rj (B+ ) i∈N bii ⎭ Ri (B+ )

(3.11)

We can get the following formula: C )−1 ∞  n − 1, B −1  (I + 

(3.12)

whose proof is similar to that of Theorem 2.2 of [6]. For completeness, we give the proof as follows. B is also an nonsingular Notice that the matrix B+ of (3.1) is an nonsingular M-matrix and so  M-matrix by Theorem 2.3 of Chapter 6 of [3]. Thus  B−1 =: (b˜ )ij  0 for all i, j ∈ N. Observe that C is a nonnegative matrix of rank 1, we deduce that it also holds for  C = DC and we can write it as  C = (c1 , . . . , cn )T e, where e = (1, . . . , 1) and ci = di ri  0. Then we can write ⎛ ⎞ w1 ··· w1 1 + w1 ⎜ w2 1 + w2 ··· w2 ⎟ ⎜ ⎟ I + C =⎜ B −1  .. .. ⎟ .. .. ⎝ . . . ⎠ . wn wn · · · 1 + wn and

1 − 1+n1 w i =1 i

B −1  (I +  C )−1 =

where wi

:=

⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝

w

− 1+wn2 wi i =1 .. . − 1+wnn wi i =1

n

˜ j=1 bij cj  0, i

− 1+wn1

i =1

wi

1 − 1+n2 w i =1 i w

− 1+

.. .

wn  n

i =1

wi

··· ··· ..

.

···

− 1+wn1

i =1

wi

⎟ ⎟

− 1+wn2 wi ⎟ ⎟ ⎟, i =1 ⎟ .. ⎟ ⎠ . w n 1 − 1 + n w i i =1

∈ N. Therefore, we can conclude that

(I +  C )−1 ∞ = 1 + B −1 

(n − 2) maxi wi  1 + ( n − 2 ) = n − 1.  1 + ni=1 wi

Hence, by (3.1), (3.2), (3.11) and (3.12) the result (1) holds. Now, we consider (2). If M is a B-matrix, then B+ is a strictly diagonally dominant matrix with positive diagonal entries and so  B is also a strictly diagonally dominant matrix with positive diagonal entries, that is, Q = N, it follows from (2) of Lemma 2.2 and (3.3) that B−1 ∞  max  j= / j1 , j1 ,j∈N

+ dj bjj + dj1 Rj1 (B+ ) = max γ (j, j1 ), j= / j1 , (1 − dj1 + dj1 bj1 j1 )(1 − dj + dj bjj ) − dj1 Rj1 (B+ )dj Rj (B+ ) j ,j∈N 1 − dj

By the same principle of (3.4)–(3.12) it is not difﬁcult to obtain that max

d∈[0,1]n

(I − D + DM )−1 ∞ (n − 1)η,

1

P.-F. Dai / Linear Algebra and its Applications 434 (2011) 830–840

837

where ⎧ ⎨

η = max max ⎩ j= / j1 , j ∈N

⎧ ⎨

⎫ ⎬

bjj

bj1 j1 bjj

,1 − Rj1 (B+ )Rj (B+ ) ⎭

⎫ Rj1 (B+ ) ⎬ + max ⎩max , . + + j= / j1 , b b j1 j 1 ⎭ j1 j1 bjj − Rj1 (B )Rj (B ) Rj1 (B+ )

j ∈N

Thus the result (2) follows. Next, we turn to (3). If M is a DB-matrix but not a B-matrix, by Proposition 2.1 in [6], B+ is a strictly doubly diagonally dominant matrix with positive diagonal entries but not a strictly diagonally dominant matrix with positive diagonal entries, that is, Q = / N and there exists i0 ∈ N − Q such that bi0 i0  Ri0 (B+ ), then according to (3) of Lemma 2.2 and (3.3) we have that ⎫ ⎧ ⎬ ⎨ − 1 B ∞  max max γ (j, i0 ), max γ (j, j1 ) .  ⎭ ⎩ j ∈Q j= / j1 , j ∈Q

Then by the same principle of (3.1)–(3.12) it is not difﬁcult to obtain that max

d∈[0,1]n

(I − D + DM )−1 ∞ (n − 1) max{η1 , η2 },

where 







η1 = max max β1 (j, i0 ), 1 + max max ⎧ ⎨

j ∈Q

j ∈Q

⎧ ⎨

⎫ ⎬

β2 (i0 ) , β2 (i0 ) , bjj − β2 (i0 )Rj (B+ )

(3.13)

⎬ β2 (j1 ) η2 = max ⎩max β1 (j, j1 ), 1 + max max , β (j ) . ⎩ j=/ j1 , bjj − β2 (j1 )Rj (B+ ) 2 1 ⎭ ⎭ j= / j1 , j ∈Q j ∈Q In particular, if |J (B+ )|  2, it is not difﬁcult to get by (3) of Lemma 2.2, (3.13) and the bound of Theorem 2.2 of [6] that   1   . max (I − D + DM )−1 ∞ (n − 1) max η1 , d∈[0,1]n min minj∈Q {bjj − Rj (B+ )}, 1 We complete the proof.



Remark 3.2. For the case that M is a B-matrix, the bound of the result (2) is smaller than the bound of Theorem 2.2 of [6] in some cases. For instance, Example 4.3. Hence, according to the result (2) and the bound of Theorem 2.2 of [6], a new bound for the case that M is a B-matrix is as follows:   n−1 −1   , max (I − D + DM ) ∞  min (n − 1)η, d∈[0,1]n min minj∈N {bjj − Rj (B+ )}, 1 where

⎧ ⎨

⎫ ⎬

⎧ ⎨

⎬ β2 (j1 ) η = max ⎩max β1 (j, j1 ), 1⎭ + max ⎩max , β2 (j1 ) . ⎭ j= / j1 , j= / j1 , b − β (j )R (B+ ) jj 2 1 j j ∈N j ∈N Remark 3.3. If M is also a Z-matrix, that is, B+ max

d∈[0,1]n

−1

(I − D + DM )

−1

∞ = B

= M and C is the null matrix, by (3.1) one can obtain

∞ .

838

P.-F. Dai / Linear Algebra and its Applications 434 (2011) 830–840

Thus the bounds of Theorem 3.1 transform into the lower bounds (n  3), which do not contain the factor n − 1, corresponding to Theorem 3.1 as follows. (1) It holds that max

d∈[0,1]n

(I − D + DM )−1 ∞ ⎧ ⎨

⎫ ⎬

⎧ ⎨

⎫⎞

⎬ β2 (i)  ⎝max max β1 (j, i), 1 + max max , max β2 (i) ⎠ . + ⎩ j=/ i, ⎭ ⎩ j=/ i, bjj − β2 (i)Rj (B ) i∈N ⎭ i,j∈N i,j∈N (2) It follows that max

d∈[0,1]n

(I − D + DM )−1 ∞  η,

where

⎧ ⎨

⎫ ⎬

⎧ ⎨

⎬ β2 (j1 ) η = max ⎩max β1 (j, j1 ), 1⎭ + max ⎩max , β2 (j1 ) . ⎭ j= / j1 , j= / j1 , b − β (j )R (B+ ) 2 1 j jj j ∈N j ∈N (3) It follows that max

d∈[0,1]n

(I − D + DM )−1 ∞  max{η1 , η2 },

where 





⎧ ⎨

⎫ ⎬

⎧ ⎨



β2 (i0 ) η1 = max max β1 (j, i0 ), 1 + max max , β2 (i0 ) , j ∈Q j∈Q bjj − β2 (i0 )Rj (B+ ) ⎫

⎬ β2 (j1 ) η2 = max ⎩max β1 (j, j1 ), 1⎭ + max ⎩max , β2 (j1 ) . ⎭ j= / j1 , j= / j1 , b − β (j )R (B+ ) jj 2 1 j j ∈Q j ∈Q In particular, if |J (B+ )|  2, it holds that max

d∈[0,1]



(I − D + DM )−1 ∞  max η1 , n





1

min minj∈Q {bjj

− Rj (B+ )}, 1



.

4. Numerical examples In this section we give some examples that are used to illustrate our theoretical results. The norm

 · ∞ in Example 4.2 is obtained by using Matlab 7.1.

Example 4.1. Let us ﬁrst consider the following P-matrix from [5,8,7]   1 −4 M1 = . 5 7 +

We write M1 as M1 = B1 + C1 , where     1 −4 0 0 + , , C1 = B1 = 5 5 0 2 +

B1 is a strictly doubly diagonally dominant matrix with positive diagonal entries and so M1 is a DB-matrix but neither a B-matrix nor an H-matrix. By simple computations, we obtain that

P.-F. Dai / Linear Algebra and its Applications 434 (2011) 830–840

max

j= / i, i,j∈{1,2}

β1 (j, i) = 1,

max

i∈{1,2}

β2 (i) = 4,

max

j= / i, i,j∈{1,2}

bjj

839

β2 (i) = 2, − β2 (i)Rj (B1+ )

and thus the upper bound (1) of Theorem 3.1 is 5. Example 3.1 of [8] by solving an optimization problem show max

d∈[0,1]n

(I − D + DM1 )−1 ∞ = 5.

Hence, this indicates that the upper bound of Theorem 3.1 is sharp for this example and is obtained with small computational cost. Final remarks in [7] cited the LCP (M1 , q) and the error bounds (2.9) of [7] for the LCP (M, q) with M being P-matrix but not H-matrix with positive diagonal entries have not been obtained so far by solving a system of linear equations. Example 4.2. Let us now consider the matrix ⎛ ⎞ 10 −4 −6 ⎝ 12 2 ⎠, M2 = −7 −8 1 11 which is simultaneously a DB-matrix and an H-matrix but not a B-matrix. Now, we use the upper + bound of Theorem 3.1 to estimate maxd∈[0,1]n (I − D + DM2 )−1 ∞ . We write M2 as M2 = B2 + C2 , where ⎛ ⎛ ⎞ ⎞ 10 0 0 0 −4 −6 + 10 0 ⎠ , C2 = ⎝2 2 2⎠ . B2 = ⎝−9 1 1 1 −9 0 10 It follows from some simple calculations that max

j∈{2,3}

β1 (j, 1) = 1, β2 (1) = 1,

β2 (1) 1   = 1. = 1, + + j∈{2,3} bjj − β2 (1)Rj (B ) min minj∈{2,3} {bjj − Rj (B2 )}, 1 2 max

So the upper bound (3) of Theorem 3.1 is 4, which is considerably smaller than the bound ⎛ ⎞⎛ ⎞  0.4194 0.1613 0.2581 10 0 0    −1  ⎝ ⎠ ⎝ 0 12 0 ⎠ M2  max(∧, I )∞ =  0.3000 0.2000 0.2000  = 8.9677  0.3323 0.1355 0.2968 0 0 11 ∞ for H-matrices given by formula (2.4) of [8]. Example 4.3. Let us assume that k   k − ka . M3 = 0 k +

> 0, a > 1 and

+

+

We write M3 as M3 = B3 + C3 , where B3 = M3 and C3 is the null matrix, Obviously, B3 is a strictly diagonally dominant matrix with positive diagonal entries and so M3 is a B-matrix and an H-matrix. By simple computations, we get the result (2) of Theorem 3.1 given by     1 1 1 η = max , 1 + max , k ak a and the bound of Theorem 2.2 of [6] is max{ (a−a1)k , 1}. It is not difﬁcult to verify that when 0 a2

a 2 −1

, 

η < max

a

(a − 1)k

 ,1 ,

840

P.-F. Dai / Linear Algebra and its Applications 434 (2011) 830–840

that is, the result (2) of Theorem 3.1 is smaller than the bound of Theorem 2.2 of [6] in this case. Furthermore, it is interesting that for all k > 0, the bounds of the result (2) of Remark 3.3 is equal to the bound (2.3) of [14].

Acknowledgments The author wish to thank the referees for their corrections and suggestions on an earlier version of the manuscript.

References [1] J.M. Peña, A class of P-matrices with applications to the localization of the eigenvalues of a real matrix, SIAM J. Matrix Anal. Appl. 22 (2001) 1027–1037. [2] J.M. Peña, On an alternative to Gershgorin circles and ovals of Cassini, Numer. Math. 95 (2003) 337–345. [3] A. Berman, R. Plemmons, Nonnegative Matrices in the Mathematical Sciences, Academic Press, New York, 1979. [4] Cottle, J.S. Pang, R.E. Stone, The Linear Complementarity Problem, Academic Press, San Diego, 1992. [5] U. Schäer, A linear complementarity problem with a P-matrix, SIAM Rev. 46 (2004) 189–201. [6] M. García-Esnaola, J.M. Peña, Error bounds for linear complementarity problems for B-matrices, Appl. Math. Lett. 22 (2009) 1071–1075. [7] Z.Y. Wang, Y.X. Yuan, Componentwise error bounds for linear complementarity problems, IMA J. Numer. Anal. 4 (2009) 1–10. [8] X.J. Chen, S.H. Xiang, Computation of error bounds for P-matrix linear complementarity problems, Math. Program. Ser. A 106 (2006) 513–525. [9] X.J. Chen, S.H. Xiang, Perturbation bounds of P-matrix linear complementarity problems, SIAM J. Optim. 18 (2007) 1250– 1265. [10] R. Mathias, J.S. Pang, Error bounds for the linear complementarity problem with a P-matrix, Linear Algebra Appl. 132 (1990) 123–136. [11] R. Brualdi, H. Ryser, Combinatorial Matrix Theory, Encyclopedia of Mathematics and Its Applications, vol. 39, Cambridge University Press, 1991. [12] B. Li, M. Tsatsomeros, Doubly diagonally dominant matrices, Linear Algebra Appl. 261 (1997) 221–235. [13] S.Z. Pan, S.C. Chen, An upper bound for A−1  of strictly doubly diagonally dominant matrices, J. Fuzhou Univ. Nat. Sci. Ed. 36 (2008) 639–642. (in Chinese). [14] M. García-Esnaola, J.M. Peña, A comparison of error bounds for linear complementarity problems of H-matrices, Linear Algebra Appl. 433 (2010) 956–964.