Do the Pseudospectra of a Matrix Determine its Behavior? Anne Greenbaum* Lloyd N. Trefethen** TR 93-1371 August 1993 Department of Computer Science Cornell University Ithaca, NY 14853-7501 * Supported by DOE Contract DEFG0288ER25053. ** Supported by NSF Grant DM59116110. Do tlie pseudospectra of a matrix determine its behavior? Anne Greenbaun?* Courant Institute of Niatheinatical Sciences 251 N?1ercer St. New York., NY 10012 greenbau4ciins.nyu.edu Lloyd N. Trefethent Departnient of Coniputer Science Cornell University Ithaca, NY 14853 LNTffia'cs. cornell.edu Abstract. Let A and B be square niatrices. It is shown that the condition (zI--HA)?1 I II for all c C is equivalent to the conditk?n p(A) IIp(B)?I ft?r all polynoniials p if I is the Frobenius norm, but not if I is the 2?norm. * Supported by DOE Contract DEFGo28?ER25o5.?. t Supported by NSF Grant DMS-9't16110 1. The problem Let A and B be complex square matrices, not necessarily of the same di- mension, and let I be a matrix norm. Consider the conditions I(zI--HA)?1II--HIG7I--HB)?1II VzcC and IIp(A)II IIp(B)It Vp, where p is a polynornial. Are these conditions equivalent? Condition (1?) assertsthat A arid B have the same resolvent norms through- out the complex plane. Equivalently, A and B have the same pse?dospectra, where the ?-pseudospectrum of A is defined fi?r each ? ? 0 bv [z E C : (zi --H A)--H? I > (?i] (1) with the convention I (zi --H A)--H1 cc if is an eigaivalue of A [10] Condition (P) asserts that A and B have the same bchavio?? if behavior is measured by norms of polynomials, or e?iivalently, since analytic functions of matrices reduce to polynomials, by norms of functions. This notion of behavior may seem restrictive, but it captures much of what one wants to know about a matrix in applications. Por example, the stability of an evolution process gov- erned by A is determined by the norms IIA? in the discrete case or 6tA1 in the continuous case [8]. Similarly, the convergence of matrix iterative algorithms for solving linear equations or finding eigenvalues, such as tile GNIRES and Arnoldi iterations [2], depends oil how fast the norms p*? (A) decrease as n iricreases, where p*? isthe polynomial that minimizes I p( A) I in a suitably normalized class of polynomials of degree n [3]. If is the 2-noim and A is nornial (i.e. A has a complete set of or- thogonal eigenvectors), then (zi --H A)--H1 dist(z, A(A))--H1 arid IIp(A)II S??z?A(A) Ip(z)I, where A(A) denotes the spectrum of A, arid thus (I?) and (P) reduce to scalar conditions that are easily seen to be equiwilent. If A isnot nor- mal, however, then (zi --H A)--H1 and IIp(A)I are not det??mined by A(A). Of course they are both determined by (zi --H A)--H1, thanks to the Cauchy integral p(A) = 2ti p(ZI --H A)--H1 p(z) dz, (2) 2 where I' is any contour enclosing A(A) [6]. If only the m?rrri (zi --H A)--H' is known, however, then (2) can be applied to derive upper bounds for IIp(A)I but they are not in general sharp. The best known and most refined example of such a bound is the Nreiss Niatrix Theorem, which can be derived from (2) by integration by parts conibined with a few other tricks [7,8,11]. 2. (P)?(R) In one direction our problem is straightforward. Theorem 1. (P) impli&? (1?). Proof If IIp(A)I = IIp(B)II for all polynou?als p, then I[p(A)II 0 if arid only if IIp(B)II = 0, arid this implies that A and B have the same minimal polynomial, rn(z). In particular A and B have the same eigcnvalues, and thus (zi--H A)--H1 = cc if an?[ only if I (zi--H B)--H' [I = cc On the other hand let z C C be a number distinct from these eigcrivalues. Then (zi --H A)--H1 q(A), where q(w) is any polynomial that interpolates (z--Hu?)?1 in the zeros of rn, courited with multiphcity (i.e., the derivatives of orders 0,1--H 1 are interpolated in the case of a zero of multipheity ?i) [5, Thur. 6.2.9]. Likewise, (zi --H B)--H' --H q(B) for the same polynon?al q. By (P), we now have Iq(A) q(B)[ , that is, I (zi --H A)--H' --H II (zi --H I?)--H' [I. I 3. (R) # (P) in the 2-norm Let be the 2-norm. Iii this case the pseudospectra can be characterized in various other w?ys besides (1), such as = fz c C : z C A(A + ) ft?r some with 1 I ? et (3) = tz ? C : a???(A) ? (4) where amin (A) denotes the smallest singular value of A. The first equahty is valid for any matrix norm induced by a vector norm [1]; the second applies to the 2-norm only. ?Ve thought at first that (R) certainly could not imply (P), since the norm of the resolvent surely could riot ??contain enough information" to determine 3 behavioral quantities exactly. Yet the information contents of (R) and (P) are better matched than they may at first appear. Por example, both pseudospec- tra and norms of polynomials take no notice of cigenvalue multiplicities, as is illustrated by the matrices 2 (Here and below, blank matrix entries are zero.) Both (R) and (P) are also satisfied if one takes B AT or B UA U* with LT unitary. Fufthennore, it is easily shown that (1?) implies (P) if A and B are of dimension ? 2. Nevertheless, the following counterexaniple shows that our first intuition was correct. Theorem 2. If is the 2-norm, then (1?) does not impky (P). Proof. Consider the Jordan blocks Ji --H 0 0 j2 --H--H with a E C. ?Ve have Y1 1 and j2? I?t so if a,> 1, then J2 > Jill. On the other hand if a ? $2, then (zi-- j2)?ill ? (zi--H ?1)--H1l V E C. (5) To show this we note first that for any Jordan bk?ck J. (zi J)--H1 depends only on Iz , i.e., the pseudospectra are disks aboift the ongin. (This can be proved by a diagonal similarity transformation.) Thus it is enough to establish (5) for real and positive. Rather than providing an algebraic proof we simply present Pigure 1, which illustrates strict inequality in (5) for a 1.1. The proof is completed by taking A=J1, Bz ?1 with 1 ? Ia ? $2. ?Ve then have IlBil --H a > IlAll 1 but I (zi --H A)?1 I (zi --H B)--H' I --H I (zi -- J1 )--Hi for all z C C. Thus these niatrices provide a counterexample to (1?) ? (P) with p(z) z'. 4 102 Izi (zI--H j)?iII 1 100 102 01 () 1 -2 0 10 10 102 Figure 1. Illustration of strict inequality in (5); the ordinate is taken as I --H j)--Hi1 --H 1 instead of 11(21 --H J)--H? because this makes the behavior in both limits I oc and Izi 0 clear. The upper curve correspondsto a matrix with smaller norm, but larger resolvent norm I (zi --H J )--H? for all norizero z C C. In the counterexample just given, the matrices A and B have different dimensions (3 and 5), l)ut this is inessential. The dim??isions could be made equal, for example, by padding A with zeros. 4. (R) ? (P) in the Frobenius norm Our third theorem shows that in tlie Frobenius norm. tiie pseudospectra do determine the behavior of a matrix. Theorem 3. if I is the Froheniiis norm, then (R) frnphes (P). Iri this case we have dim(A) dim(B). Proof The Probeniiis norni of (zi --H A)- given by II(zI --H A)?iII2 IzI?2 tr [(I --H z?iA)?*(J --H z?iA)?l )j where tr(.) denotes the trace. If Izi > p(A), where p(.) denotes the spectral 5 radius, then this expression can be expanded in a convergent Neumann series as (? r?kAk) --H 4)?1 112 = lzl?2 tr k 4*k) k--H--Ho = lz1?2 tr ?? For Izi > maxfp(?4), p(B)J, then, condition (R) implies that ?? can write ?kzk?C tr(A*kA:?k) = z?kzk? tr(B*kB:?k). f=o k=o ?--H--HO k--H--HO (6) Taking the limit as Izi cc imphes that the ( = 0 terms of (6) must be equal, tr(i?4) = t4iB), where 1j1 and 1B denote the identities of dimensions dim( A) and dim(B), respec- tively. This implies dim(A) dim(B), as claimed. Now subtract these ? = 0 term from both sides of (6), multiply by z, and take the limit as `I Oc again to obtain tr(A) + tr(A*) = tr(B) + tr(B*). Choosing two different values for /7, say 1 and --H1, we find tr(A) = tr(B), tr(A*) = tr(B*). Continuing in this w?y, suppose it has been shown that the traces involved in the terms with (/ ? rn. are all equal. To show that the traces involved in the = m terms are equal, first subtract the known equal terms from both sides of (6), then multiply by zrn and take the limit as I -?+ cc to obtain rn rn ?( ))k tr( A*%4rn--Hk) = ?( )k tr(B*kBrn?k). k=O k--H--Ho Choosing fl2 + 1 different values on the unit circle for z/z?, say, ??o, .. ?rn, gives a Vandermonde system of rn + 1 independent homogeneous equations for the fl2 + 1 quantities tr(A*k?trn?k) --H tr(B*kBm?k): 1 n0 . . . ?0rn 1 ? . . . ?i 1 ?m rn tr(Am) --H tr(Bm) 0 t4A*Arn--Hi) --H tr(B*Bm--Hi) 0 tr(A*rn) --H tr(B* ) 0 6 It follows that tr(A*%4e) = tr(B*kB?) for all k and , and this implies IIp(A)II --H IIp(B)II for all p since IIp(A)112 = c?c? tr(A*%4?), Ip(B)112 = ckc? tr(B*?BC), k C k if p(x) = Zk ck?k. I Unfortunately, in the Frobenius norm the pseudospectra, defined by (1), are not characterized by (3). Even for the simplest example, where A is the zero matrix of dimension A?, A?(A) is the dosed disk about the origin of radius V7y?, whereas the set defined in (3), = tz E C : E A() for some with IlEll ? eJ, is the disk of radius c. In general, for any A and e we have 5?F)(A) C ??(2)(A) ? ?(F)( 4), where the superscripts iiidicate Frobenius or 2-norm. The first inequality follows from IlEjIF > 11E112 for the perturbation matrix , and the second from II (zi 4)--H' IF > II (zi --H 4)--H' 112 5. Discussion The problem of relating information in the complex plane to the behavior of a matrix or linear operator A is an old one. Niany results are known, of which the most important connect the spectrum of A with the asymptotic behavior of A? and etA as n, t H 00, anci the nuinerical range of A with the initial behavior of A? and glA as n, t --H+ 0 [1]. Since the spectrum is determined by the &pseudospectra in the limit e H 0 and tlie numencal range by the (2-norm) &pseudospectra in the limit e 00, these two examples can both be regarded as special cases of pseudospectral information [4]. In effect this paper has considered the question of how much more can be gained if one knc?ws A?(A) for finite valiws of e in addition to the limits e 0 and e 00. A related collection of results is associated with von Neumann's theory of spectral sets, described for example in [9]. Since the 2-norm is more useful for most applications than the Frobenius norm, we regard the maiii result of this paper as negative: exact information about matrix behavior cannot be inferred from the norm of the resolvent (The- orem 2). It remains to be seen, however, whether the gap between these two kinds of information may be quantiflable. For example, the gap between the norms of powers I Ii and the bound provided by the I&reiss Niatrix Theorem is known to be linear in the dimension of the m?'?trix remark