Bauer-Fike and the conditioning of eigenvalues

Intuition Beginner

Eigenvalues are the special stretch factors of a matrix, and a fair question is how much they move when the matrix is nudged. If you measure a matrix from real data, every entry carries a little error, and you would like to know whether the eigenvalues you compute are trustworthy or whether a tiny change in the matrix could throw them off badly.

For some matrices the eigenvalues are rock solid: a small change in the matrix produces an equally small change in every eigenvalue. These are the well-behaved matrices, the ones whose special directions sit at right angles to each other, like the axes of a tilted but undistorted grid. Symmetric matrices are the headline example, and for them an error of a certain size moves each eigenvalue by no more than that same size.

Other matrices are touchy. Their special directions lean hard against one another, almost pointing the same way, and when directions nearly coincide the matrix is close to one that has a genuine defect. For such a matrix a microscopic change in the entries can move an eigenvalue by a large amount. The single number that measures this touchiness is how skewed the eigenvector directions are, and the Bauer-Fike theorem turns that skewness into a guaranteed bound on how far the eigenvalues can wander.

Visual Beginner

The picture contrasts two matrices under the same small perturbation. For the well-behaved matrix the eigenvalues barely twitch; for the touchy one they smear out into a wide blot. The difference is entirely in how the eigenvector directions sit relative to each other.

Two facts are visible. When the eigenvector arrows are perpendicular the wiggle circles are as small as the perturbation itself. When the arrows nearly line up the wiggle circles balloon, and their radius is the perturbation size multiplied by a skewness factor that grows without bound as the directions merge.

Worked example Beginner

Take the matrix

$$A=\left(\begin{array}{cc}1& 1000\\ 0& 2\end{array}\right).$$

Its eigenvalues are $1$ and $2$, read straight off the diagonal because the matrix is triangular. The eigenvector for $1$ is $(1,0)$, and the eigenvector for $2$ turns out to be $(1000,1)$ rescaled, which points almost flat along the horizontal. So the two eigenvector directions are nearly parallel, a warning sign of touchiness.

Step 1. Perturb the matrix in its bottom-left corner, which started at $0$:

$$A+E=\left(\begin{array}{cc}1& 1000\\ 0.001& 2\end{array}\right).$$

The change has size $0.001$, very small.

Step 2. Find the new eigenvalues. They solve $(1-t)(2-t)-(1000)(0.001)=0$, that is $(1-t)(2-t)-1=0$, which expands to $t^2-3t+1=0$.

Step 3. Solve: $t=(3\pm \sqrt{9-4})/2=(3\pm \sqrt{5})/2$, so the eigenvalues are about $2.618$ and $0.382$.

Step 4. Compare. The eigenvalues moved from $1$ and $2$ to about $0.382$ and $2.618$ — each shifted by roughly $0.6$. A change of size $0.001$ in the matrix moved the eigenvalues by $0.6$, about six hundred times as much.

What this tells us: the huge off-diagonal entry $1000$ makes the eigenvector directions nearly parallel, and that near-parallelism amplifies a tiny perturbation into a large eigenvalue shift. A symmetric matrix, whose eigenvectors are perpendicular, would never let this happen.

Check your understanding Beginner

Formal definition Intermediate+

Let $A\in M_n(\mathbb{C})$ be diagonalisable, $A=V\Lambda V^{-1}$, where $\Lambda =\mathrm{diag}({\lambda }_1,\dots ,{\lambda }_n)$ collects the eigenvalues and the columns of $V$ are right eigenvectors, $AV=V\Lambda$, in the sense of 01.01.08. Let $\Vert \cdot {\Vert }_p$ denote a vector $p$-norm and the matrix norm it induces, and write ${\kappa }_p(V)=\Vert V{\Vert }_p\Vert V^{-1}{\Vert }_p$ for the condition number of the eigenvector matrix, the same quantity defined as the conditioning of a linear solve in 43.01.02. The spectrum is $\sigma (A)=\{{\lambda }_1,\dots ,{\lambda }_n\}$.

Definition (eigenvalue conditioning). A matrix $A$ is said to have well-conditioned eigenvalues when small perturbations of $A$ produce comparably small movements of $\sigma (A)$, and ill-conditioned eigenvalues otherwise. The Bauer-Fike theorem below makes "comparably small" precise through the factor ${\kappa }_p(V)$, and the per-eigenvalue refinement uses the left and right eigenvectors of a single eigenvalue.

