<<

. 3
( 11)



>>

m(V+ ) = m(|V+ |),
˜ ˜
equality (5.6) with V+ = |V+ | yields the ¬rst inequality (5.10). Similarly, the
second inequality (5.10) can be proved. 2
Proof of Theorem 3.4.1: Due to Lemma 3.5.2,

(I + W’ )’1 ¤ mup (A), (I + W+ )’1 ¤ mlow (A).
∞ ∞

Lemma 3.5.3 yields
n’1
(’1)k W’
k
¤ mup (A) ’ 1,

k=1

and
n’1
(’1)k W+
k
¤ mlow (A) ’ 1.

k=1

Hence,
n’1
j
(’1)k+j W’ W+
k
¤ θ(A).

j,k=1

Now the required result follows directly from Lemma 3.5.1. 2



3.6 Positive Invertibility of Matrices
For h = (hk ), w = (wk ) ∈ Rn , we write h ≥ (>) g, if hk ≥ (>) wk , (k =
1, ..., n). A matrix A is (non-negative ) positive: A > (≥) 0, if all its entries
are (non-negative) positive. For matrices A, B we write A > (≥) B if A’B >
(≥) 0.
Again V+ , V’ and D are the upper triangular, lower triangular, and di-
agonal parts of matrix A = (ajk )n j,k=1 , respectively (see Section 3.1).
n
Matrix A = (ajk )j=1,k=1 is called a Z-matrix, if the conditions

ajk ¤ 0 for j = k, and akk > 0 (j, k = 1, ..., n) (6.1)

hold. That is, D > 0, V± ¤ 0.
3.7. Positive Matrix-Valued Functions 45


Lemma 3.6.1 Let A be a Z-matrix, and let condition (4.1) hold. Then A
is positively invertible and the inverse operator satis¬es the inequalities (4.2)
and
A’1 ≥ D’1 . (6.2)

Proof: As it was proved in the previous section, condition (4.1) implies the
invertibility of A. Moreover, relation (5.5) holds. But W± ¤ 0. So
j
(’1)k+j W’ W+ ≥ 0
k


