˜ ˜

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.