View source for Bauer-Fike theorem

As popularized in most texts on computational [[Linear-algebra(2)|linear algebra]] or numerical methods, the Bauer–Fike theorem is a theorem on the perturbation of eigenvalues of a diagonalizable matrix. However, it is actually just one theorem out of a small collection of theorems on the localization of eigenvalues within small regions of the complex plane [[#References|[a1]]].

A vector norm is a [[Functional|functional]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b1300601.png" /> on a vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b1300602.png" /> which satisfies three properties:

1) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b1300603.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b1300604.png" /> if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b1300605.png" />.

2) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b1300606.png" /> for any scalar <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b1300607.png" />.

3) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b1300608.png" /> (the triangle inequality). A matrix norm <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b1300609.png" /> satisfies the above three properties plus one more:

4) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006010.png" /> (the submultiplicative inequality). An operator norm is a matrix norm derived from a related vector norm:

5) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006011.png" />. The most common vector norms are:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006012.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006013.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006014.png" /> denotes the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006015.png" />th entry of the vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006016.png" />. The operator norms derived from these are, respectively:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006017.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006018.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006019.png" /> denotes the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006020.png" />th entry of the matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006021.png" />. In particular, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006022.png" /> is the  "maximum absolute row sum"  and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006023.png" /> is the  "maximum absolute column sum" . For details, see, e.g., [[#References|[a2]]], Sec. 2.2–2.3.

Below, the notation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006024.png" /> will denote a vector norm when applied to a vector and an operator matrix norm when applied to a matrix.

Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006025.png" /> be a real or complex <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006026.png" />-matrix that is diagonalizable (i.e. it has a complete set of eigenvectors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006027.png" /> corresponding to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006028.png" /> eigenvalues <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006029.png" />, which need not be distinct; cf. also [[Eigen vector|Eigen vector]]; [[Eigen value|Eigen value]]; [[Complete set|Complete set]]). Its eigenvectors make up an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006030.png" />-matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006031.png" />; let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006032.png" /> be the diagonal matrix. Then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006033.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006034.png" /> be an arbitrary <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006035.png" />-matrix. The popular Bauer–Fike theorem states that for such <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006036.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006037.png" />, every eigenvalue <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006038.png" /> of the matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006039.png" /> satisfies the inequality

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006040.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a1)</td></tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006041.png" /> is some arbitrary eigenvalue of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006042.png" />.

If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006043.png" /> is small, this theorem states that every eigenvalue of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006044.png" /> is close to some eigenvalue of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006045.png" />, and that the distance between eigenvalues of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006046.png" /> and eigenvalues of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006047.png" /> varies linearly with the perturbation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006048.png" />. But this is not an asymptotic result valid only as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006049.png" />; this result holds for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006050.png" />. In this sense, it is a very powerful localization theorem for eigenvalues.

As an illustration, consider the following situation. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006051.png" /> be an arbitrary <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006052.png" />-matrix, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006053.png" /> be the diagonal part of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006054.png" />, and define <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006055.png" /> to be the matrix of all off-diagonal entries. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006056.png" /> be an arbitrary eigenvalue of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006057.png" />. The matrix of eigenvectors for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006058.png" /> is just the identity matrix, so the Bauer–Fike theorem implies that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006059.png" />, for some diagonal entry <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006060.png" />. The <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006061.png" />-norm <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006062.png" /> is just the maximum absolute row sum over the off-diagonal entries of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006063.png" />. In this norm the assertion means that every eigenvalue of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006064.png" /> lies in a circle centred at a diagonal entry of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006065.png" /> with radius equal to the maximum absolute row sum over the off-diagonal entries. This is a weak form of a Gershgorin-type theorem, which localizes the eigenvalues to circles centred at the diagonal entries, but the radius here is not as tight as in the true Gershgorin theory [[#References|[a2]]], sec. 7.2.1, (cf. also [[Gershgorin theorem|Gershgorin theorem]]).

Another simple consequence of the Bauer–Fike theorem applies to symmetric, Hermitian or normal matrices (cf. also [[Symmetric matrix|Symmetric matrix]]; [[Normal matrix|Normal matrix]]; [[Hermitian matrix|Hermitian matrix]]). If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006066.png" /> is symmetric, Hermitian or normal, then the matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006067.png" /> of eigenvectors can be made unitary (orthogonal if real; cf. also [[Unitary matrix|Unitary matrix]]), which means that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006068.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006069.png" /> denotes the complex conjugate transpose of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006070.png" />. Then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006071.png" />, and (a1) reduces to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006072.png" />. Hence, for symmetric, Hermitian or normal matrices, the change to any eigenvalue is no larger than the norm of the change to the matrix itself.

The Bauer–Fike theorem as stated above has some limitations. The first is that it only applies to diagonalizable matrices. The second is that it says nothing about the correspondence between an eigenvalue <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006073.png" /> of the perturbed matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006074.png" /> and the eigenvalues of the unperturbed matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006075.png" />. In particular, as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006076.png" /> increases from zero, it is difficult to predict how each eigenvalue of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006077.png" /> will move, and there is no way to predict which eigenvalue of the original <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006078.png" /> corresponds to any particular eigenvalue <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006079.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006080.png" />, except in certain special cases such as symmetric or Hermitian matrices.

However, in their original paper [[#References|[a1]]], F.L. Bauer and C.T. Fike presented several more general results to relieve the limitation to diagonalizable matrices. The most important of these is the following: Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006081.png" /> be an arbitrary <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006082.png" />-matrix, and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006083.png" /> denote any eigenvalue of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006084.png" />. Then either <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006085.png" /> is also an eigenvalue of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006086.png" /> or

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006087.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a2)</td></tr></table>

This result follows from a simple matrix manipulation, using the norm properties given above:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006088.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006089.png" /></td> </tr></table>

Even though this may appear to be a rather technical result, it actually leads to a great many often-used results. For example, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006090.png" /> is diagonalizable, it is easy to show that

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006091.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006092.png" /></td> </tr></table>

which leads immediately to the popular Bauer–Fike theorem (using the fact that the operator norm of a diagonal matrix is just its largest entry in absolute value). One can also repeat the construction, in which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006093.png" /> is an arbitrary matrix, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006094.png" /> is the matrix consisting of the diagonal entries of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006095.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006096.png" /> is the matrix of off- diagonal entries. Using the norm <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006097.png" />, the leftmost inequality in (a2) then reduces to

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130060/b13006098.png" /></td> </tr></table>

leading immediately to the first [[Gershgorin theorem|Gershgorin theorem]] (see also [[#References|[a2]]], Sec. 7.2.1.

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  F.L. Bauer,   C.T. Fike,   "Norms and exclusion theorems"  ''Numer. Math.'' , '''2'''  (1960)  pp. 137–141</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  G.H. Golub,   C.F. Van Loan,   "Matrix computations" , Johns Hopkins Univ. Press  (1996)  (Edition: Third)</TD></TR></table>