and thus
n’1
j
(’1)k+j W’ W+ ]’1 ≥ 0,
k
[I ’
j,k=1

since
n’1
j
(’1)k+j W’ W+ ¤ θ0 < 1.
k

j,k=1

In addition,
n’1
’1
(’1)k W± ≥ 0.
k
(I + W± ) =
k=1

Now (5.5) implies (6.2). Inequality (4.2) is due to Theorem 3.4.1. 2



3.7 Positive Matrix-Valued Functions
We will call A an anti-Hurwitz matrix if its spectrum σ(A) lies in the open
right half-plane:
β(A) := inf Re σ(A) > 0.

For an anti-Hurwitzian matrix A, de¬ne the matrix-valued function F (A) by

e’At f (t)dt,
F (A) = (7.1)
0

where
e’β(A)t f (t) ∈ L1 [0, ∞). (7.2)

Lemma 3.7.1 Let A be an anti-Hurwitzian Z-matrix. In addition, let rela-
tions (7.1), (7.2) hold, and f (t) ≥ 0 for almost all t ≥ 0. Then

F (A) ≥ F (D) ≥ 0. (7.3)
46 3. Invertibility of Finite Matrices


Since D > 0 and V± ¤ 0, we have
Proof:
e’At = lim (I ’ An’1 )nt = lim (I ’ n’1 D ’ n’1 V )nt ≥
n’∞ n’∞

lim (I ’ n’1 D)nt = e’Dt ,
n’∞
where I is the unit matrix. Thus
∞ ∞
’At
e’Dt f (t)dt = F (D).
f (t)dt ≥
F (A) = e
0 0

As claimed. 2

In, particular, let A be an anti-Hurwitzian matrix, and

ak tsk
f (t) ≡
“(sk + 1)
k=1

(sk = const > 0, ak = const ≥ 0, k = 1, 2, ...),
where “(.) is the Euler Gamma function. Then

ak A’sk ’1 ,
F (A) = (7.4)
k=1

provided the series converges. The following functions are examples of the
functions de¬ned by (7.4):
’1
A’ν , A’ν eb0 A (b0 = const > 0; 0 < ν ¤ 1).
Lemma 3.7.2 Let A be a Z-matrix. Then it is anti-Hurwitzian and satis¬es
the inequality (6.2) if and only if it is positively invertible.
Proof: Let A be anti-Hurwitzian. Then due to Lemma 3.7.1,

’1
e’At dt ≥ D’1 > 0.
A =
0

Conversely, let A be positively invertible. Put T = ’V+ ’ V’ . Then for any
» with Re » ≥ 0,
|(A + »)h| = |(D + » ’ T )h| ≥ |(D + »)h| ’ T |h| ≥ D|h| ’ T |h| = A|h|.
Here |h| means the vectors whose coordinates are the absolute values of the
coordinates of h. This proves the result. 2
Lemma 3.6.1 and the previous lemma imply
Corollary 3.7.3 Let F be de¬ned by (7.1) with a non-negative function f
satisfying (7.2). In addition, let A be a Z-matrix and condition (4.1) hold.
Then relation (7.3) is valid.
3.8. Notes 47


3.8 Notes
As it was mentioned, although excellent computer softwares are now available
for eigenvalue computation, new results on invertibility and spectrum inclu-
sion regions for ¬nite matrices are still important, since computers are not
very useful, in particular, for analysis of matrices dependent on parameters.
So the problem of ¬nding invertibility conditions and spectrum inclusion re-
gions for ¬nite matrices continues to attract attention of many specialists,
cf. (Brualdi, 1982), (Farid, 1995 and 1998), (Gudkov, 1967), (Li and Tsat-
someros, 1997), (Tam et al., 1997) and references given therein.
Let A = (ajk ) be a complex n — n-matrix (n ≥ 2) with the nonzero
diagonal: akk = 0 (k = 1, ..., n). Put
n
|ajk |.
Pj =
k=1, k=j

The well-known Levy-Desplanques theorem states that if |ajj | > Pj (j =
1, ..., n), then A is nonsingular. This theorem has been improved in many
ways. For example, each of the following is known to be a su¬cient condition
for non-singularity of A:
(i) |aii ||ajj | > Pj Pi (i, j = 1, ..., n) ( Marcus and Minc, 1964, p. 149).
(ii) |ajj | ≥ Pj (j = 1, ..., n), provided that at least one inequality is strict
and A is irreducible ( Marcus and Minc, 1964, p. 147).
(iii) |ajj | ≥ rj mj (j = 1, ..., n), where rj are positive numbers satisfying
n
(1 + rk )’1 ¤ 1 and mj = max |ajk | (see (Bailey and Crabtree, 1969).
k=j
k=1

(iv) |ajj | > Pj Q1’ (j = 1, ..., n) where
j
n
0 ¤ ¤ 1, Qj = |akj | ( Marcus and Minc, 1964, p. 150) .
k=1, k=j

Theorems 3.1.1, 3.3.1 and 3.4.1 yield new invertibility conditions which
improve the mentioned results, when the considered matrices are close to
triangular ones. Moreover, they give us estimates for di¬erent norms of the
inverse matrices. Note that Theorems 3.1.1, 2.1.1 and 2.14.1 allow us to
derive additional invertibility conditions in the terms of the Euclidean norm.
The material in Chapter 3 is based on the papers (Gil™, 1997), (Gil™, 1998)
and (Gil™, 2001).


References
[1] Bailey D. W. and D. E. Crabtree, (1969), Bounds for determinants,
Linear Algebra and Its Applications, 2, 303-309.
48 3. Invertibility of Finite Matrices


[2] Brualdi, R.A. (1982), Matrices, eigenvalues and directed graphs, Linear
and Multilinear Algebra, 11, 143-165
[3] Collatz, L. (1966). Functional Analysis and Numerical Mathematics.
Academic press, New York and London.
[4] Farid, F.O. (1995), Criteria for invertibility of diagonally dominant ma-
trices, Linear Algebra and Its Applications, 215, 63-93.

[5] Farid, F.O. (1998), Topics on a generalization of Gershgorin™s theorem,
Linear Algebra and Its Applications, 268, 91-116.
[6] Gil™, M.I. (1997), A nonsingularity criterion for matrices, Linear Algebra
and Its Applications, 253, 79-87.
[7] Gil™, M.I. (1998), On positive invertibility of matrices, Positivity, 2, 165-
170.
[8] Gil™, M.I. (2001), Invertibility and positive invertibility of matrices, Lin-
ear Algebra and and Its Applications, 327, 95-104

[9] Gudkov, V. V. (1967). On a certain test for nonsingularity of matrices,
Latvian Math. Yearbook, 1965, 385-390, (Math. Reviews, 33), review
1323)

[10] Horn, R. A. and Johnson Ch. R. (1991). Topics in Matrix Analysis,
Cambridge, Cambridge University Press.

[11] Krasnosel™skii, M. A., Lifshits, J. and A. Sobolev. (1989). Positive Linear
Systems. The Method of Positive Operators, Heldermann Verlag, Berlin.

[12] Li B. and Tsatsomeros, M.J. (1997), Doubly diagonally dominant ma-
trices, Linear Algebra and Its Applications, 261, 221-235.

[13] Marcus M. and Minc, H. (1964). A Survey of Matrix Theory and Matrix
Inequalities, Allyn and Bacon, Boston.
[14] Tam, B.S., Yang, S. and Zhang. X. (1997) Invertibility of irreducible
matrices, Linear Algebra and Its Applications, 259, 39-70
4. Localization of
Eigenvalues
of Finite Matrices



The present chapter is concerned with perturbations of ¬nite matrices and
bounds for their eigenvalues. In particular, we improve the classical Gersh-
gorin result for matrices, which are ”close” to triangular ones. In addition,
we derive upper and lower estimates for the spectral radius. Under some
restrictions, these estimates improve the Frobenius inequalities. Moreover,
we present new conditions for the stability of matrices, which supplement the
Rohrbach theorem.


4.1 De¬nitions and Preliminaries
In this chapter, . is an arbitrary norm in Cn , A and B are n — n-matrices
having eigenvalues »1 (A), ..., »n (A) and »1 (B), ..., »n (B), respectively, and
q = A’B .
We recall some well-known de¬nitions from matrix perturbation theory
(see (Stewart and Sun, 1990)). The spectral variation of B with respect to A
is
svA (B) := max min |»i (B) ’ »j (A)|.
i j

The Hausdor¬ distance between the spectra of A and B is
hd(A, B) := max{svA (B), svB (A)}.
The matching distance between eigenvalues of A and B is
md(A, B) := min max |»π(i) (B) ’ »i (A)|,
π i


M.I. Gil™: LNM 1830, pp. 49“63, 2003.
c Springer-Verlag Berlin Heidelberg 2003
50 4. Eigenvalues of Finite Matrices


where π is taken over all permutations of {1, 2, ..., n}.
Recall also that σ(A) denotes the spectrum of A.

Lemma 4.1.1 For any µ ∈ σ(B), we have either µ ∈ σ(A), or

q Rµ (A) ≥ 1. (1.1)

Proof: Suppose that the inequality

q Rµ (A) < 1. (1.2)

holds. We can write Rµ (A) ’ Rµ (B) = Rµ (B)(B ’ A)Rµ (A). This yields

Rµ (A) ’ Rµ (B) ¤ Rµ (B) q Rµ (A) . (1.3)

Thus, (1.2) implies

Rµ (B) ¤ Rµ (A) (1 ’ q Rµ (A) )’1 .

That is, µ is a regular point of B. This contradiction proves the result. 2

Lemma 4.1.2 Assume that

R» (A) ¤ φ(ρ’1 (A, »)) for all regular » of A, (1.4)

where φ(x) is a monotonically increasing non-negative function of a non-
negative variable x, such that φ(0) = 0 and φ(∞) = ∞. Then the inequality

svA (B) ¤ z(φ, q) (1.5)

is true, where z(φ, q) is the extreme right-hand (positive) root of the equation

1 = qφ(1/z). (1.6)

Proof: Due to Lemma 4.1.1 and condition (1.4),

1 ¤ qφ(ρ’1 (A, »)) for all » ∈ σ(B).

Since φ(x) monotonically increases, z(φ, q) is a unique positive root of (1.6)
and ρ(A, ») ¤ z(φ, q). Thus, the inequality (1.5) is valid. 2


4.2 Perturbations of Multiplicities
and Matching Distance
Put
„¦(c, r) ≡ {z ∈ C : |z ’ c| ¤ r} (c ∈ C, r > 0).
4.2. Perturbations of Multiplicities 51


Lemma 4.2.1 Under condition (1.4), let A have an eigenvalue »(A) of the
algebraic multiplicity ν and the distance from »(A) to the rest of σ(A) is equal
to 2d, i.e.
distance{»(A), σ(A)/»(A)} = 2d. (2.1)
In addition, for a positive number a ¤ d, let
qφ(1/a) < 1. (2.2)
Then in „¦(»(A), a) operator B has eigenvalues whose total algebraic multi-
plicity is equal to ν.
Proof: This result is a particular case of the well-known Theorem 3.18
(Kato, 1966, p. 215). 2

Since φ is a nondecreasing function, comparing (2.2) with (1.6), we get
Corollary 4.2.2 Let A have an eigenvalue »(A) of the algebraic multiplicity
ν. In addition, under conditions (1.4) and (2.1), let the extreme right-hand
root z(φ, q) of equation (1.6) satis¬es the inequality
z(φ, q) ¤ d. (2.3)
Then in „¦(»(A), z(φ, q)) operator B has eigenvalues whose total algebraic
multiplicity is equal to ν.
Let θ1 , ..., θn1 (n1 ¤ n) be di¬erent eigenvalues of A, i.e.,
˜
d(A) := min{|θj ’ θk | : j = k; j, k = 1, .., n1 } > 0 (2.4)
and
n1
νk = n,
k=1
where νk is the multiplicity of the eigenvalue θk .
By virtue of Lemma 4.2.1, we arrive at the following result.
Lemma 4.2.3 Let condition (1.4) hold. In addition, for a positive number
˜
a ¤ d(A), let condition (2.2) is valid. Then all the eigenvalues of operator B
lie in the set
∪n1 „¦(θk , a)
k=1
and thus, md (A, B) ¤ a.
Moreover, Corollary 4.2.2 implies
Corollary 4.2.4 Under conditions (1.4) and (2.4), let the extreme right-
˜
hand root z(φ, q) of equation (1.6) satis¬es the inequality z(φ, q) ¤ d(A).
Then all the eigenvalues of operator B lie in the set
∪n1 „¦(θk , z(φ, q))
k=1

and thus md (A, B) ¤ z(φ, q).
52 4. Eigenvalues of Finite Matrices


4.3 Perturbations of Eigenvectors
and Eigenprojectors
Under condition (1.4), let A have an eigenvalue »(A) of the algebraic multi-
plicity ν and (2.1) hold. Let ‚„¦ be the boundary of „¦(»(A), d):

‚„¦ ≡ {z ∈ C : |z ’ »(A)| = d}.

Put
1
P (A) = ’ R» (A)d» (3.1)
2πi ‚„¦

and
1
P (B) = ’ R» (B)d». (3.2)
2πi ‚„¦

That is, both P (A) and P (B) are the projectors onto the eigenspaces of
A and B, respectively, corresponding to points of the spectra, which lie in
„¦(»(A), d).

Lemma 4.3.1 Let A satisfy condition (1.4) and have an eigenvalue »(A) of
the algebraic multiplicity ν, such that the conditions (2.1) and

qφ(1/d) < 1 (3.3)

hold. Then dim P (A) = dim P (B). Moreover,

qdφ2 (1/d)
P (A) ’ P (B) ¤ . (3.4)
1 ’ qφ(1/d)

Proof: Thanks to Lemma 4.2.1 dim P (A) = dim P (B). From (1.3) and
(1.4) it follows that

R» (B) ¤ R» (A) (1 ’ qφ(1/d))’1 ¤ φ(1/d)(1 ’ qφ(1/d))’1 (» ∈ ‚„¦)

and
1
P (A) ’ P (B) ¤ R» (A) ’ R» (B) |d»| ¤
2π ‚„¦

qφ2 (1/d)d
1
R» (B) qφ(1/d)|d»| ¤ ,
1 ’ qφ(1/d)
2π ‚„¦

as claimed. 2

We will say that an eigenvalue of a linear operator is a simple eigenvalue,
if its algebraic multiplicity is equal to one. The eigenvector corresponding to
a simple eigenvalue will be called a simple eigenvector.
4.4. Perturbations in Euclidean Norm 53


Lemma 4.3.2 Suppose A has a simple eigenvalue »(A), such that the rela-
tions (1.4), (2.1) and
q[dφ2 (1/d) + φ(1/d)] < 1 (3.5)
hold. Then for the eigenvector e of A corresponding to »(A) with e = 1,
there exists a simple eigenvector f of B with f = 1, such that
e ’ f ¤ 2δ(1 ’ δ)’1 ,
where
qdφ2 (1/d)
δ≡ .
1 ’ qφ(1/d)
Proof: Firstly, note that condition (3.5) implies the relations (3.3) and
δ < 1, and B has in „¦(»(A), d) a simple eigenvalue »(B) due to Lemma
4.2.1. Let P (B) and P (A) be de¬ned by (3.1) and (3.2). Due to Lemma
4.3.1,
P (A) ’ P (B) ¤ δ < 1.
Consequently, P (B)e = 0, since P (A)e = e. Thanks to the relation
BP (B)e = »(B)P (B)e,
P (B)e is an eigenvector of B. Let N = P (B)e . Then f ≡ N ’1 P (B)e is a
normed eigenvector of B. So
e ’ f = P (A)e ’ N ’1 P (B)e = e ’ N ’1 e + N ’1 (P (A) ’ P (B))e.
But
N ≥ P (A)e ’ (P (A) ’ P (B))e ≥ 1 ’ δ.
Hence N ’1 ¤ (1 ’ δ)’1 and
e ’ f ¤ (N ’1 ’ 1) e + N ’1 P (A) ’ P (B) ¤
(1 ’ δ)’1 ’ 1 + (1 ’ δ)’1 δ = 2δ(1 ’ δ)’1 ,
as claimed. 2



4.4 Perturbations of Matrices
in the Euclidean Norm
4.4.1 Perturbations of eigenvalues
We recall that the quantities . 2 , g(A) and γn,k are de¬ned in Sections 1.2
and 2.1. In addition, put
q2 := A ’ B 2 .
The norm for matrices is understood in the sense of the operator norm.
54 4. Localization of Eigenvalues of Finite Matrices


Theorem 4.4.1 Let A and B be n — n-matrices. Then

svA (B) ¤ z(q2 , A), (4.1)

where z(q2 , A) is the extreme right-hand (unique nonegative) root of the al-
gebraic equation
n’1
n
γn,j z n’j’1 g j (A).
z = q2 (4.2)
j=0

Proof: Theorem 2.1.1 gives us the inequality
n’1
g k (A)γn,k
¤ (» ∈ σ(A)).
R» (A) (4.3)
2
ρk+1 (A, »)
k=0

Rewrite (4.2) as
n’1
γn,j g j (A)
1= .
z j+1
j=0

Now the required result is due to Lemma 4.1.2 and (4.3). 2
Put
n’1
wn = γn,j .
j=0

Setting z = g(A)y in (4.2) and applying Lemma 1.6.1, we have the estimate
z(q2 , A) ¤ q2 wn , provided
q2 wn ≥ g(A) (4.4)
and
z(q2 , A) ¤ g 1’1/n (A)[q2 wn ]1/n ,
provided
q2 wn ¤ g(A). (4.5)
Now Theorem 4.4.1 ensures the following result.
Corollary 4.4.2 Let condition (4.4) hold. Then svA (B) ¤ qwn . If condition
(4.5) holds, then
svA (B) ¤ g 1’1/n (A)[qwn ]1/n .


4.4.2 Perturbations of multiplicities
and matching distance
For a positive scalar variable x, set
n’1
γn,j xj+1 g j (A).
Gn (x) ≡
j=0
4.4. Perturbations in the Euclidean Norm 55


Lemma 4.4.3 Let A have an eigenvalue »(A) of the algebraic multiplicity ν
and (2.1) hold. In addition, for a positive number a < d, let

q2 Gn (1/a) < 1. (4.6)

Then in „¦(»(A), a) operator B has eigenvalues whose total algebraic multi-
plicity is equal to ν.

This result follows from (4.3) and Lemma 4.2.1. 2
Proof:

Inequality (4.3) and Corollary 4.2.2 imply

Corollary 4.4.4 Let A have an eigenvalue »(A) of the algebraic multiplic-
ity ν. In addition, under condition (2.1), let the extreme right-hand root
z(q2 , A) of equation (4.2) satis¬es the inequality z(q2 , A) ¤ d. Then in
„¦(»(A), z(q2 , A)) operator B has eigenvalues whose total algebraic multiplic-
ity is equal to ν.

Let θ1 , ..., θn1 (n1 ¤ n) be the di¬erent eigenvalues of A, again. By virtue
of (4.3) and Lemma 4.2.3 we get the following result.
˜
Lemma 4.4.5 Under (2.4), for a positive number a < d(A), let condition
(4.6) is valid. Then all the eigenvalues of operator B lie in the set

∪n1 „¦(θk , a)
k=1

and thus md (A, B) ¤ a.

In addition, due to (4.3) and Corollary 4.2.4, we get

Corollary 4.4.6 Under (2.4), let the extreme right-hand root z(q2 , A) of
˜
equation (4.2) satis¬es the inequality z(q2 , A) ¤ d(A). Then all the eigenval-
ues of operator B lie in the set

∪n1 „¦(θk , z(q2 , A))
k=1

and thus md (A, B) ¤ z(q2 , A).

To estimate z(q2 , A) we can apply Lemma 1.6.1.


4.4.3 Perturbations of eigenvectors and eigenprojectors
in the Euclidean norm
Let A have an eigenvalue »(A) of the algebraic multiplicity ν and (2.1) hold.
De¬ne P (A) and P (B) as in Section 3.1. Recall that Gn and q2 are de¬ned
in the previous two subsections.
56 4. Eigenvalues of Finite Matrices


Lemma 4.4.7 Let A and B be linear operators in Cn . In addition, let A
have an eigenvalue »(A) of the algebraic multiplicity ν, such that the condi-
tions (2.1) and
q2 Gn (1/d) < 1
hold. Then dim P (A) = dim P (B). Moreover,

q2 Gn (1/d)d
P (A) ’ P (B) ¤ .
2
1 ’ q2 Gn (1/d)

This result is due to (4.3) and Lemma 4.3.1.

Lemma 4.4.8 Let A and B be linear operators in Cn . Suppose A has a
simple eigenvalue »(A), such that the relations (2.1) and

q2 [G2 (1/d)d + Gn (1/d)] < 1
n

hold. Then for the eigenvector e of A corresponding to »(A) with e = 1,
2
there exists the simple eigenvector f of B with f 2 = 1, such that

¤ 2δ2 (1 ’ δ2 )’1 ,
e’f 2

where
q2 dG2 (1/d)
n
δ2 ≡ .
1 ’ q2 Gn (1/d)

This result is due to (4.3) and Lemma 4.3.2.


4.5 Upper Bounds for Eigenvalues in Terms
of the Euclidean Norm
Let A be an n — n-matrix with entries ajk (j, k = 1, ..., n). Recall that D, V+
and V’ are the diagonal, upper nilpotent part and lower nilpotent part of A,
respectively, (see Section 3.1), and
n’1
wn = γn,j ,
j=0

where γn,j are de¬ned in Section 2.1. Assume that V+ = 0, V’ = 0 and
denote
µ2 (A) = wn min {N ’1 (V+ ) V’ 2 , N ’1 (V’ ) V+ 2 },
and
1/n 1/n
δ2 (A) = wn min {N 1’1/n (V+ ) V’
1/n 1’1/n
2} if µ2 (A) ¤ 1
2 ,N (V’ ) V+

and δ2 (A) = min { V’ 2 , V+ 2 } if µ2 (A) > 1.
4.6. Lower Bounds for the Spectral Radius 57


Theorem 4.5.1 All the eigenvalues of matrix A = (ajk )n j,k=1 lie in the union
of the discs
{» ∈ C : |» ’ akk | ¤ δ2 (A)}, k = 1, ..., n. (5.1)
Proof: Take A+ = D + V+ . Since A+ is triangular,
σ(A+ ) = σ(D) = {akk , k = 1, ..., n}. (5.2)
Since A ’ A+ = V’ , Corollary 4.4.2 implies
svA+ (A) ¤ N 1’1/n (V+ )[ V’ 2 wn ]1/n , (5.3)
provided that wn V’ 2 ¤ N (V+ ). Replace A+ by A’ = D + V’ . Repeating
the above procedure, we get
svA’ (A) ¤ N 1’1/n (V’ )[ V+ 2 wn ]1/n ,
provided that wn V+ 2 ¤ N (V’ ). In addition, σ(A’ ) = σ(D). These rela-
tions with (5.2) and (5.3) complete the proof in the case µ2 (A) ¤ 1. Te case
µ2 (A) > 1 is similarly considered 2


4.6 Lower Bounds for the Spectral Radius
Let A = (ajk ) be an n — n-matrix. Recall that rs (A) = sup |σ(A)| is the
(upper) spectral radius;
±(A) = sup Re σ(A) and rl (A) = inf |σ(A)|
is the inner (lower) spectral radius. Let V+ , V’ be the upper and lower
triangular parts of A (see Section 3.1). Denote by z(ν) the unique positive
root of the equation
n’1
n
g k (A)γn,k z n’k’1
z (A) = ν(A) (6.1)
k=0

where
ν(A) = min{ V’ 2 , V+ 2 }.
Theorem 4.6.1 Let A = (ajk )n j,k=1 be an n — n-matrix. Then for any k =
1, ..., n, there is an eigenvalue µ0 of A, such that
|µ0 ’ akk | ¤ z(ν). (6.2)
Moreover, the following inequalities are true:
rs (A) ≥ max{0, max |akk | ’ z(ν)}, (6.3)
k=1,...,n

rl (A) ¤ min |akk | + z(ν), (6.4)
k=1,...,n

and
±(A) ≥ max Re akk ’ z(ν). (6.5)
k=1,...,n
58 4. Eigenvalues of Finite Matrices


Proof: Take A+ = D + V+ . So relation (5.2) holds and A ’ A+ = V’ .
Theorem 4.3.1 gives us the inequality

svA (A+ ) ¤ z’ , (6.6)

where z’ is the extreme right-hand root of the equation
n’1
n
γn,j z n’j’1 g j (A).
z = V’ 2
j=0

Replace A+ by A’ = D + V’ . Repeating the same arguments, we get

svA (A’ ) ¤ z+ , (6.7)

where z+ is the extreme right-hand root of the equation
n’1
n
γn,j z n’j’1 g j (A).
z = V+ 2
j=0

Relations (6.6) and (6.7) imply (6.2). Furthermore, take µ in such a way
that |µ| = rs (D). Then due to (6.2), there is µ0 ∈ σ(A), such that |µ0 | ≥
rs (D) ’ z(ν). Hence, (6.3) follows. Similarly, inequality (6.4) can be proved.
Now take µ in such a way that Re µ = ±(D). Due to (6.2) for some
µ0 ∈ σ(A), |Re µ0 ’ ±(D)| ¤ z(ν). So, either Re µ0 ≥ ±(D), or Re µ0 ≥
±(D) ’ z(ν). Thus, inequality (6.5) is also proved. The proof is complete. 2
Again put
n’1
wn = γn,j .
j=0

Setting z = g(A)y in (6.1) and applying Lemma 1.6.1, we obtain the estimate
z(ν) ¤ δn (A), where

if ν(A)wn ≥ g(A),
ν(A)wn
δn (A) = .
g 1’1/n (A)[ν(A)wn ]1/n if ν(A)wn ¤ g(A)

Now Theorem 4.6.1 ensures the following result.
Corollary 4.6.2 For a matrix A = (ajk )n
j,k=1 , the inequalities

rs (A) ≥ max |akk | ’ δn (A), (6.8)
k=1,...,n

rl (A) ¤ min |akk | + δn (A),
k=1,...,n

±(A) ≥ max Re akk ’ δn (A) (6.9)
k=1,...,n

are valid.
4.7. Additional Bounds 59


4.7 Additional Bounds for Eigenvalues
In the present section instead of the Euclidean norm we use the norm . ∞ .
Besides, we derive additional bounds for eigenvalues.
Let A be an n — n-matrix with entries ajk (j, k = 1, ..., n), again. Denote
j’1 n
|ajk |, qlow = |ajk |.
qup = max max
j=2,...,n j=1,...,n’1
j+1
k=1

Recall that vk , wk , mup (A) and mlow (A) are de¬ned in Section 3.4. Without
˜˜
lossing the generality, assume that

min {qlow mup (A), qup mlow (A)} ¤ 1. (7.1)

Theorem 4.7.1 Under condition (1.1), all the eigenvalues of A lie in the
union of the discs

{» ∈ C : |» ’ akk | ¤ δ∞ (A)}, k = 1, ..., n,

where
n
δ∞ (A) := min{qlow mup (A), qup mlow (A)}.

The proof of this theorem is presented in the next section.
If A is a triangular matrix, then Theorem 4.7.1 gives the exact relation

σ(A) = {akk , k = 1, ..., n}.

Moreover, we have
Corollary 4.7.2 Under condition (1.1), the spectral radius rs (A) of A sat-
is¬es the inequality

rs (A) ¤ max |akk | + δ∞ (A).
k=1,...,n

Furthermore, consider the quantity

s(A) ≡ max |»i (A) ’ »j (A)|.
i,j

According to Theorem 4.7.1, for arbitrary »i (A), »j (A), there are akk , amm ,
such that

|»i (A) ’ akk | ¤ δ∞ (A), |»j (A) ’ amm | ¤ δ∞ (A).

Consequently,

|»i (A) ’ »j (A)| ¤ |»i (A) ’ akk | + |»j (A) ’ amm | + s(D)

¤ s(D) + 2δ∞ (A) (i, j ¤ n),
where s(D) = maxi,j |aii ’ ajj |. So we have
60 4. Eigenvalues of Finite Matrices


Corollary 4.7.3 Under condition (1.1), s(A) ¤ s(D) + 2δ∞ (A).
According to Theorem 4.7.1, Re »k (A) ¤ maxj Re ajj + δ∞ (A). We thus get
Corollary 4.7.4 Under (7.1), let maxj Re ajj + δ∞ (A) < 0. Then A is a
Hurwitz matrix.
These results supplement the well known theorems by Hirsh and Rochrbach
(Marcus and Minc, 1964, Sections III.1.3 and Section III.3.1).


4.8 Proof of Theorem 4.7.1
Recall that V± and D are de¬ned in Section 3.1.
Lemma 4.8.1 The following estimate is true:
n
vk
˜
’1
¤ρ
R» (D + V+ ) (D, ») [1 + ],

|akk ’ »|
k=2

where ρ(D, ») = mink=1,...n |akk ’ »|.
Clearly, R» (D + V+ ) = R» (D)(I + Vup R» (D))’1 . Due to Lemma
Proof:
2.10.1,
n
vk
˜
’1
¤
(I + V+ R» (D)) [1 + ],

|akk ’ »|
k=2

since V+ R» (D) is nilpotent and its entries are ajk (akk ’ »)’1 . Hence, the
required result follows. 2


Lemma 4.8.2 Each eigenvalue µ of the matrix A = (ajk ) satis¬es the in-
equality
n
vk
˜
’1
1 ¤ qlow ρ (D, µ) (1 + ).
|akk ’ µ|
k=2

Proof: Take B = V+ + D. We have
j’1
A’B |ajk | = qlow .
= V’ = max
∞ ∞
j=2,...,n
k=1

Lemma 4.1.1 and Lemma 4.8.1 imply
n
vk
˜
’1
1 ¤ qlow Rµ (D + V+ ) ¤ qup ρ (D, µ) (1 + )
|akk ’ »|
k=2

for any µ ∈ σ(A), as claimed. 2
4.8. Proof of Theorem 4.7.1 61


Lemma 4.8.3 All the eigenvalues of matrix A = (ajk )n
j,k=1 lie in the set


∪n „¦(akk , z(A)),
j=2

where

„¦(akk , z(A)) = {» ∈ C : |» ’ akk | ¤ z(A)} (k = 1, ..., n)

and z(A) is the extreme right-hand (unique positive and simple) root of the
algebraic equation
n
n
z = qlow (z + vk ).
˜ (8.1)
k=2

Proof: Since |akk ’ »| ≥ ρ(D, ») for all k = 1, ..., n, Lemma 4.8.2 implies
the inequality
n
’1
(1 + vk )ρ’1 (D, µ))
1 ¤ qlow δ (D, µ) ˜ (8.2)
k=2