Definition (left and right eigenvectors; condition number of a simple eigenvalue). Let $\lambda$ be a simple eigenvalue of $A$ (algebraic multiplicity one). A right eigenvector is a nonzero $x$ with $Ax=\lambda x$; a left eigenvector is a nonzero $y$ with $y^{\ast }A=\lambda y^{\ast }$, equivalently $A^{\ast }y=\bar{\lambda }y$. For a simple eigenvalue $y^{\ast }x\ne 0$, and the condition number of the eigenvalue is

$$\kappa (\lambda )=\frac{\Vert x{\Vert }_2\Vert y{\Vert }_2}{|y^{\ast }x|},s(\lambda )=\frac{1}{\kappa (\lambda )}=\frac{|y^{\ast }x|}{\Vert x{\Vert }_2\Vert y{\Vert }_2},$$

with $x,y$ normalised to unit length giving $\kappa (\lambda )=1/|y^{\ast }x|=1/\cos \theta$, where $\theta =\angle (x,y)$ is the acute angle between the left and right eigenvectors. The reciprocal $s(\lambda )$ is the separation or eigenvalue sensitivity.

Definition ($ϵ$-pseudospectrum). For $ϵ>0$, the $ϵ$-pseudospectrum of $A$ in the norm $\Vert \cdot {\Vert }_2$ is

$${\sigma }_{ϵ}(A)=\{z\in \mathbb{C}:z\in \sigma (A+E)\text{ for some }E\text{ with }\Vert E{\Vert }_2\le ϵ\}=\{z\in \mathbb{C}:\Vert (zI-A{)}^{-1}{\Vert }_2\ge {ϵ}^{-1}\},$$

with the convention $\Vert (zI-A{)}^{-1}{\Vert }_2=\infty$ for $z\in \sigma (A)$. The two descriptions coincide (proved in the Advanced results). The pseudospectrum is the qualitative picture of eigenvalue sensitivity: for a normal matrix it is the union of closed $ϵ$-discs about the eigenvalues, while for a non-normal matrix it can bulge far beyond them.

Notation: $V^{-1}$ is the inverse of the eigenvector matrix; $y^{\ast }$ is the conjugate transpose of $y$; $\angle (x,y)$ is the acute angle between the lines spanned by $x$ and $y$; $\sigma (A)$ is the spectrum and ${\sigma }_{ϵ}(A)$ the pseudospectrum; the resolvent is $(zI-A{)}^{-1}$ defined for $z\notin \sigma (A)$. A matrix is normal when $A^{\ast }A=A{A}^{\ast }$, which is equivalent to having a unitary eigenvector matrix and hence ${\kappa }_2(V)=1$.

Counterexamples to common slips

• Bauer-Fike bounds the distance from every perturbed eigenvalue to some original eigenvalue; it does not pair them up. A perturbation can pull two eigenvalues toward a common point or split a tight pair, so the bound is a one-sided exclusion statement, not a matching.
• The factor is $\kappa (V)$, the conditioning of the eigenvector matrix, not $\kappa (A)$. A matrix can have $\kappa (A)$ enormous yet perfectly conditioned eigenvalues (any normal matrix with a wide spectrum), and a matrix can have $\kappa (A)=1$ in some scaling yet ill-conditioned eigenvalues — the two condition numbers measure different problems.
• The per-eigenvalue formula $1/|y^{\ast }x|$ requires a simple eigenvalue. At a defective eigenvalue the right and left eigenvectors become orthogonal, $y^{\ast }x\to 0$, the condition number blows up, and the perturbation expansion ceases to be first order: the eigenvalue moves like a fractional power ${ϵ}^{1/m}$ of the perturbation for a Jordan block of size $m$.

Key theorem with proof Intermediate+

Theorem (Bauer-Fike; Bauer-Fike 1960 ^{[source pending]}; Trefethen-Bau Lecture 34 ^{[source pending]}). Let $A\in M_n(\mathbb{C})$ be diagonalisable, $A=V\Lambda V^{-1}$, and let $\mu$ be any eigenvalue of the perturbed matrix $A+E$. Then there is an eigenvalue ${\lambda }_i$ of $A$ with

