# Gersgorin-type eigenvalue inclusion theorems and their sharpness.

Dedicated to Professor John Todd, on the occasion of his 90th birthday, May 16, 2001.Abstract. Here, we investigate the relationships between G(A), the union of Gersgorin disks, K(A), the union of Brauer ovals of Cassini, and B(A), the union of Brualdi lemniscate sets, for eigenvalue inclusions of an n x n complex matrix A. If [sigma](A) denotes the spectrum of A, we show here that

[sigma](A) [subset or equal to] B(A) [subset or equal to] K(A) [subset or equal to] G(A)

is valid for any weakly irreducible n x n complex matrix A with n [greater than or equal to] 2. Further, it is evident that B(A) can contain the spectra of related n x n matrices. We show here that the spectra of these related matrices can fill out B(A). Finally, if [G.sup.R](A) denotes the minimal Gersgorin set for A, we show that

[G.sup.R](A) [subset or equal to] B(A):

Key words. Gersgorin disks, Brauer ovals of Cassini, Brualdi lemniscate sets, minimal Gersgorin sets.

AMS subject classification. 15A18.

1. Gersgorin Disks and Ovals of Cassini. For any n [greater than or equal to] 2, let A be any n x n complex matrix (written A = [[a.sub.i,j]] [member of] [C.sup.nxn]), and let [sigma](A) denote its spectrum (i.e., [sigma](A) := {[lambda] [member of] C : det[A - [lambda][I.sub.n]] = 0}). A familiar result of Gersgorin [3] is that if

(1.2) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

denotes the i-th Gersgorin disk for A, then the union of these n Gersgorin disks contains all eigenvalues of A:

(1.2) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

A less familiar result of Brauer [1] is that if

(1.3) [K.sub.i,j](A) := {z [member of] C : [absolute value of (z - [a.sub.i,i])] x [absolute value of (z - [a.sub.j,j])] [less than or equal to] [r.sub.i](A) x [r.sub.j] (A)} (1 [less than or equal to] i; j [less than or equal to] n, i [not equal to] j)

denotes the (i, j)-th Brauer oval of Cassini for A, then similarly

(1.4) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where K(A) now depends on [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] sets [K.sub.i,j](A).

It is interesting that both G(A) and K(A) are defined solely from the same 2n numbers,

(1.5) [{[a.sub.i,i]}.sup.n.sub.i=1] and [{[r.sub.i](A)}.sup.n.sub.i=1],

determined from the matrix A, and it is natural to ask which of the sets G(A) and K(A) is smaller, as the smaller set would give a "tighter" estimate for the spectrum [sigma](A). That K(A) [subset of equal to] G(A) holds in all cases is a result, not well known, which was stated by Brauer [1], and, as the idea of the proof is simple and will be used later in this paper, its proof is given here.

Theorem A. For any A = [[a.sub.i,j]] [member of] [C.sup.nxn] with n [greater than or equal to] 2,

(1.6) K(A) [subset or equal to] G(A).

Proof. Fix any i and j, with 1 [less than or equal to] i, j [less than or equal to] n and i [not equal to] j, and let z be any point of [K.sub.i,j](A), so that from (1.3),

(1.7) [absolute value of (z - [a.sub.i,i])] x [absolute value of (z - [a.sub.j,j])] [less than or equal to] [r.sub.i](A) x [r.sub.j](A) (1 [less than or equal to] i, j [less than or equal to] n, i [not equal to] j).

If [r.sub.i](A) x [r.sub.j](A) = 0, then z = [a.sub.i,i] or z = [a.sub.j,j]. But, as [a.sub.i,i] [member of] [G.sub.i](A) and [a.sub.j,j] [member of] [G.sub.j](A) from (1.1), then z [member of] [G.sub.i](A) [union] [G.sub.j](B). If [r.sub.i](A) x [r.sub.j](A) > 0, we have from (1.7) that

(1.8) ([absolute value of (z - [a.sub.i,i])] / [r.sub.i](A)) x ([absolute value of (z - [a.sub.j,j])] / [r.sub.j](A)) [less than or equal to] 1.

As the factors on the left of (1.8) cannot both exceed unity, then at least one of these factors is at most unity, i.e., z [member of] [G.sub.i](A) or z [member of] [G.sub.j](z). Hence, in either case, it follows that z [member of] [G.sub.i](A)[G.sub.j](A), so that

(1.9) [K.sub.i,j] (A) [subset or equal to] [G.sub.i](A) [union] [G.sub.j] (A) (1 [less than or equal to] i, j [less than or equal to] n, i [not equal to] j).

With (1.9), it follows from (1.2) and (1.4) that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

the desired result of (1.6)

We remark that the case of equality in the inclusion of (1.9) is covered (cf. [7]) in

(1.10) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

As mentioned above, G(A) and K(A) depend solely on the same 2n numbers of (1.5) which are derived from the matrix A, but there is a continuum of matrices (for n [greater than or equal to] 2) which give rise to the same numbers in (1.5). More precisely, following the notations of [6], let