for any eigenvalues µ of A. Dividing the algebraic equation (8.1) by z n we
can write down
n
’1
(1 + vk z ’1 ).
1 = qlow z ˜
k=2

Comparing this with (8.2) and taking into account that z(A) is the extreme
right root of (8.1) we obtain ρ(A, ») ¤ z(A), as claimed. 2
Proof of Theorem 4.7.1: By Lemma 1.6.1,

z(A) ¤ qlow mup (A) if qlow mup (A) ¤ 1.
n




Then due to Lemma 4.8.3 all the eigenvalues of A lie in the union of the discs

{» ∈ C : |» ’ akk | ¤ qlow mup (A) } , k = 1, ..., n.
n




Replace A by the adjoint matrix A— , and repeat our arguments. We can
assert that all the eigenvalues of A— lie in the union of the discs

{» ∈ C : |» ’ akk | ¤ qup mlow (A) } ; k = 1, ..., n,
n




provided that qup mlow (A) ¤ 1. Since σ(A) = σ(A— ), we get the required
result. 2
62 4. Eigenvalues of Finite Matrices


4.9 Notes
Recall that, for nonnegative matrices, Frobenius has derived the following
lower estimate:
n
rs (A) ≥ r(A) ≡ min
˜ ajk , (9.1)
j=1,...,n
k=1