$$|\mu -{\lambda }_i|\le {\kappa }_p(V)\Vert E{\Vert }_p,$$

where ${\kappa }_p(V)=\Vert V{\Vert }_p\Vert V^{-1}{\Vert }_p$ and $\Vert \cdot {\Vert }_p$ is any induced matrix norm. In particular every eigenvalue of $A+E$ lies in the union of the closed discs of radius ${\kappa }_p(V)\Vert E{\Vert }_p$ centred at the eigenvalues of $A$.

Proof. If $\mu \in \sigma (A)$ the bound holds with $|\mu -{\lambda }_i|=0$, so assume $\mu \notin \sigma (A)$; then $\Lambda -\mu I$ is invertible. Let $v\ne 0$ satisfy $(A+E)v=\mu v$, that is $(A-\mu I)v=-Ev$. Substitute $A=V\Lambda V^{-1}$ and apply $V^{-1}$ on the left:

$$(\Lambda -\mu I)V^{-1}v=-V^{-1}Ev=-V^{-1}EV(V^{-1}v).$$

Write $w=V^{-1}v\ne 0$. Since $\Lambda -\mu I$ is invertible,

$$w=-(\Lambda -\mu I{)}^{-1}{V}^{-1}EVw.$$

Take norms and use submultiplicativity:

$$\Vert w{\Vert }_p\le \Vert (\Lambda -\mu I{)}^{-1}{\Vert }_p\Vert V^{-1}{\Vert }_p\Vert E{\Vert }_p\Vert V{\Vert }_p\Vert w{\Vert }_p.$$

Divide by $\Vert w{\Vert }_p>0$:

$$1\le \Vert (\Lambda -\mu I{)}^{-1}{\Vert }_p{\kappa }_p(V)\Vert E{\Vert }_p.$$

Because $\Lambda -\mu I$ is diagonal, its induced $p$-norm is the largest entry modulus of its inverse, $\Vert (\Lambda -\mu I{)}^{-1}{\Vert }_p={\max }_i|{\lambda }_i-\mu {|}^{-1}=({\min }_i|{\lambda }_i-\mu |{)}^{-1}$. Substituting,

$$1\le \frac{{\kappa }_p(V)\Vert E{\Vert }_p}{{\min }_i|{\lambda }_i-\mu |},\text{hence}\underset{i}{\min }|{\lambda }_i-\mu |\le {\kappa }_p(V)\Vert E{\Vert }_p,$$

which is the claim with ${\lambda }_i$ the minimising eigenvalue. $\square$

Bridge. The Bauer-Fike bound builds toward the per-eigenvalue condition number $1/|y^{\ast }x|$ and the pseudospectral picture of the Advanced results, where the global factor $\kappa (V)$ is refined into one sensitivity number for each eigenvalue, and it appears again in 43.06.03 as the reason the QR algorithm can compute the eigenvalues of a normal matrix to full accuracy while a non-normal matrix limits the attainable accuracy. The foundational reason the factor is $\kappa (V)$ and not $\kappa (A)$ is that the diagonalising change of basis $V$ is exactly the lens through which the perturbation $E$ is viewed: the conjugated perturbation $V^{-1}EV$ carries the norm inflation $\kappa (V)$, and this is exactly the conditioning of the eigenvector basis rather than of the linear solve. The normal case generalises the Hermitian Weyl bound of 01.01.14: when $A$ is normal, $V$ is unitary, ${\kappa }_2(V)=1$, and Bauer-Fike collapses to $|\mu -{\lambda }_i|\le \Vert E{\Vert }_2$, the central insight being that perpendicularity of eigenvectors is the precise structural condition for perfect eigenvalue conditioning. Putting these together, eigenvalue sensitivity is governed not by the size of the matrix or its inverse but by how far its eigenvectors are from orthogonal, and the bridge is the recognition that the same skewness factor reappears, sharpened to a single eigenvalue, as $1/\cos \angle (x,y)$.

Exercises Intermediate+

Advanced results Master

Theorem (condition number of a simple eigenvalue; Stewart-Sun Ch. V ^{[source pending]}; Kato Ch. II §2 ^{[source pending]}). Let $\lambda$ be a simple eigenvalue of $A$ with unit right eigenvector $x$ and unit left eigenvector $y$, $Ax=\lambda x$, $y^ A = \lambda y^$.Undertheanalyticperturbation$A + tE$theeigenvaluebranch$\lambda(t)$with$\lambda(0) = \lambda$isanalyticnear$t = 0$ with