[OMEGA] (A) := {B = [[b.sub.i,j]] [member of] [C.sup.nxn] : [b.sub.i,i] = [a.sub.i,i] and [r.sub.i](B) = [r.sub.i](A), 1 [less than or equal to] i [less than or equal to] n, (1.11)

and let

(1.12) [??](A) := {B = [[b.sub.i,j]] [member of] [C.sup.nxn] : [b.sub.i,i] = [a.sub.i,i] and [r.sub.i](B) [less than or equal to] [r.sub.i](A), 1 [less than or equal to] i [less than or equal to] n,

so that [OMEGA](A) [subset or equal to] [??](A). We note, from the final inequality in (1.3), that the first inclusion of (1.4) is then valid for all matrices in (A) or [??](A), i.e., with (1.6) and with the definitions of

(1.13) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

it follows that

(1.14) [sigma] ([OMEGA](A)) [subset or equal to] [sigma] ([??](A)) [subset or equal to] K(A) [subset or equal to] G(A).

Recently in Varga and Krautstengl [7], the following was established. (For notation, if T is a set in the complex plane C, then [bar.T] denotes its closure, T' := C\T its complement, and [partial derivative]T := [bar.T] [intersection] \([bar.T]') its boundary.)

Theorem B. For any A = [[a.sub.i,j]] [member of] [C.sup.nxn] with n [greater than or equal to] 2,

(1.15) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and, in general, for any n [greater than or equal to] 2,

(1.16) [sigma]([??](A)) = K(A

In other words, for n [greater than or equal to] 3, each point of the Brauer ovals of Cassini K(A) is an eigenvalue of some matrix in (A) or [??](A), and, given only the data of (1.5), K(A) does a perfect job of estimating the spectra of all matrices in (A) or [??](A).

2. Lemniscate and Brualdi Lemniscate Sets. Given an n x n complex matrix A = [[a.sub.i,j]] [member of] [C.sup.nxn], let [{[i.sub.j]}.sup.m.sub.j=1] be any m distinct positive integers from N := {1, 2, ..., n}, so that n [greater than or equal to] m. Then, the lemniscate (1) of order m, derived from [{[i.sub.j]}.sup.m.sub.j=1] and the 2n numbers {[a.sub.i,i]}.sup.n.sub.i=1]} and [{[r.sub.i](A)}.sup.n.sub.i=1], is the compact set in C defined by

(2.1) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and their union, denoted by

(2.2) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

is over all [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] such choices of [{[i.sub.j]}.sup.m.sub.j=1] from N. As special cases, the Gersgorin disks [G.sub.i](A) of (1.1) are lemniscates of order 1, while the Brauer ovals of Cassini [K.sub.i,j] (A) of (1.3) are lemniscates of order 2, so that with (1.2) and (1.4)), we have

(2.3) [L.sub.(1)](A) = G(A) and [L.sub.(2)](A) = K(A).

When one considers the proof of Gersgorin's result (1.2) or the proof of Brauer's result (1.4), the difference is that the former focuses on one row of the matrix A, while the latter focuses on two distinct rows of the matrix A. But, from the result of (1.6) of Theorem A, this would seem to suggest that "using more rows in A gives better eigenvalue inclusion results for the spectrum of A". Alas, it turns out that L(m)(A), as defined in (2.2), fails, in general for m > 2, to give a set in the complex plane which contains the spectrum of each A in [C.sup.nxn], n [greater than or equal to] m, as the following example (attributed to Morris Newman in Marcus and Minc [4]) shows. It suffices to consider the 4 x 4 matrix