cf. (Marcus and Minc, 1964, Chapter 3, Section 3.1). Relation (6.8) improves
estimate (9.1) in the case ajk ≥ 0 (j, k = 1, ..., n), provided that maxk akk ’
δn (A) > r(A). That is, (6.8) is sharper than (9.1) for matrices which are
˜
close to triangular ones, since δn (A) ’ 0, when V’ ’ 0 or V+ ’ 0.
Due to inequality (6.9), matrix A is unstable, when

max Re akk ’ z(ν) > 0.
k=1,...,n


The latter result supplements the Rorhbach theorem (Marcus and Minc, 1964,
Chapter 3, Section 3.3.3).
A lot of papers and books are devoted to bounds for m(A, B), cf. (Stewart
and Sun, 1990), (Bhatia, 1987), (Elsner, 1985), (Phillips, 1990 and 1991) and
references therein. One of the recent results belongs to R. Bhatia, L. Elsner
and G. Krause (1990). They have proved that

m(A, B) ¤ 22’1/n q 1/n ( A + B 2 )1’1/n . (9.2)
2

In the paper (Farid, 1992) that inequality was improved in the case when
both A and B are normal matrices with spectra on two intersecting lines.
Corollary 4.4.6 improves (9.2), if A is close to a triangular matrix.
The contents of Sections 4.2 and 4.3 are taken from (Gil™, 1997) while the
results of Sections 4.4 and 4.5 are adapted from (Gil™, 2001). The material
in Section 4.6 is taken from (Gil™, 1995).
About other perturbation results see, for instance, the books (Kato, 1966)
and (Baumgartel, 1985).