$$\lambda (t)=\lambda +t\frac{y^{\ast }Ex}{y^{\ast }x}+O(t^2),|\lambda (t)-\lambda |\le \frac{\Vert E{\Vert }_2}{|y^{\ast }x|}|t|+O(t^2).$$

The condition number $\kappa(\lambda) = 1/|y^ x| = 1/\cos\angle(x, y)$governsthefirst-ordersensitivity,anditequals$1$ exactly when the left and right eigenvectors are parallel.*

For a normal matrix the left and right eigenvectors of a simple eigenvalue coincide up to phase, so $|y^{\ast }x|=1$ and $\kappa (\lambda )=1$: this is the per-eigenvalue refinement of the global statement ${\kappa }_2(V)=1$ from Bauer-Fike. The condition number is independent of any scaling of $x$ and $y$ because the ratio $\Vert x\Vert \Vert y\Vert /|y^{\ast }x|$ is homogeneous of degree zero in each. As $A$ approaches a matrix with a defective $\lambda$, the eigenvectors $x$ and $y$ rotate toward orthogonality, $y^{\ast }x\to 0$, and $\kappa (\lambda )\to \infty$, the analytic boundary at which the first-order expansion fails and the eigenvalue begins to move like a fractional power of the perturbation.

Theorem (defective eigenvalue: fractional-power perturbation; Kato Ch. II §1 ^{[source pending]}). Let $\lambda$ be an eigenvalue of $A$ whose largest Jordan block has size $m\ge 2$. For a generic perturbation $A+tE$, the $m$ eigenvalues splitting off from $\lambda$ behave like

$${\lambda }_k(t)=\lambda +c(t{)}^{1/m}{\omega }^k+o(t^{1/m}),\omega =e^{2\pi i/m},k=0,\dots ,m-1,$$

a Puiseux series in $t^{1/m}$ rather than a Taylor series in $t$. A defective eigenvalue is therefore infinitely ill-conditioned in the first-order sense: a perturbation of size $ϵ$ moves it by order ${ϵ}^{1/m}$, which dwarfs $ϵ$ as $ϵ\to 0$. The companion matrix of a polynomial with a repeated root exhibits exactly this, and it is why root-finding through the companion eigenproblem inherits the conditioning of multiple roots. The Bauer-Fike factor $\kappa (V)$ diverges in this limit because $V$ becomes singular as the eigenvectors merge, consistent with the breakdown of diagonalisability.

Theorem (pseudospectrum: three equivalent definitions; Trefethen-Embree Ch. 1-2 ^{[source pending]}). For $A\in M_n(\mathbb{C})$ and $ϵ>0$, the following sets coincide:

$${\sigma }_{ϵ}(A)=\{z:\Vert (zI-A{)}^{-1}{\Vert }_2\ge {ϵ}^{-1}\}=\{z:z\in \sigma (A+E),\Vert E{\Vert }_2\le ϵ\}=\{z:{\sigma }_{\min }(zI-A)\le ϵ\},$$

where ${\sigma }_{\min }$ is the smallest singular value (with $\Vert (zI-A{)}^{-1}\Vert =\infty$ for $z\in \sigma (A)$). The resolvent-norm form makes the pseudospectrum computable as a level set of $z\mapsto {\sigma }_{\min }(zI-A)$, the perturbation form gives its meaning as the reachable spectra under bounded perturbations, and the singular-value form is the bridge between the two. For a normal $A$ the resolvent norm is exactly $1/\mathrm{dist}(z,\sigma (A))$, so ${\sigma }_{ϵ}(A)$ is the union of $ϵ$-discs about the eigenvalues; for a non-normal $A$ the resolvent norm can be enormous far from the spectrum, and the pseudospectrum bulges accordingly. The pseudospectrum, not the spectrum, governs transient growth of $\Vert e^{tA}\Vert$ and $\Vert A^k\Vert$ and the behaviour of non-normal iterations, which is why a non-normal eigenvalue computation reports the spectrum but the pseudospectrum reports the trustworthy information.

Theorem (Bauer-Fike via pseudospectra; the disc-inflation form). For diagonalisable $A=V\Lambda V^{-1}$ and every $ϵ>0$,