(2.4) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [{[b.sub.i,i] = 1}.sup.4.sub.i=1] and where [r.sub.1](B) = [r.sub.2](B) = 1; [r.sub.3](B) = r4(B) = 0. On choosing m = 3 in (2.1), then, for any choice of three distinct integers {[i.sub.1], [i.sub.2], [i.sub.3]} from {1, 2,3, 4}, the product [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is zero, and the associated lemniscate in (2.1), for B of (2.4), always reduces to the set of points z for which [[absolute value of z - 1].sup.3] = 0, so that z = 1 is its sole point. Hence, with (2.2), L(3)(B) = f1g, which does not contain [sigma](B). (The same argument also gives [L.sub.(4)](B) = {1}, and this can be extended to all n > 2.)

This brings us to the penetrating work of Brualdi [2], which shows how the union of higher-order lemniscates for a general matrix A (these lemniscates not necessarily being of the same order) can give compact sets in the complex plane C which contain _(A), thereby circumventing the counterexample of (2.4). Brualdi's construction depends on a very clever use of circuits, from the directed graph of A, which we now describe. Given A = [[a.sub.i,j]] 2 [C.sup.nxn], n [greater than or equal to] 2, then [GAMMA](A) is the directed graph on n distinct vertices [{[v.sub.i]}.sup.n.sub.i=1] for the matrix A, consisting of a (directed) arc [??], from vertex [v.sub.i] to vertex [v.sub.j], only if i [not equal to] j and if [a.sub.i,j] [not equal to] 0. (This omits the usual use of loops when [a.sub.i,i] [not equal to] 0.) A path [pi] from vertex [v.sub.i] to vertex [v.sub.j] is a sequence i = [i.sub.0], [i.sub.1], ..., [i.sub.k] = j of vertices for which [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are abutting arcs, and the length of the path [pi] is said to be k. Then, the directed graph [GAMMA](A) is said to be strongly connected if, for each ordered pair (i, j) of vertices [v.sub.i] and [v.sub.j], there is a path from [v.sub.i] to [v.sub.j] . (As is well-known, A is irreducible if and only if [GAMMA](A) is strongly connected.) A circuit [gamma] of [GAMMA](A) is a path corresponding to the sequence [i.sub.1], [i.sub.2], ..., [i.sub.p], [i.sub.p+1] = [i.sub.1] (where p [greater than or equal to] 2), where [i.sub.1], [i.sub.2], ..., [i.sub.p] are all distinct, and where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are arcs of [GAMMA](A). (The length of this circuit [gamma] is p.) Then, C(A) denotes the set of all circuits [gamma] in [GAMMA] (A). Following Brualdi [2], a matrix A is said to be weakly irreducible if each vertex [v.sub.i] of [GAMMA] (A) belongs to some circuit [gamma] in C(A). (Obviously, A irreducible implies A is weakly irreducible.)

Next, for n [greater than or equal to] 2, we define the set

[P.sub.n] := {all cycles, of length at least two, from the integers (1, 2, ..., n)},

where it can be verified that the cardinality of [P.sub.n] is given by card ([P.sub.n]) =

(2.5) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Then, a circuit [gamma] of [GAMMA](A), given by the sequence [i.sub.1], [i.sub.2], ..., [i.sub.p] [i.sub.p+1] with [i.sub.p+1] = [i.sub.1], can be associated with an element in [P.sub.n], i.e.,

(2.6) [gamma] = ([i.sub.1]; [i.sub.2], ..., [i.sub.p]) [member of] [P.sub.n], where [member of] [less than or equal to] p [less than or equal to] n and where [i.sub.p+1] = [i.sub.1]. (2.6)

With the above notations and definitions, a result of Brualdi [2, Cor. 2.4], is

Theorem C. For any A = [[a.sub.i,j]] [member of] [C.sup.nxn], n [greater than or equal to] 2, for which A is weakly irreducible, then

(2.7) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We have introduced in (2.7) the quantity B(A), which we call the Brualdi lemniscate set for A, as it is the union of lemniscates (see (2.1)), of possibly different orders, derived from the matrix A.

For the matrix B = [[b.sub.i,j]] of (2.4), its directed graph is

[ILLUSTRATION OMITTED]

and, as C(B) consists solely of the circuit (1; 2), then B is not weakly irreducible, as there are no circuits through vertices [v.sub.3] or [v.sub.4]. However, on considering the near-by matrix [B.sub.[epsilon]], defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

its directed graph is

Then, C([B.sub.[epsilon]]) = (1, 2)[union](3, 4), and [B.sub.[epsilon]] is thus weakly irreducible for any [epsilon] > 0. Applying Theorem C to [B.sub.[epsilon]] gives a valid eigenvalue inclusion for [B.sub.[epsilon]]:

[sigma] ([B.sub.[epsilon]]) [subset or equal to] {z [member of] C : [[absolute value of z - 1].sup.2] [less than or equal to] 1} [union] {z [member of] C : [[absolute value of z - 1].sup.2] [less than or equal to] [[epsilon].sup.2]}.

[ILLUSTRATION OMITTED]

We note that the eigenvalue inclusion of Brualdi's Theorem C, applied to a weakly irreducible matrix A = [[a.sub.i,j]] [member of] [C.sup.nxn] with n [greater than or equal to] 2, now depends on all the quantities of

(2.8) [{[a.sub.i,i]}.sup.n.sub.i=1], [{[r.sub.i](A)}.sup.n.sub.i=1], and C(A)

As (2.8) requires more information from the matrix A, in order to form the Brualdi lemniscate set B(A), then is required by the Brauer ovals of Cassini K(A) or the Gersgorin disks G(A), one might expect that B(A) is a set, which is no larger, in the complex plane, than K(A) or G(A). This will be shown to be true in Theorem 1 of the next section. In addition, one can ask, in the spirit of Theorem B, if the union of the spectra of all matrices, which match the data of (2.8), fills out the Brualdi lemniscate set B(A) of (2.7). This will be precisely answered in Theorem [member of] of Section 4.

3. Comparison of Brauer's Ovals of Cassini and Brualdi's Lemniscate Sets. Our new result here is very much in the spirit of the proof of Theorem A. (See also [6].)

Theorem 1. For any A = [[a.sub.i,j]] [member of] [C.sup.nxn], n [greater than or equal to] 2, which is weakly irreducible, then, with the definitions of (1.4) and (2.7),

(3.1) B(A) [subset or equal to] K(A).

Remark. This establishes that the Brualdi lemniscate set for a matrix A is always no larger than the union of the Brauer ovals of Cassini for this matrix.

Proof. Consider any circuit [gamma] in C(A). If this circuit has length two, i.e., [gamma] = ([i.sub.1], [i.sub.2]), where [i.sub.3] = [i.sub.1], it follows from (2.7) that

(3.2) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which, from (1.3), is exactly [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], i.e.,

(3.3) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Next, assume that [gamma] has length p > 2, i.e., [gamma] = ([i.sub.1], [i.sub.2], ..., [i.sub.p]), where [i.sub.p+1] = [i.sub.1]. Since A is weakly irreducible, each vertex of [GAMMA](A) has a circuit passing through it, so that [r.sub.l](A) > 0 for each l in N. From (2.7), we define

(3.4) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let z be any point of B(A). On squaring the inequality in (3.4), we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

As these [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (A)'s are all positive, we can equivalently express the above inequality as

(3.5) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

As the factors on the left of (3.5) cannot all exceed unity, then at least one of the factors is at most unity. Hence, there is an l with 1 [less than or equal to] l [less than or equal to] p such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(where if l = p, then [i.sub.l+1] = [i.sub.1]). But from the definition in (1.3), we see that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and, as a consequence, it follows that

(3.6) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Thus, from (2.7) and (3.6),

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

the desired result of (3.1).

We next show that there are many cases where equality holds in (3.1). Consider any matrix A = [[a.sub.i,j]] [member of] [C.sup.nxn], with n > 2, for which every non-diagonal entry [a.sub.i,j] of A is nonzero. The matrix A is then clearly irreducible, and hence, weakly irreducible. Moreover, every partition, of length [greater than or equal to] 2, of [P.sub.n] of (2.5) can be associated with a circuit [gamma] of C(A), so that the total number of these circuits is, from (2.5),

(3.7) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

In this case, as each Brauer oval of Cassini [K.sub.i,j](A), i [not equal to] j, corresponds to a circuit (of length 2) in B(A), it follows from (2.7) that K(A) _ B(A), but as the reverse inclusion holds in (3.1), then

(3.8) B(A) = K(A). (3.8)

In other words, the Brualdi lemniscate set B(A) need not, in general, be a proper subset of the Brauer ovals of Cassini K(A). We remark that for a 10 x 10 complex matrix A, all of whose off-diagonal entries are nonzero, there are, from (3.7), 1,112,073 distinct circuits in C(A). But because of (3.8), only [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] = 45 of these circuits, corresponding to the Brauer ovals of Cassini, are needed to determine B(A).

4. The Sharpness of Brualdi Lemniscate Sets. Given A = [[a.sub.i,j]] [member of] [C.sup.nxn], with n [greater than or equal to] 2 for which A is weakly irreducible, we have from (2.7) of Theorem C that

(4.1) [sigma](A) [subset or equal tro] B(A),

where the associated Brualdi lemniscate set B(A) is determined, in (2.7), from the quantities

[{[a.sub.i,i]}.sup.n.sub.i=1], [{[r.sub.i](A)}.sup.n.sub.i=1], and C(A). (4.2)

It is again evident that any matrix B = [[b.sub.i,j]] [member of] [C.sup.nxn], having the identical quantities of (4.2), has its eigenvalues also in B(A), i.e., with notations similar to (1.11) and (1.12), if

(4.3) [[OMEGA].sub.B](A) := {B = [[b.sub.i,j]] [member of] [C.sup.nxn] : [b.sub.i,i] = [a.sub.i,i], [r.sub.i](B) = [r.sub.i](A), 1 [less than or equal to] i [less than or equal to] n, and C(B) = C(A)},

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and if

(4.4) [[??].sub.B](A) := {B = [[b.sub.i,j]] [member of] [C.sup.nxn] : [b.sub.i,i] = [a.sub.i,i], 0 < [r.sub.i](B) [less than or equal to] [r.sub.i](A), 1 [less than or equal to] i [less than or equal to] n, and C(B) = C(A)},

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], it follows, in analogy with (1.14), that

[sigma]([[OMEGA].sub.B](A)) [subset or equal to] [sigma]([[OMEGA].sub.B](A)) [subset or equal to] B(A). (4.5)

(We note, since A is weakly irreducible, that [r.sub.i](A) > 0 for all 1 [less than or equal to] i [less than or equal to] n.)

It is natural to ask if equality can hold throughout in (4.5). The answer, in general, is no, as the following simple example shows. Consider the matrix

(4.6) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

so that

[r.sub.1](D) = [r.sub.2](D) = 1, and [r.sub.3](D) = 1/2.

The directed graph [GAMMA](D) is then

so that D is irreducible, and the circuit set of D is

C(D) = (1, 2) [union] (1, 2, 3).

Now, any matrix E in B(D) can be expressed, from (4.3), as

(4.7) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[ILLUSTRATION OMITTED]

where s satisfies 0 < s < 1 and where [{[[theta].sub.i]}.sup.4.sub.(i=1) are any real numbers. (Note that letting s = 0 or s = 1 in (4.7) does not preserve the circuit sets of C(D).) With [[gamma].sub.1] := (1, 2) and [[gamma].sub.2] := (1, 2, 3), we see that

(4.8) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where the set [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (D) consists of two disjoint components. These sets are shown in Figure 1.

[FIGURE 1 OMITTED]

It can be seen, from (4.8) and from Figure 1, that z = 0 is a boundary point of the compact sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (D) and B(D) := [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII](D) [union] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (D). Suppose that we can find an s with 0 < s < 1 and real values of [{[[theta].sub.1]}.sup.4.sub.i=1] for which an associated matrix E of (4.7) has eigenvalue 0. This implies that det E = 0, which, by direct calculations with (4.7), gives

(4.9) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

But as 0 < s < 1, the right side of (4.9) is in modulus at most

(1 - s) + 1/2 s = 2 - s/2 < 1,

so that det E [not equal to] 0 for any E in B(D), i.e., 0 [not member of] [sigma](B(D)). A similar argument shows (cf. (4.4)) that 0 [not member of] [sigma]([[OMEGA].sub.B](D)). But as 0 [member of] B(D), we have

(4.10) [sigma]([[OMEGA].sub.B](D)) [subset or equal to] [sigma]([[??].sub.B](D)) [??] B(A).

But, in order to achieve equality in (4.10), suppose that we allow s to be zero, noting from (4.8) that the parameter s plays no role in B(D) = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then, on setting s = 0 in (4.7), the matrix E of (4.7) becomes

(4.11) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and on choosing [[theta].sub.1] = 0 and [[theta].sub.2] = [pi], then z = 0 is an eigenvalue of [??], where [??] is the limit of matrices E in (4.7) when s [down arrow] 0. We note that the directed graph of [GAMMA]([??]) is

[ILLUSTRATION OMITTED]

so that C([??]) [not equal to] C(D), but [??] remains an element of (A) of (1.11).

This example suggests that we consider the closures of the sets [[OMEGA].sub.B](A) and [[??].sub.B] (A) of (4.3) and (4.4), where A = [[a.sub.i,j]] [member of] [C.sup.nxn], n [greater than or equal to] 2, is weakly irreducible:

(4.12) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and

(4.13) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

This brings us to the new result of

Theorem 2. For any A = [[a.sub.i,j]] [member of] [C.sup.nxn]; n [greater than or equal to] 2, which is weakly irreducible, then

[partial derivative]B(A) [subset or equal to] ([[bar.[OMEGA].sub.B]](A)) [subset or equal to] [sigma] ([[??].sub.B](A)) = B(A), (4.14)

i.e., each boundary point of B(A) is an eigenvalue of some matrix in [[bar.[OMEGA]].sub.B], and each point of B(A) is an eigenvalue of some matrix in [[??].sub.B](A).

Remark. This establishes the sharpness of the Brualdi set B(A) for the matrix A, as the final equality in (4.14) gives that the spectra of matrices in [[??].sub.B] (A) are dense in B(A).

Proof. Since [sigma]([[OMEGA].sub.B](A)) [subset or equal to] [sigma] ([[??].sub.B] (A)) from (4.5), it follows that their closures of (4.12) and (4.13) necessarily satisfy [sigma]([[bar.[OMEGA]].sub.B] (A)) [subset or equal to] [sigma]([[??].sub.B](A), giving the middle inclusion of (4.14). It suffices to establish the first inclusion and the final equality in (4.14).

Consider any circuit [gamma] in C(A). From our discussion in Section 2, we can express [gamma] as an element of [P.sub.n] of (2.5), i.e.,

(4.15) [gamma] = ([i.sub.1], [i.sub.2], ..., [i.sub.p]) where [i.sub.p+1] := [i.sub.1]; and where [member of] [less than or equal to] p [less than or equal to] n.

Without loss of generality, we can assume, after a suitable permutation of the rows and columns of A, that

(4.16) [gamma] = (1, 2, ..., p),

noting that this permutation leaves unchanged the collection of diagonal entries, row sums, and circuits of A. This permutated matrix, also called A, then has the partitioned form

(4.17) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where the matrices [A.sub.1,2], [A.sub.2,1], and [A.sub.2,2] are not present in (4.17) if p = n. Our aim below is to construct a special matrix B(t) = [[b.sub.i,j] (t)] [member of] [C.sup.nxn], whose entries depend continuously on the parameter t in [0, 1], such that

(4.18) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

To this end, write

(4.19) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

i.e., the rows p + 1 [less than or equal to] l [less than or equal to] n of B(t) are exactly those of A, and are independent of t. We note from (4.16) that

(4.20) [a.sub.1,2] * [a.sub.2,3] ... [a.sub.p-1,p] * [a.sub.p,1] [not equal to] 0,

and the rows of B(t) are then defined, for all t [member of] [0; 1], by

(4.21) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

It is evident that the entries of B(t) are all continuous in the variable t of [0; 1]. Moreover, B(t) and A have the same diagonal entries and the same row sums for all 0 [less than or equal to] t [less than or equal to] 1, and, as [a.sub.i,j] [not equal to] 0 implies [b.sub.i,j] (t) [not equal to] 0 for all 0 < t [less than or equal to] 1, then B(t) and A have the same circuits in their directed graphs for all 0 < t [less than or equal to] 1. As A is weakly irreducible by hypothesis, it follows that B(t) is weakly irreducible for all 0 < t [less than or equal to] 1. Also, from (4.3), B(t) [member of] B(A) for all 0 < t [less than or equal to] 1, and from (4.12), B(0) [member of] B(A). Hence, from (4.5),

(4.22) [sigma](B(t)) [subset or equal to] B(A) for all 0 < t [less than or equal to] 1.

But as B(A) is a closed set from (2.7), and as the eigenvalues of B(t) are continuous functions of t, for 0 [less than or equal to] t [less than or equal to] 1, we further have, for the limiting case t = 0, that

(4.23) [sigma](B(0)) [subset or equal to] B(A), (4.23)

where, from the definitions in (4.21),

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

With

(4.24) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We note from (4.21) that the nondiagonal entries in the first p rows of B(t) are defined only in terms of their moduli, which allows us to fix the arguments of certain nondiagonal nonzero entries of [B.sub.1,1](0) through the factors [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] where the [{[[theta].sub.j]}.sup.p.sub.j=1] are all real. (These factors appear in [B.sub.1,1](0) of (4.24).) The partitioned form of B(0) gives us that

(4.25) [sigma](B(0)) = [sigma]([B.sub.1,1](0)) [union] [sigma]([A.sub.2,2]),

and, from the special cyclic-like form of [B.sub.1,1](0) in (4.24), it is easily seen that each eigenvalue [value] of [B.sub.1,1](0) satisfies

(4.26) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for any real choices of {[[theta].sub.j]}.sup.p.sub.j=1] in (4.24). But (4.26), when coupled with the definition in (3.4), immediately gives us that [lambda] [member of] [partial derivative][B.sub.[gamma]](A), and, as all different choices of the real numbers [{[[theta].sub.j]}.sup.p.sub.j=1], in [B.sub.1,1](0) of (4.24), give eigenvalues of [B.sub.1,1](0) which cover the entire boundary of [B.sub.[gamma]](A), we have

(4.27) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

This can be used as follows. Let z be any boundary point of B(A) of (2.7). As B(A) is the union of a finite number of closed sets [B.sub.[gamma]](A), this implies that there is a circuit [gamma] of C(A) with z [member of] [partial derivative] [B.sub.[gamma]] (A), where [B.sub.[gamma]](A) is defined in (3.4). As the result of (4.27) is valid for any [gamma] of C(A), then each boundary point z of B(A) is an eigenvalue of some matrix in [[bar.[OMEGA]].sub.B](A) of (4.12), i.e.,

(4.28) [partial derivative]B(A) [subset or equal to] [sigma]([[bar.[OMEGA]].sub.B](A));

which is the desired first inclusion of (4.14).

To investigate how the eigenvalues of [[??].sub.B](A) of (4.13) fill out B(A), we make a small change in the definition of the matrix B(t) of (4.18) and (4.21). Let [{[[tau].sub.i]}.sup.p.sub.i=1] be any positive numbers such that

(4.29) 0 < [[tau].sub.i] [less than or equal to] [r.sub.i](A) (1 [less than or equal to] i [less than or equal to] p),

and let [??](t) = [[??].sub.i,j] (t)] [member of] [C.sup.nxn] have the same partitioned form as B(t) of (4.19), but with (4.21) replaced by

(4.30) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Then, [??](t) andA have the same diagonal entries, the row sums of [??](t) now satisfy [r.sub.j] ([??](t)) = [[tau].sub.j] for all 1 [less than or equal to] j [less than or equal to] p, all 0 [less than or equal to] t [less than or equal to] 1, and [??](t) and A have the same circuits for all 0 < t [less than or equal to] 1. From (4.4), [??](t) [member of] ^B(A) for all 0 < t [less than or equal to] 1, and from (4.13), [??](0) [member of] [[??].sub.B](A). In analogy with (4.23), we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

with

(4.31) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where

(4.32) [sigma]([??](0)) = [sigma]([[??].sub.1,1](0)) [union] [sigma]([A.sub.2,2]).

It similarly follows that any eigenvalue [lambda] of [[??].sub.1,1](0) in (4.31) now satisfies

(4.33) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for any choice of the real numbers [{[[theta].sub.j]}.sup.p.sub.j=1] in [[??].sub.1,1](0) of (4.31). Using the fact that [{[[tau].sub.j]}.sup.p.sub.j=1] are any numbers satisfying (4.29) and that [{[[theta].sub.j]}.sup.p.sub.j=1] are any real numbers, it follows from (3.4) and closure considerations that all the eigenvalues of [[??].sub.1,1](0) fill out [B.sub.[gamma]](A), i.e.,

(4.34) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

As this holds for any [gamma] [member of] C(A), where [??](0) [member of] [[??].sub.B](A), then

(4.35) [sigma]([[??].sub.B](A)) = B(A);,

the desired final result of (4.14).

5. A Comparison of Minimal Gersgorin Sets and Brualdi Lemniscate Sets. Given A = [[a.sub.i,j]] [member of] [C.sup.nxn] and x = [[x.sub.1], [x.sub.2], ..., [x.sub.n]].sup.T] > 0 in IRn, then with X := diag [[x.sub.1], [x.sub.2],..., [x.sub.n]], we have that [X.sup.-1]AX = [[a.sub.i,j][x.sub.j]/[x.sub.i]], where, since A and [X.sup.-1]AX are similar matrices, [sigma](A) = [sigma]([X.sup.-1]AX). On setting

(5.1) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

then Gersgorin Theorem, applied to [X.sup.-1]AX, gives

(5.2) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

As this eigenvalue inclusion holds for each x = [[[x.sub.1], [x.sub.2], ..., [x.sub.n]].sup.T] > 0 in [R.sup.n], we have

(5.3) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and [G.sup.R](A) is called (cf. [5]) the minimal Gersgorin set for A, relative to the collection of all weighted row sums [{[r.sup.x.sub.i] (A)}.sup.n.sub.i=1]. As [G.sup.x](A) is, for each x > 0, the union of n closed disks in the complex plane C, then [G.sup.x](A) is compact, as is [G.sup.R](A).

Another natural question is how the Brualdi lemniscate set B(A) of (2.7), a compact set in C, compares with the minimal Gersgorin set [G.sup.R](A) of (5.3), for every A = [[a.sub.i,j]] [member of] [C.sup.nxn]. The first apparent difference is that the Brualdi lemniscate set B(A) requires A to be weakly irreducible, whereas the minimal Gersgorin set [G.sup.R](A) does not make this restriction. But, if we assume that A = [[a.sub.i,j]] [member of] [C.sup.nxn] is weakly reducible, we can compare the associated sets in the complex plane. Given A = [[a.sub.i,j]] [member of] [C.sup.nxn], n [greater than or equal to] 2, we consider the following set of matrices, associated with A:

(5.4) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Lemma 3. For any A = [[a.sub.i,j]] [member of] [C.sup.nxn], n [greater than or equal to] 2, which is weakly irreducible, then (cf. (4.13))

(5.5) [DELTA](A) [subset or equal to] [[??].sub.B](A).

Proof. We first note that as A is weakly irreducible, then [r.sub.i](A) > 0 for all i [member of] N. Consider any matrix B = [b.sub.i,j] in [DELTA](A), so that from (5.4),

(5.6) [r.sub.i](B) [less than or equal to] [r.sub.i](A) for all i [member of] N.

Set [S.sub.i](A) := {j [member of] N : j [not equal to] i and [absolute value of [a.sub.i,j]] > 0}, for each i [member of] N. Then, [S.sub.i](A) [not equal to] 0 for any i [member of] N, since A is weakly irreducible. If there is a j in [S.sub.i](A) for which [b.sub.i,j] = 0, we note that

(5.7) [r.sub.i](B) < [r.sub.i](A).

Then, for a fixed [epsilon] > 0, replace this (i, j)-th entry of B by any number having modulus [epsilon], and do the same for every k in [S.sub.i](A) for which [b.sub.i,k] = 0, leaving the remaining entries in this i-th row, of B, unchanged. On carrying out this procedure for all rows of the matrix B, a matrix B([epsilon]), in [C.sup.nxn], is created, whose entries are continuous in the parameter [epsilon], and for which the circuit set C(B([epsilon])) of B([epsilon]) is identical with the circuit set C(A) of A, for each [epsilon] > 0. In addition, because of the strict inequality in (5.7) whenever [b.sub.i,j] = 0 with j [member of] [S.sub.i](A), it follows, for all [epsilon] > 0 sufficiently small, that

(5.8) [r.sub.i](B([epsilon])) [less than or equal to] [r.sub.i](A) for all i [member of] N.

Hence from (4.4), B([epsilon]) [member of] [[??].sub.B](A) for all [epsilon] > 0, sufficiently small. As such, we see from the definition in (4.13) that B(0) = B [member of] [[bar.[??]].sub.B]B(A), and as this holds for any B [member of] [DELTA](A), the inclusion of (5.5) is valid.

This brings us to the following new result which is both surprising and simple.

Theorem 4. For any A = [[a.sub.i,j]] [member of] [C.sup.nxn], n [greater than or equal to] 2, which is weakly irreducible, then

(5.9) [G.sup.R](A) [subset or equal to] B(A).

Remark. The word "minimal" in the minimal Gersgorin set [G.sup.R](A) seems to be appropriate!

Proof. It is known from [5] that [G.sup.R](A) of (5.3) satisfies

(5.10) [G.sup.R](A) = [sigma]([DELTA](A)),

and as [DELTA](A) [subset or equal to] [[bar.[??]].sub.B](A) from (5.5) of Lemma 3, then [sigma]([DELTA](A)) [subset or equal to] [sigma]([[bar.[??]].sub.B](A)). But as [sigma]([[bar.[??]].sub.B](A) = B(A) from (4.14) of Theorem 2, then these inclusions give that

[G.sup.R](A) [subset or equal to] B(A),

the desired result of (5.9). []

6. An Example. To illustrate the above results, consider the matrix

(6.1) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Then, F is irreducible, with C(F) = (1, 2) [union] (1, 2, 3, 4), with row sums [r.sub.i](F) = 1 for all 1 [less than or equal to] i [less than or equal to] 4. In this case, we have from (2.7) that B(F) consists of the union of the two closed sets

(6.2) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

These sets are shown in Figure 2, where [B.sub.[gamma]2] (F) has the shape of a four-leaf clover. Next, any matrix h in [[??].sub.B](F) can be expressed from (4.4) as

(6.3) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[FIGURE 2 OMITTED]

where 0 < [[tau].sub.i] [less than or equal to] 1 and 0 [less than or equal to] [[theta].sub.i] [less than or equal to] 2[pi] for all 1 [less than or equal to] i [less than or equal to] 5 and 0 < s < 1. To show how the eigenvalues of H fill out B(F), we take random numbers [{[[tau].sub.i]}.sup.5.sub.i=1], random numbers [{[[theta].sub.i]}.sup.5.sub.i=1] from [0, 2[pi]), and a random number s from (0, 1), and the eigenvalues of all these matrices, are plotted in Figure 3. Figure 3 indeed shows that these eigenvalues of F tend to fill out B(F).

[FIGURE 3 OMITTED]

It is of interest to note the following near paradox arising from Theorem 2. As an example, F of (6.1) is irreducible, and it is a known result of Brualdi [3, Cor. 2.11] that a boundary point z of B(F) can be an eigenvalue of F only if z is a boundary point of each of the lemniscates [B.sub.[gamma]1] (F) and [B.sub.[gamma]2] (F) of (6.2). But from Figure 2, it is apparent that z = 0 is the only point for which [partial derivative][B.sub.[gamma]1] (F) and [partial derivative][B.sub.[gamma]2] (F) have a common point. Yet, (4.14) of Theorem 2 gives the nearly contradictory result that, for each point of [partial derivative]B(F), there is an arbitrarily close eigenvalue of some matrix in [[OMEGA].sub.B](F). The difference, of course, lies in the fact that Cor. 2.11 of [2] applies to the fixed matrix F, while the common data of (4.2) apply to all matrices in [[OMEGA].sub.B](F).

Next, we consider the minimal Gersgorin set, [G.sup.R](F), for the matrix F of (6.1). The boundary of this set, [partial derivative][G.sup.R](F), can be verified to be

(6.4) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and [partial derivative][G.sup.R](F) is shown in Figure 4. Note that [partial derivative][G.sup.R](F) consists of three separate components.

[FIGURE 4 OMITTED]

Next, we see from (5.4) that any matrix J in [DELTA](F) is of the form

(6.5) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where 0 [less than or equal to] [[tau].sub.i] [less than or equal to] 1 and 0 [less than or equal s to] [[theta].sub.i] [less than or equal to] 2[pi], for all 1 {less than or equal to] i [less than or equal to] 5. We similarly consider the eigenvalues of j of (6.5), where we take random choices of [{[s.sub.i]}.sup.5.sub.i=1] in [0, 1], and random choices of [{[[theta].sub.i]}.sup.5.sub.i=1] in [0, 2[pi]] in (6.5). These eigenvalues are plotted in Figure 5, which show again how they fill out [G.sup.R](F). In Figure 6, we show both B(F) and [G.sup.R](F), and we directly see that

(6.6) [G.sup.R](F) [??] B(F).

That (6.6) holds can be seen from the fact that each matrix J of (6.5) is necessarily a matrix H of (6.4), but not conversely.

[FIGURE 5 OMITTED]

7. A Final Equality. The result, of (5.9) of Theorem 4, shows that the minimal Gersgorin set [G.sup.R](A) is always a subset of the Brualdi lemniscate set. Adding to this from the inclusion of (3.1) and (1.6), we then have

(7.1) [G.sup.R](A) [subset or equal to] B(A) [subset or equal to] K(A) [subset or equal to] G(A),

for any A = [[a.sub.i,j]] [member of] [C.sup.nxn], n [greater than or equal to] 2, which is weakly irreducible. But, the last three sets in (7.1) have no dependence on weighted row sums, while the first set certainly does from its definition in (5.3). To see the effect that weighted sums can have, consider any x = [[x.sub.1], [x.sub.2], ..., [x.sub.n]] > 0, and with [r.sup.x.sub.i] (A) of (5.1), we define (cf. (1.3)), in analogy with (5.2) and (5.3),

(7.2) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and (cf. (1.4))

(7.3) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[FIGURE 6 OMITTED]

Similarly, for any circuit [gamma] of [GAMMA](A), we similarly define (cf. (3.4) and (2.7))

(7.4) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and

(7.5) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

As we see from (1.1) and (5.2), [r.sup.x.sub.i] (A) = [r.sub.i]([X.sup.-1]AX). Hence, the last three inclusions of (7.1), applied to the matrix [X.sup.-1]AX, become

(7.6) [B.sup.x](A) [subset or equal to] [K.sup.x](A) [subset or equal to] [G.sup.x](A),

and as (7.6) holds for any x > 0, then

(7.7) [B.sup.R](A) [subset or equal to] [K.sup.R](A) [subset or equal to] [G.sup.R](A).

On the other hand, we have from (5.9) and (7.4) that

[G.sup.R]([X.sup.-1]AX) [subset or equal to] B([X.sup.-1]AX) = [B.sup.x](A), for any x > 0.

But as is easily verified, [G.sup.R]([X.sup.-1]AX) = [G.sup.R](A) for any x > 0, so that

[G.sup.R](A) [subset or equal to] [B.sup.x](A) for any x > 0.

As this inclusion holds for all x > 0, then with (7.5),

(7.8) [G.sup.R](A) (7.8) [B.sup.R](A).

Thus, on combining (7.7) and (7.8), we immediately have the result of

Theorem 5. For any A = [[a.sub.i,j]] [member of] [C.sup.nxn], n [greater than or equal to] 2, which is weakly irreducible, then

(7.9) [G.sup.R](A) = [K.sup.R](A) = [B.sup.R](A).

Acknowledgement: The author wishes to thank his colleague, Professor Victor Lomonosov, for a spirited discussion leading to Theorem 5, and the referee for his comments.

REFERENCES

[1] A. BRAUER, Limits for the characteristic roots of a matrix II, Duke Math. J. 14 (1947), pp. 21-26.

[2] R. BRUALDI, Matrices, eigenvalues and directed graphs, Linear Multilinear Algebra 11 (1982), 143-165.

[3] S. GERSCHGORIN, Uber die Abgrenzung der Eigenwerteeiner Matrix, Isv. Akad. Nauk USSR Ser. Mat., 7 (1931), pp. 749-754.

[4] M. MARCUS AND H. MINC, A Survey of Matrix Theory and Matrix Inequalities, Allyn and Bacon, Boston, 1964.

[5] R. S. VARGA, Minimal Gerschgorin sets, Pacific J. Math., 15 (1965), pp. 719-729.

[6] R. S. VARGA, Gerschgorin disks, Brauer ovals of Cassini (a vindication), and Brualdi sets, Information (to appear).

[7] R. S. VARGA AND A. KRAUTSTENGL, On Gersgorin-type problems and ovals of Cassini, Electron. Trans. Numer. Anal., 8 (1999), pp. 15-20.

[8] J. L. WALSH, Interpolation and Approximation by Rational Functions in the Complex Domain, American Mathematical Society Colloquium Publication Volume XX, American Mathematical Society, 1965.

* Received April 2, 2001. Accepted for publication April 26, 2001. Recommended by L. Reichel.

(1) The classical definition of a lemniscate (cf. Walsh [8, p. 54]) is the curve, corresponding to the case of equality in (2.1). The above definition of a lemniscate then is the union of this curve and its interior.

RICHARD S. VARGA ([dagger])

([dagger]) Institute for Computational Mathematics, Department of Mathematics and Computer Science, Kent State University, Kent, Ohio 44242 (U.S.A.), Research supported under NSF Grant DMS-9707359. varga@msc.kent.edu

Printer friendly Cite/link Email Feedback | |

Author: | Varga, Richard S. |
---|---|

Publication: | Electronic Transactions on Numerical Analysis |

Date: | Jan 1, 2001 |

Words: | 8132 |

Previous Article: | Numerical experiments with algebraic multilevel preconditioners. |

Next Article: | Some nonstandard finite element estimates with applications to 3D Poisson and Signorini problems. |