References
[1] Baumgartel, H. (1985). Analytic Perturbation Theory for Matrices and
Operators. Operator Theory, Advances and Appl., 52. Birkhauser Verlag,
Basel, Boston, Stuttgart

[2] Bhatia, R. (1987). Perturbation Bounds for Matrix Eigenvalues, Pitman
Res. Notes Math. 162, Longman Scienti¬c and Technical, Essex, U.K.

[3] Bhatia R., Elsner, L. and Krause, G. (1990). Bounds for variation of the
roots of a polynomial and the eigenvalues of a matrix. Linear Algebra
and Appl. 142, 195-209
4.9. Notes 63


[4] Elsner, L. (1985). On optimal bound for the spectral variation of two
matrices. Linear Algebra and Appl. 71, 77-80.
[5] Farid, F. 0. (1992). The spectral variation for two matrices with spectra
on two intersecting lines, Linear Algebra and Appl. 177: 251-273.
[6] Gil™, M.I. (1995). Norm Estimations for Operator-Valued Functions and
Applications. Marcel Dekker, Inc. New York.

[7] Gil™, M.I. (1997). A nonsingularity criterion for matrices, Linear Algebra
Appl. 253, 79-87.
[8] Gil™, M.I. (2001). Invertibility and positive invertibility of matrices, Lin-
ear Algebra and Appl., 327, 95-104
[9] Kato, T. (1966). Perturbation Theory for Linear Operators, Springer-
Verlag. New York.
[10] Marcus M. and Minc, H. (1964). A Survey of Matrix Theory and Matrix
Inequalities, Allyn and Bacon, Boston.