$${\sigma }_{ϵ}(A)\subseteq \bigcup _i\{z:|z-{\lambda }_i|\le {\kappa }_2(V)ϵ\}.$$

Equivalently, the resolvent obeys $\Vert (zI-A{)}^{-1}{\Vert }_2\le {\kappa }_2(V)/\mathrm{dist}(z,\sigma (A))$. This is Bauer-Fike restated at the level of sets: the $ϵ$-pseudospectrum is contained in the eigenvalues' discs inflated by the eigenvector conditioning. The resolvent bound is the engine — it is proved by the same conjugation $V^{-1}(zI-A{)}^{-1}V=(zI-\Lambda {)}^{-1}$ that drove the theorem in the Intermediate tier, now read as a statement about the resolvent rather than a single perturbed eigenvector. The inclusion is generally not tight: the genuine pseudospectrum of a non-normal matrix can be far smaller than the Bauer-Fike disc union, which is why pseudospectra are the sharp tool and Bauer-Fike the convenient upper bound.

Synthesis. Eigenvalue conditioning is one structural fact at three magnifications, and the diagonalisation $A=V\Lambda V^{-1}$ is the foundational reason the bounds take their form: Bauer-Fike charges the global $\kappa (V)$, the per-eigenvalue theorem refines this to $1/|y^{\ast }x|=1/\cos \angle (x,y)$ for a simple eigenvalue, and the pseudospectrum draws the exact reachable set as a resolvent level curve. This is exactly where non-normality becomes visible: a normal matrix has unitary $V$, so ${\kappa }_2(V)=1$, the left and right eigenvectors coincide, $|y^{\ast }x|=1$, and the pseudospectrum is a union of round discs, so Bauer-Fike collapses to the Hermitian Weyl bound of 01.01.14. A non-normal matrix breaks all three: skewed eigenvectors inflate $\kappa (V)$, the left and right eigenvectors rotate apart so $|y^{\ast }x|$ shrinks, and the resolvent norm balloons far from the spectrum so the pseudospectrum bulges. The central insight is that eigenvalue sensitivity measures departure from normality, and the bridge from algebra to numerics is that the same factor controls how accurately any backward-stable algorithm — the QR algorithm of 43.06.03 above all — can report an eigenvalue: the computed spectrum is the exact spectrum of a nearby matrix, and Bauer-Fike turns that backward error into a forward error of size $\kappa (V)\Vert E\Vert$. Putting these together, the static perturbation theory of this unit tells the iterative algorithms of the chapter when their output can be trusted and when only the pseudospectrum carries meaning.

Full proof set Master

Proposition (Bauer-Fike, full statement and proof). For diagonalisable $A=V\Lambda V^{-1}$ and any eigenvalue $\mu$ of $A+E$, ${\min }_i|\mu -{\lambda }_i|\le {\kappa }_p(V)\Vert E{\Vert }_p$ for every induced matrix norm.

Proof. If $\mu \in \sigma (A)$ the claim is immediate. Otherwise let $(A+E)v=\mu v$ with $v\ne 0$, so $(A-\mu I)v=-Ev$. With $A=V\Lambda V^{-1}$ and $w=V^{-1}v\ne 0$, left-multiplication by $V^{-1}$ gives $(\Lambda -\mu I)w=-V^{-1}EVw$, hence $w=-(\Lambda -\mu I{)}^{-1}{V}^{-1}EVw$ since $\Lambda -\mu I$ is invertible. Submultiplicativity yields $$ |w|_p \le |(\Lambda - \mu I)^{-1}|_p,|V^{-1}|_p,|E|_p,|V|_p,|w|_p. $$ Cancel $\Vert w{\Vert }_p>0$ and use that for a diagonal matrix $\Vert (\Lambda -\mu I{)}^{-1}{\Vert }_p=({\min }_i|{\lambda }_i-\mu |{)}^{-1}$ in any induced norm, because the induced norm of a diagonal matrix is its largest entry modulus. Rearranging gives ${\min }_i|{\lambda }_i-\mu |\le {\kappa }_p(V)\Vert E{\Vert }_p$. $\square$

