Vol.17 No.1
ACTA M A T H E M A T I C A E A P P L I C A T A E SINICA
Jan., 2001
SOME INVERSE M-MATRIX PROBLEMS* XIANG
SHUHUANG ( ~ ' ~ k . ~ )
(Department of Applied Mathematics and Software, Central South University of Technology, Changsha 410083, China) YOU
ZHAOYONG ('~j~g~Tjr
(Department of Mathematics, Xi 'an Jiaotong University, Xi 'an 710049, China)
Abstract An upper bound and a lower bound for ao are given such that aI+BE.M -1 for a>ao and aI+Bf~.h,t -1 for a_
Nonnegative matrix, inverse M-matrix, M-matrix
1.
Introduction
Johnson in [1] gave an overview about inverse M - m a t r i x problems and proved t h a t if B is a power invariant zero pattern matrix, then there is a positive diagonal matrix D such that B + D is an inverse M-matrix. He also put several open problems such as Question. Consider B E Af such that a I + B has power invariant zero p a t t e r n for a :> 0, where Af denotes the set of n • n nonnegative matrices, I is the n • n identity matrix. How may a0, a function of B, be characterized such that a I --k B E . M - 1
for a > ao
aI + B ~ .~-1
for a _< a0
and are satisfied? The difficulty of characterizing all nonnegative matrices whose inverses are M-matrices has led to the study of the general properties of inverse M-matrices and to the identification of particular classes of such matrices such as type of D matrices (see [2]), ultrametric matrices (see [3]), generalized ultrametric matrices (see [4,5]). In this paper, we confine ourselves to power invariant zero p a t t e r n matrices. Let B = (bij) E R n'n and put S -- ( 1 , 2 , - - . ,n}. We denote the class of n • n M matrices by A.{ and, denote the class of n • n inverse M-matrices by A/1-1. Af is denoted as above, and :D (respectively ~ ) is denoted as the class of n • n diagonal matrices whose Received January 4, 1998. Revised October 11, 1999. * This project is supported by Science and Art Foundation of Central South University of Technology.
No. 1
SOME INVERSE M-MATRIX PROBLEMS
15
diagonal entries are positive (respectively nonnegative) real numbers. We denote the spectral radius of an n-by-n m a t r i x C by p(C) and diag B by the diagonal matrix whose entries are a l l , a 2 2 , " "", ann, offdiag B = B - diagB. D e f i n i t i o n 1 [1]. Let B E AY and k be any positive integer. B is called a power invariant zero p a t t e r n m a t r i x if it satisfies the condition t h a t the (i, j) entry of B k is zero if and only if the ( i , j ) entry of B is zero. T h e o r e m A [1]. Suppose t h a t B E M -1. T h e n B is a power invariant zero p a t t e r n matrix. T h e o r e m B [1]. Suppose t h a t B E A/"+, where A/+ denotes the set of n • n nonnegative matrices whose diagonal entries are positive. T h e n there is a D E ~ such t h a t B + D E Az1-1 if and only if B 2 and B have the same zero pattern. Before proving the main results, we first introduce some properties of power invariant zero p a t t e r n matrices. P r o p e r t y 1. Suppose t h a t B E A / i s a power invariant zero p a t t e r n matrix. T h e n there is a nonnegative constant r such t h a t b~2) < rb~j, where B 2 = (b12)). Proos
According to Definition 1, for k = 2, bl~ ) = 0 if and only if b~j -- 0. Let
r = m a x ( t i b ~ ) = tbij for b~j ~ O,i,j 9 S}. T h e n for b~j # O, i,j 9 S, bl~) <_ rblj. T h e above inequalities are also true for bij = 0, i, j 9 S. P r o p e r t y 2. If B is a power invariant zero p a t t e r n matrix and B # 0, then there exists a positive constant r such t h a t
bij >_ r min (b~k;bkj}, l
Proos
V i , j E S.
Let r =
min i,jES
( min{bik, bkj } bik # O, bkj # O, k E S .
Since B is a power invariant zero p a t t e r n matrix, it is nonnegative. So we have r > 0. Let i , j E S be such t h a t blj = 0. Claim: bik 9 bkj = 0 for all k = 1 , 2 , - - - , n . To see this, we consider B 2 = (bij). (2)
B y Definition 1, we have 0 = bl~) = f i bikbkj. k=l
From this, we see t h a t the claim holds since the entries of B are nonnegative. It follows from the above discussion t h a t r > 0. It is clear t h a t this positive constant r satisfies the required inequalities. N o t e . Let a power invariant zero p a t t e r n m a t r i x B be nonnegative symmetric strictly row and column diagonally d o m i n a n t of its entries. If r > 1, then B is a strictly ultrametric matrix. B y the definition of power invariant zero p a t t e r n matrix, we are easy to get t h a t P r o p e r t y 3. Let B E Af. For any positive constant a, a I + B is a power invariant zero p a t t e r n matrix if and only if there exists a nonnegative constant r such t h a t offdiagB 2 _< r 9 offdiagB. Let B be a nonnegative matrix. P u t 0, A0 -
if B has none eigenvalue with negative real part, rain{Re (A)1% is an eigenvalue of B and Re (A) < 0},
otherwise.
T h e o r e m 1. Suppose t h a t B is a nonnegative m a t r i x and t h a t there is a nonnegative constant 7 satisfying that. B 2 <_ 7 B . Define 70 = rain {71 B2 -< 7 B } . If 0 < A0, t h e n A0 _< c~0 _< 70 such t h a t
aI+BEM
-1 for a > a o ;
aI+B~M
-1 for a _ < s 0 .
16
ACTA MATHEMATICAE APPLICATAE SINICA
Vol. 17
Proof. First, suppose that a > p(B), then (aI + B) -1 may be written as
B2 o--~- . . . . )
D
(,+
Bs
,
.
I a
B(I_~2)-1 as
I
+ B4 +...)+
Bs ( I + B2
+ B4
+...)
Bs B2 + _~_y( i _ _ ~ ) - 1
(
1 (aB - B 2) I (23
(1)
-~
Since a > p(B) and B is a nonnegative matrix, we see that I ( B~) -1 M-matrix and I - ~ _> 0.
S 2 -
~-v
must be a nonsingular
If a > max (p(B), 7o), then
aB - B s > 0
-~(aB-
and
B 2 ) ( I - B 2 ~] - l ->
So the offdiagonal entries of (aI + B) -1 are nonpositive. But a I + B is non_negative, so (aI + B) -1 must be an M-matrix. That is to say, a I + B is an inverse M-matrix. Suppose that there exists an a satisfying a < Ao and a I + B is an inverse M-matrix. Then a I + B + (A0 - a ) I is also an inverse M-matrix due to Johnson (see [1]). But according to the definition of A0, there is an eigenvalue of AoI+B with zero real part, which contradicts the fact that the eigenvalues of inverse M-matrix are of positive real parts. So ao satisfies A0 _< ao ~ max (p(B), 70) such that
a I + B E .M -1 for a > a o ;
a I + B ~.a,4 -1 for a _ < a o .
Since B s _< 7B, then p(B) <_7o. So Ao _< a0 _< 70T h e o r e m 2. Let B be a nonnegative matrix and B satisfy the condition that offdiagB2 -< 7" offdiagB. Let 70 = min{71offdiag Bs -< 7" off diagB}. If 0 < Ao, then Ao _< ao _< 3/3 + 70 such that
a I + B E A A -1 for a > a o ;
aI+B!~M
-1 for a < a 0
where/3 -- ~/'Y~1762
Proos Since B is nonnegative, by Perron-Frobenius Theorem, we have p(B s) -- p(B) s and p(B s) _> b2-**, i = 1, 2, 99-, n. So diag B 2 ~ p(B)2I, (B +/3i)s =offdiag(B 2) + diagB s + 2/3B + <70 offdiagB +
321
p(B)2I + 2/3B +/321 (2)
<(70 + 2/3)B + (p(B) s +/3s)i. Since 70 + 2~3 =~/72 + 4p(B) 2, p(S)2 + f12 =p(B)2 +
+ 4p(B) s + 78 - 270V/7 4
+ 4p(S)2
No. 1
SOME INVERSE M-MATRIX PROBLEMS 7o 2 + 4p(B) 2
7o V/7o 2 + 4p(B) 2
2
2
=~/702+4p(B)2( r
17
)
=/3\/3,02 + 4p(B) 2 =/3(2/3 + 70).
(3)
So by formulas (2) and (3), we have (B + / 3 I ) 2 _< (2/3 + 3"o)(B +/31). By T h e o r e m 1, we have t h a t for B +/3I, a~ < 2/3 + 7o such t h a t
a I + B + /3I E.M - i
for a > a'o.
Thus, for B, we have the following estimation a b o u t the u p p e r b o u n d of no: ao < 3/3 + 7oBy the same discussion as in the proof of T h e o r e m 1, A0 < a0. Hence A0 < a0 < 3/3 + 7oE x a m p l e 1. Consider the m a t r i x
B=
[!1 1 1 2
1 5 1 2
,
T h e n 3'o = 26.5, a0 = 24.5. E x a m p l e 2. Let B=
B2=
6.25 |26.5
[8
EzI ] 0 1
2.5 4.5 5.75
6.5 ] 2.5 . 7.75
.
T h e n according to T h e o r e m 2, t3 < 0.8, 3"0 = 25, 3/3 + 3"0 < 27.4, a0 = 25. Willoughby in [6] gave a sufficient condition for a positive n x n m a t r i x A = (aij), where A has been scaled to have unit diagonal elements and offdiagonal elements satisfying 0 < y G aij < x < 1. Define an interpolation p a r a m e t e r s via x 2 = sy+ (1 - s)y 2, t h e n A - i is a strictly diagonally d o m i n a n t (both by rows and by columns) M - m a t r i x if n = 2, or if n>3ands-i>n-2. C o r o l l a r y 1. Suppose A E R n'n is a nonnegative m a t r i x with unit diagonal elements satisfying offdiag(A 2) < 3". offdiagA, 3p(offdiagA) + 3' < 1. T h e n A E 2~4- i . Proof. Let B = offdiagA. T h e n offdiag B = offdiagA and offdiagB 2 _< offdiagA 2 _< 7 9offdiagA = 3" 9 offdiagB. By T h e o r e m 2, for B, ao < 3/3 + 7- Since t3 < p(B) and 3/3 + 7 < 3p(B) + 7 < 1, according to T h e o r e m 2, t h e n A = I + B is an inverse M - m a t r i x . T h e o r e m 3. Suppose B E A/" satisfying S 2 = 3"B. T h e n for any positive constant a ,
a I + B E ~4 -i. Proof. (i) If B = 0, it is true obviously. (ii) If B # 0, t h e n 3' > 0. Suppose t h a t A is a nonzero eigenvalue of B, eigenvector. T h e n B x = Ax. By B 2 = 7 B , we have B2x = A2x = TAX. So A = 7.
x is the
18
ACTA M A T H E M A T I C A E A P P L I C A T A E SINICA
Vol. 17
Since the minimal polynomial of matrix B is #2 _ V# = 0 and is irreducible, then there exists a nonsingular matrix P such that
"7 7 p-1Bp
=
7
=7
[Ik
0
]
'
k = rank B.
(4)
0
Then
Denote P = ( P l , P 2 , " " ,Pn), p - 1 = ( q l , q 2 , " " ,q,O T- T h e n B = 7 (pl, p2, 9 9 9 pk) (ql,
9 9 9 qk) r
and ( q l , q2, 9
Let P = ( P l , P 2 , ' " , P k ) , positive a we have
,
qk)T(pl ,P2,''" ,Pk) = Ik.
Q = ( q l , q 2 , ' " , q k ) T. By Sherman-Morrison formula, for any
(I + a P Q ) -1 = I - aP_~Q = I ~---ff--. l B . l+a 1+~ 7 The offdiagonal entries of ( I + a P Q ) -1 are nonpositive. So ( I + a P Q ) is an inverse M - m a t r i x . T h a t is to say, for any positive constant a , a I + B E A,t -1. C o r o l l a r y 2. Suppose that B E Af satisfies that B 2 -- 7B. (i) If B is an irreducible matrix, then rank B = 1 and B can be written as
where 7 > 0 and ~, ~/are nonnegative n x 1 vectors satisfying ~ T ~ __ 1. (ii) If B is nonsingular, then B = 7 I . Proof. (i) By the proof of T h e r o e m 3, since B satisfies B 2 = 7 B and B is a nonnegative irreducible matrix of form (4), 7 must be positive and is the unique largest simple eigenvalue of B. So r a n k B = 1, B = 7Plq T and qTpl = 1. Since B is nonnegative, the nonzero entries in Pl, ql must be of the same signs9 So we can select nonnegative n x 1 vectors ~, 7/satisfying B = 7~rl T and rlT~ = 19 (ii) In the same way, since B is nonsinguIar, according to form (4), we have rank B = n and B = 7 P I P -1 = 7I. T h e o r e m 4. Suppose t h a t B E A/" is a nonzero matrix. Then B 2 = 7 B if and only if B can be written as B = 7 P Q , where 7 is a nonnegative constant, P is an n x k m a t r i x and Q is a k x n matrix satisfying P Q >_ 0 and Q P = Ik, k = rankB. Proof. Sufficiency: Suppose B 2 = 7B. According to the proof of T h e o r e m 3, there exists a nonsingular matrix P such t h a t
B=7P[
Ik
o ] P -1,
k = r a n k B > 0.
No. 1
SOME INVERSE M-MATRIX PROBLEMS
19
D e n o t e P = ( P l , P 2 , " " ,P=), p - 1 = ( q l , q 2 , " " ,q=)T. T h e n
B = 7 ( P l , P 2 , " " ,Pk)(ql, q 2 , ' " , qk) T and
( q l , q 2 , ' ' ' , q k ) T ( p l , P 2 , ' ' " ,Pk) = Ik. Let P = ( P l , P 2 , " " ,Pk), -Q = ( q l , q 2 , " " ,qk) T. T h e n B = 7 P Q > 0 a n d P Q = Ik. Necessity: Since B 2 = ( T P Q ) 2 = 7 2 P Q P Q = 72PQ, = 7 B , t h e n T h e o r e m 4 is true. Acknowledgement. We are grateful to t h e referee for much useful suggestion a n d helpful c o m m e n t s . T h e first a u t h o r shows his g r a t i t u d e to N a n k a i University for the h o s p i t a l i t y he received d u r i n g his doing p o s t d o c t o r a l research at N a n k a i University. References 1 C.B.. Johnson. Inverse M-Matrices. Linear Algebra AppI., 1982, 47:195-216 2 T.L. Markham. Nonnegative Matrices whose Inverses are M-matrices. Proc. Amer. Math. Soc., 1972, 36:326-330 3 S. Martinez, G. Michon, and J. San Martin. Inverse of Ultrametric Matrices of Stieltjes Type. SIAM J. Matrix Anal. Appl., 1994, 15:98-106 4 J.J. McDonald, M. Neumann~ H. Schneider, M.J. Tsatameros. Inverse M-matrix Inequalities and Generalized Ultrametric Matrices. Linear Algebra AppI., 1995, 220:321-341 5 R. Nabben, R.S. Varga. Generalized Ultrametric Matrices--a Class of Inverse M-matrices. Linear Algebra Appl., 1995, 220:365-390 6 R.A. Willoughby. The Inverse M-matrix Problem. Linear Algebra Appl., 1977, 18:75-94