[11] Phillips, D. (1990). Improving spectral-variation bound with Chebyshev
polynomials, Linear Algebra Appl., 133, 165-173
[12] Phillips, D. (1991). Resolvent bounds and spectral variation, Linear Al-
gebra Appl., 149, 35-40
[13] Stewart, G. W. and Ji-guang Sun, (1990). Matrix Perturbation Theory,
Academic Press, New York.
5. Block Matrices and
π-Triangular Matrices



The present chapter is devoted to block matrices. In particular, we derive
the invertibility conditions, which supplement the generalized Hadamard cri-
terion and some other well-known results for block matrices.


5.1 Invertibility of Block Matrices
Let an n — n-matrix A = (ajk )n
j,k=1 be partitioned in the following manner:

« 
A11 A12 . . . A1m
¬ A21 . . . A2m ·
A22
A=¬ ·, (1.1)
. .
... .
Am1 Am2 . . . Amm

where m < n, Ajk are matrices. Again I = In is the unit operator in Cn and
n
|ajk |.
A = max

j=1,...,n
k=1

Let the diagonal blocks Akk be invertible. Denote
up
Ajk A’1
vk = max (k = 2, ..., m),

kk
j=1,2,...,k’1


and
Ajk A’1
low
(k = 1, ..., m ’ 1).
vk = max ∞
kk
j=k+1,...,m