Proposition (first-order eigenvalue perturbation, simple eigenvalue). *Let $\lambda$ be a simple eigenvalue of $A$ with right eigenvector $x$ and left eigenvector $y$, $y^{\ast }x\ne 0$. The branch $\lambda (t)$ of $A+tE$ with $\lambda (0)=\lambda$ is analytic at $t=0$ and ${\lambda }^{\prime }(0)=y^{\ast }Ex/(y^{\ast }x)$.*

Proof. Simplicity of $\lambda$ means the spectral projection $P=x{y}^{\ast }/(y^{\ast }x)$ onto the eigenline is well defined and the resolvent $(\zeta I-A{)}^{-1}$ has a simple pole at $\zeta =\lambda$. By the analytic perturbation theory of an isolated simple eigenvalue, $\lambda (t)$ and a right eigenvector $x(t)$ depend analytically on $t$ for small $t$. Differentiate the eigenrelation $(A+tE)x(t)=\lambda (t)x(t)$ at $t=0$: $$ Ex + Ax'(0) = \lambda'(0)x + \lambda x'(0). $$ Apply $y^{\ast }$ on the left and use $y^{\ast }A=\lambda y^{\ast }$ to cancel $y^{\ast }A{x}^{\prime }(0)=\lambda y^{\ast }{x}^{\prime }(0)$ against $\lambda y^{\ast }{x}^{\prime }(0)$: $$ y^*Ex = \lambda'(0),y^*x. $$ Dividing by $y^{\ast }x\ne 0$ gives ${\lambda }^{\prime }(0)=y^{\ast }Ex/(y^{\ast }x)$. The bound $|{\lambda }^{\prime }(0)|\le \Vert E{\Vert }_2\Vert x{\Vert }_2\Vert y{\Vert }_2/|y^{\ast }x|=\kappa (\lambda )\Vert E{\Vert }_2$ follows from Cauchy-Schwarz. $\square$

Proposition (left and right eigenvectors of a normal matrix coincide). *If $A$ is normal and $\lambda$ is a simple eigenvalue with unit right eigenvector $x$, then $y=x$ is a unit left eigenvector, so $|y^{\ast }x|=1$ and $\kappa (\lambda )=1$.*

Proof. A normal matrix has $A^{\ast }A=A{A}^{\ast }$, so $A$ and $A^{\ast }$ share eigenvectors: if $Ax=\lambda x$ with $\Vert x\Vert =1$, then $A^{\ast }x=\bar{\lambda }x$. The latter says $x^{\ast }A=\lambda x^{\ast }$, so $x$ is a left eigenvector for $\lambda$. Taking $y=x$, $y^{\ast }x=x^{\ast }x=1$ and $\kappa (\lambda )=\Vert x\Vert \Vert y\Vert /|y^{\ast }x|=1$. The standard route is via the spectral theorem for normal operators, which produces an orthonormal eigenbasis; the eigenvector matrix $V$ assembling that basis is unitary, giving ${\kappa }_2(V)=1$ in agreement with the per-eigenvalue value. $\square$

Proposition (pseudospectrum equivalence: resolvent and perturbation forms). For $z\notin \sigma (A)$, $\Vert (zI-A{)}^{-1}{\Vert }_2\ge {ϵ}^{-1}$ if and only if $z\in \sigma (A+E)$ for some $E$ with $\Vert E{\Vert }_2\le ϵ$.

Proof. ($\Leftarrow$) Suppose $(A+E)v=zv$ with $v\ne 0$ and $\Vert E{\Vert }_2\le ϵ$. Then $(zI-A)v=Ev$, so $v=(zI-A{)}^{-1}Ev$ and $\Vert v{\Vert }_2\le \Vert (zI-A{)}^{-1}{\Vert }_2\Vert E{\Vert }_2\Vert v{\Vert }_2\le \Vert (zI-A{)}^{-1}{\Vert }_2ϵ\Vert v{\Vert }_2$. Cancelling $\Vert v{\Vert }_2$ gives $\Vert (zI-A{)}^{-1}{\Vert }_2\ge {ϵ}^{-1}$.

