BIB-VERSION:: CS-TR-v2.0
ID:: CORNELLCS//TR93-1371
ENTRY:: 1993-10-14
ORGANIZATION:: Cornell University, Computer Science Department
LANGUAGE:: English
TITLE:: Do the Pseudospectra of a Matrix Determine its Behavior?
AUTHOR:: Greenbaum, Anne 
AUTHOR:: Trefethen, Lloyd N. 
DATE:: August 1993
PAGES:: 8
ABSTRACT::
Let $A$ and $B$ be square matrices. It is shown that the condition 
$(R) ||(zI-A)^{-1}|| = ||(zI -B)^{-1}||$ for all $z \in \complex$ is 
equivalent to the condition $(P) ||p(A)|| = ||p(B)||$ for all polynomials $p$ 
if $|| \cdot ||$ is the Frobenius norm, but not if $|| \cdot ||$ is the 2-norm.
END:: CORNELLCS//TR93-1371
BODY::
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<ibly small, in view
of the exponential factors that appear in the process of taking powers. It would
be interesting to know whether analogous results may hold for more general
functions p(A).
References
[1] J L. NI. van Dorssdaer, J. F. B. NI. Rraaijevanger, and NI. N. Spijker, Linear
stability analysis in the numerical soLution of initial value problems, Acta
Numerica 1993 (1993), 199--H237.
[21 R. ?V. Freund, G. H. Golub, and N. Ni. Naditigal, Iterative solution of linear
systems, Acta Nunwnca 1992 (1992), 57 100.
[3] A. Greenbaum and L. N. Trefethen, GMftES/CR and Arnoldi/Lanczos as
matrnx approximation problems, SIANI J. Sd. Comp., to appear.
[4] D. J. Higham and L. N. Trefethen, Stiffness of ODEs. BIT, to appear.
[5] R. A. Horn and C. R. Johnson, Topics in Matrix Analys, Cambridge 1'ni-
versity Press, Cambridge, 1991.
[6] T. Kato, Perturbation Theory for Linear Operators, Springer-Verlag, New
York, 1976.
[7] H.-O. Kreiss, Uber die StabilitJt?deftnition frr Differenze?qleichungen die
partielle Differentialyleichungen approximieren, BIT 2 (1962), 153 181.
[8] R. D. Richtmyer and N. ?V. Niorton, Difference Methods for Initial- VaLue
Problems, ?Tiley?Interscience, New York, 1967
[9] F. Riesz and B. Sz.-Nagy, Functional AnaLysis, Frederick Ungar, New York,
1955.
[10] L. N. Trefethen, Pseudospectra of matrices, iii D. F. Grifliths and G. A.
??%tson, eds., Numerical Analysis 1991. Lc?ngman, 1992.
[11] E. Wegert and L. N. Trefethen, From the Buffon needle problem to the
Kreiss matrix theorem, Amer. Niath. Nionthly, to appear.
8