M.I. Gil™: LNM 1830, pp. 65“74, 2003.
c Springer-Verlag Berlin Heidelberg 2003
66 5. Block Matrices


Theorem 5.1.1 Let the diagonal blocks Akk (k = 1, ..., m) be invertible. In
addition, with the notations
up low
Mup ≡ (1 + vk ), Mlow ≡ (1 + vk ),
2¤k¤m 1¤k¤m’1

let the condition
Mlow Mup < Mlow + Mup (1.2)
hold. Then matrix A de¬ned by (1.1) is invertible. Moreover,

maxk A’1 ∞ Mlow Mup
’1 kk
¤
A . (1.3)

Mlow + Mup ’ Mlow Mup

The proof of this theorem is divided into a series of lemmas, which are pre-
sented in Sections 5.2-5.5.
Theorem 5.1.1 is exact in the following sense. Let the matrix A in (1.1) be
upper block triangular and Akk be invertible. Then Mlow = 1 and condition
(1.2) takes the form Mup < 1 + Mup . Thus, due to Theorem 5.1.1, A is
invertible. We have the same result if the matrix in (1.1) is lower block
triangular.
Consider a block matrix with m = 2:
A11 A12
A= . (1.4)
A21 A22

Then
up
v2 = A12 A’1 v1 = A21 A’1
low
∞, ∞.
22 11

In addition,
up low
Mup = 1 + v2 and Mlow = 1 + v1 .
Assume that
up up
low low
(1 + v2 )(1 + v1 ) < 2 + v2 + v1 ,
or, equivalently, that

A12 A’1 A21 A’1 < 1. (1.5)
∞ ∞
22 11

Then due to Theorem 5.1.1, the matrix in (1.4) is invertible. Moreover,

maxk=1,2 A’1 ∞ Mlow Mup
’1 kk
¤
A .

Mlow + Mup ’ Mlow Mup

Now assume that m is even: m = 2m0 with a natural m0 , and Ajk are 2 — 2
matrices:
a2j’1,2k’1 a2j’1,2k
Ajk =
a2j’1,2k a2j,2k
5.2. π-Triangular Matrices 67


with j, k = 1, ..., m0 . Take into account that
’a2k’1,2k
a2k,2k
A’1 = d’1
kk k ’a2k,2k’1 a2k’1,2k’1
with
dk = a2k’1,2k’1 a2k,2k ’ a2k,2k’1 a2k’1,2k .
up low
Thus, the quantities vk , vk are simple to calculate. Now relation (1.2)
yields the invertibility, and (1.3) gives the estimate for the inverse matrix.
In Section 5.4 below, we show that the matrix in (1.4) is invertible pro-
vided
A12 A’1 A21 A’1 < 1 (1.6)
22 11

with an arbitrary matrix norm . in Cn .


π-Triangular Matrices
5.2
Let B(Cn ) be the set of all linear operators in Cn . In what follows

π = {Pk , k = 0, ..., m ¤ n}

is a chain of orthogonal projectors Pk in Cn , such that

0 = P0 ‚ P1 ‚ .... ‚ Pm = In .

The relation Pk’1 ‚ Pk means that

Pk’1 Cn ‚ Pk Cn (k = 1, ..., m).

Let operators A, D, V ∈ B(Cn ) satisfy the relations

APk = Pk APk (k = 1, ..., m), (2.1)

DPk = Pk D (k = 1, ..., m), (2.2)
V Pk = Pk’1 V Pk (k = 2, ..., m); V P1 = 0. (2.3)
Then A, D and V will be called a π-triangular operator, a π- diagonal one
and a π-nilpotent one, respectively
Since

V m = V m Pm = V m’1 Pm’1 V = V m’2 Pm’2 V Pm’1 V =

... = V P1 ...V Pm’2 V Pm’1 V,
we have
V m = 0. (2.4)
That is, every π-nilpotent operator is a nilpotent operator. Denote

∆Pk = Pk ’ Pk’1 ; Vk = V ∆Pk (k = 1, ..., m).
68 5. Block Matrices


Lemma 5.2.1 Let A be π-triangular. Then
A = D + V, (2.5)
where V is a π-nilpotent operator and D is a π-diagonal one.
Proof: Clearly,
m m m k m
A= ∆Pj A ∆Pk = ∆Pj A∆Pk = Pk A∆Pk .
j=1 k=1 j=1
k=1 k=1

Hence (2.5) is valid with
m
D= ∆Pk A∆Pk , (2.6)
k=1

and
m m
V= Pk’1 A∆Pk = Vk . (2.7)
k=2 k=2
2