($\Rightarrow$) Suppose $\Vert (zI-A{)}^{-1}{\Vert }_2\ge {ϵ}^{-1}$. Let $u$ be a unit vector attaining the operator norm, $\Vert (zI-A{)}^{-1}u{\Vert }_2=\Vert (zI-A{)}^{-1}{\Vert }_2=:\beta \ge {ϵ}^{-1}$, and set $v=(zI-A{)}^{-1}u$, so $\Vert v{\Vert }_2=\beta$ and $(zI-A)v=u$, that is $Av=zv-u$. Define the rank-one perturbation $E=u{v}^{\ast }/\Vert v{\Vert }_2^2$, with $\Vert E{\Vert }_2=\Vert u{\Vert }_2\Vert v{\Vert }_2/\Vert v{\Vert }_2^2=1/\beta \le ϵ$. Then $Ev=u(v^{\ast }v)/\Vert v{\Vert }_2^2=u$, so $(A+E)v=Av+Ev=(zv-u)+u=zv$. Hence $z\in \sigma (A+E)$ with $\Vert E{\Vert }_2\le ϵ$. The third form follows from $\Vert (zI-A{)}^{-1}{\Vert }_2=1/{\sigma }_{\min }(zI-A)$, a standard singular-value identity. $\square$

Proposition (Bauer-Fike resolvent bound). For diagonalisable $A=V\Lambda V^{-1}$ and $z\notin \sigma (A)$, $\Vert (zI-A{)}^{-1}{\Vert }_2\le {\kappa }_2(V)/\mathrm{dist}(z,\sigma (A))$.

Proof. Conjugating, $(zI-A{)}^{-1}=V(zI-\Lambda {)}^{-1}{V}^{-1}$, since $zI-A=V(zI-\Lambda )V^{-1}$. Taking $2$-norms and using submultiplicativity, $$ |(zI - A)^{-1}|_2 \le |V|_2,|(zI - \Lambda)^{-1}|_2,|V^{-1}|_2 = \kappa_2(V),|(zI - \Lambda)^{-1}|_2. $$ The diagonal resolvent has $\Vert (zI-\Lambda {)}^{-1}{\Vert }_2={\max }_i|z-{\lambda }_i{|}^{-1}=1/\mathrm{dist}(z,\sigma (A))$, giving the bound. Combining with the perturbation form of the previous proposition: if $z\in {\sigma }_{ϵ}(A)$ then ${ϵ}^{-1}\le \Vert (zI-A{)}^{-1}{\Vert }_2\le {\kappa }_2(V)/\mathrm{dist}(z,\sigma (A))$, so $\mathrm{dist}(z,\sigma (A))\le {\kappa }_2(V)ϵ$, recovering the disc-inflation form of Bauer-Fike. $\square$

Connections Master

The eigenvalue conditioning of this unit is the non-normal completion of the Hermitian perturbation theory of 01.01.14: where Weyl's inequalities and Cauchy interlacing give $|{\lambda }_k(A+E)-{\lambda }_k(A)|\le \Vert E{\Vert }_2$ for self-adjoint $A$ — the case ${\kappa }_2(V)=1$ — Bauer-Fike supplies the general diagonalisable bound ${\kappa }_2(V)\Vert E{\Vert }_2$, and the two agree exactly when $A$ is normal, so the symmetric theory is recovered as the perfectly conditioned boundary case rather than re-proved.

The factor $\kappa (V)$ is the eigenvector-matrix instance of the conditioning theory of 43.01.02: that unit defines $\kappa (A)=\Vert A\Vert \Vert A^{-1}\Vert$ as the sensitivity of a linear solve, and here the identical quantity applied to the diagonaliser $V$ measures the sensitivity of the eigenproblem — the same conditioning concept, attached to a different matrix, which is why a matrix can be well-conditioned for solving yet ill-conditioned for its eigenvalues.

Bauer-Fike is the accuracy verdict on the QR algorithm of 43.06.03: a backward-stable eigensolver returns the exact spectrum of $A+E$ with $\Vert E\Vert =O({ϵ}_{\mathrm{mach}}\Vert A\Vert )$, and this unit converts that backward error into the forward eigenvalue error $\kappa (V)O({ϵ}_{\mathrm{mach}}\Vert A\Vert )$, so a normal matrix yields full-accuracy eigenvalues while a non-normal one limits attainable accuracy regardless of the algorithm's stability.

The condition number $1/|y^{\ast }x|$ built from left and right eigenvectors connects to the spectral-projection and biorthogonality structure underlying 43.06.01: the same left eigenvector that measures sensitivity is the one that makes the spectral projection $P=x{y}^{\ast }/(y^{\ast }x)$, and the deflation step of power-iteration variants relies on exactly this biorthogonal pairing, so a poorly separated $y^{\ast }x$ degrades both the conditioning and the numerical deflation simultaneously.

Historical & philosophical context Master

The exclusion theorem now universally called Bauer-Fike appeared in the 1960 Numerische Mathematik paper of Friedrich Bauer and C. T. Fike, "Norms and exclusion theorems," which packaged a family of eigenvalue-localisation results around the single inequality ${\min }_i|\mu -{\lambda }_i|\le {\kappa }_p(V)\Vert E{\Vert }_p$ and connected eigenvalue perturbation to the conditioning of the diagonalising transformation ^{[Bauer 1960]}. The result generalised the much older disc-localisation of Semyon Gershgorin, whose 1931 paper bounded the spectrum by the union of row discs $|z-a_{ii}|\le {\sum }_{j\ne i}|a_{ij}|$ and is the diagonally-dominant special case that Bauer-Fike subsumes when $A$ itself is taken as a perturbation of its diagonal ^{[Gershgorin 1931]}.

The first-order perturbation formula $\dot{\lambda }=y^{\ast }Ex/(y^{\ast }x)$ and the analytic theory of a simple eigenvalue, together with the Puiseux-series behaviour at a defective eigenvalue, were placed on their definitive footing by Tosio Kato in Perturbation Theory for Linear Operators, whose treatment of the analytic perturbation of isolated eigenvalues remains the standard reference ^{[Kato 1980]}. Stewart and Sun's Matrix Perturbation Theory consolidated the matrix-analytic side, defining the eigenvalue condition number through the biorthogonal left and right eigenvectors and developing the sensitivity theory used in numerical practice ^{[Stewart 1990]}. The pseudospectral viewpoint, which reframes non-normal sensitivity as the geometry of resolvent level sets, was developed and popularised by Lloyd Trefethen and collaborators through the 1990s and synthesised in Trefethen and Embree's Spectra and Pseudospectra, establishing that for non-normal matrices the pseudospectrum, not the spectrum, predicts the behaviour of matrix powers, exponentials, and iterative solvers ^{[Trefethen 2005]}.

Bibliography Master

@article{BauerFike1960,
  author  = {Bauer, Friedrich L. and Fike, C. T.},
  title   = {Norms and exclusion theorems},
  journal = {Numerische Mathematik},
  volume  = {2},
  year    = {1960},
  pages   = {137--141}
}

@article{Gershgorin1931,
  author  = {Gershgorin, Semyon Aronovich},
  title   = {{\"U}ber die Abgrenzung der Eigenwerte einer Matrix},
  journal = {Izvestiya Akademii Nauk SSSR, Otdelenie Fiziko-Matematicheskikh Nauk},
  volume  = {6},
  year    = {1931},
  pages   = {749--754}
}

@book{Kato1980,
  author    = {Kato, Tosio},
  title     = {Perturbation Theory for Linear Operators},
  edition   = {2nd},
  publisher = {Springer-Verlag},
  address   = {Berlin},
  year      = {1980}
}

@book{StewartSun1990,
  author    = {Stewart, G. W. and Sun, Ji-Guang},
  title     = {Matrix Perturbation Theory},
  publisher = {Academic Press},
  address   = {Boston},
  year      = {1990}
}

@book{TrefethenEmbree2005,
  author    = {Trefethen, Lloyd N. and Embree, Mark},
  title     = {Spectra and Pseudospectra: The Behavior of Nonnormal Matrices and Operators},
  publisher = {Princeton University Press},
  address   = {Princeton},
  year      = {2005}
}

@book{TrefethenBau1997,
  author    = {Trefethen, Lloyd N. and Bau, David},
  title     = {Numerical Linear Algebra},
  publisher = {SIAM},
  address   = {Philadelphia},
  year      = {1997}
}

@book{HornJohnson2013,
  author    = {Horn, Roger A. and Johnson, Charles R.},
  title     = {Matrix Analysis},
  edition   = {2nd},
  publisher = {Cambridge University Press},
  year      = {2013}
}

@book{GolubVanLoan2013,
  author    = {Golub, Gene H. and Van Loan, Charles F.},
  title     = {Matrix Computations},
  edition   = {4th},
  publisher = {Johns Hopkins University Press},
  address   = {Baltimore},
  year      = {2013}
}