De¬nition 5.2.2 Let A ∈ B(Cn ) be a π-triangular operator and suppose
(2.5) holds. Then the π-diagonal operator D and π-nilpotent operator V will
be called the π-diagonal part and π-nilpotent part of A, respectively.
Lemma 5.2.3 Let π = {Pk }m be a chain of orthogonal projectors in Cn . If
k=1
˜ is a π-nilpotent operator, and A is a π-triangular one, then both operators
V
˜ ˜
AV and V A are π-nilpotent ones.
Proof: By (2.1) and (2.3) we get
˜ ˜ ˜ ˜
V APk = V Pk APk = Pk’1 V Pk APk = Pk’1 V APk , k = 1, ..., m.
˜
That is, V A is indeed a π-nilpotent operator. Similarly we can prove that
˜
AV is a π-nilpotent operator. 2

Lemma 5.2.4 Let A ∈ B(Cn ) be a π- triangular operator and D be its
π-diagonal part. Then the spectrum of A coincides with the spectrum of D.
Proof: Due to (2.5)
R» (A) = (A ’ »I)’1 = (D + V ’ »I)’1 = R» (D)(I + V R» (D))’1 . (2.8)
According to Lemma 5.2.3, V R» (D) is π- nilpotent if » is not an eigenvalue
of D. Therefore,
m’1
’1
R» (D)(’V R» (D))k .
R» (A) = R» (D)(I + V R» (D)) =
k=0
5.3. Multiplicative Representation of Resolvents 69


This relation implies that » is a regular point of A if it is a regular point of
D.
Conversely, let » ∈ σ(A). Due to (2.5)

R» (D) = (D ’ »I)’1 = (A ’ V ’ »I)’1 =

R» (A)(I ’ V R» (A))’1 .
According to Lemma 5.2.3, V R» (A) is π- nilpotent. Therefore,
m’1
R» (A)(V R» (A))k .
R» (D) =
k=0

So » ∈ σ(D), provided let » ∈ σ(A). The lemma is proved. 2



5.3 Multiplicative Representation
of Resolvents of π-Triangular Operators
For X1 , X2 , ..., Xm ∈ B(Cn ) and j < m, again denote

Xk ≡ Xj Xj+1 ...Xm .
j¤k¤m

Lemma 5.3.1 Let π = {Pk }m be a chain of orthogonal projectors in Cn (m ¤
k=1
n), V be a π-nilpotent operator. Then

’1
(I ’ V ) = (I + V ∆Pk ). (3.1)
2¤k¤m

Proof: According to (2.4)
m’1
’1
V k.
(I ’ V ) = (3.2)
k=0

On the other hand,
’ m
(I + V ∆Pk ) = I + Vk + V k1 V k 2
2¤k¤m k=2 2¤k1 <k2 ¤m

+... + V2 V3 ...Vm .
Here, as above, Vk = V ∆Pk . However,

V k1 V k2 = V ∆Pk1 V ∆Pk2 =
2¤k1 <k2 ¤m 2¤k1 <k2 ¤m
70 5. Block Matrices


Pk1 ’1 V ∆Pk2 = V 2 ∆Pk2 = V 2 .
V
3¤k2 ¤m 3¤k2 ¤m

Similarly,
Vk1 Vk2 ...Vkj = V j
2¤k1 <k3 ...<kj ¤m

for j < m. Thus from (3.2) follows (3.1). This is the desired conclusion. 2.

Theorem 5.3.2 For any π- triangular operator A and a regular » ∈ C

’1
(I ’ V ∆Pk (D ’ »I)’1 ∆Pk ),
R» (A) = (D ’ »I)
2¤k¤m

where D and V are the π-diagonal and π-nilpotent parts of A, respectively.

Proof: Due to Lemma 5.2.3, V R» (D) is π-nilpotent. Now Lemma 5.3.1
gives

’1
(I ’ V R» (D)∆Pk ).
(I + V R» (D)) =
2¤k¤m

But R» (D)∆Pk = ∆Pk R» (D). This proves the result. 2



5.4 Invertibility with Respect to a Chain of
Projectors
Again, let
π = {Pk , k = 0, ..., m}
be a chain of orthogonal projectors Pk . Denote the chain of the complemen-
tary projectors by π :
˜

˜
Pk = In ’ Pm’k and π = {In ’ Pm’k , k = 0, ..., m}.
˜

In the present section, V is a π-nilpotent operator, D is a π-diagonal one,
and W is a π -nilpotent operator.
˜

Lemma 5.4.1 Any operator A ∈ B(Cn ) admits the representation

A = D + V + W. (4.1)

Proof: Clearly,
m m
A= ∆Pj A ∆Pk .
j=1 k=1
5.4. Invertibility with Respect to a Chain 71


Hence, (4.1) holds, where D and V are de¬ned by (2.6) and (2.7), and
m m m
˜ ˜
W= ∆Pj A∆Pk = Pk’1 A∆Pk
k=1 j=k+1 k=2

˜ ˜ ˜
with ∆Pk = Pk ’ Pk’1 . 2

Let . be an arbitrary norm in Cn .
Lemma 5.4.2 Let the π-diagonal matrix D be invertible. In addition, with
the notations
VA ≡ V D’1 , WA ≡ W D’1 ,
let the condition

θ := VA (I + VA )’1 (I + WA )’1 WA < 1 (4.2)

hold. Then the operator A de¬ned by (4.1) is invertible. Moreover,

A’1 ¤ (I + VA )’1 D’1 (I + WA )’1 (1 ’ θ)’1 . (4.3)

Proof: Due to Lemma 5.4.1,

A = D + V + W = (I + VA + WA )D = [(I + VA )(I + WA ) ’ VA WA ]D.

Clearly, VA and WA are nilpotent matrices and, consequently, the matrices,
I + VA and I + WA are invertible. Thus,

A = (I + VA )(I ’ BA )(I + WA )D, (4.4)

where
BA = (I + VA )’1 VA WA (I + WA )’1 .
Condition (4.2) yields

(I ’ BA )’1 ¤ (1 ’ θ)’1 .

Therefore, (4.2) provides the invertibility of A. Moreover, according to (4.4),
inequality (4.3) is valid. 2


Corollary 5.4.3 Under condition (1.6), the matrix in (1.4) is invertible.

<<

. 3
( 11)



>>