Bauer-Fike theorem

As popularized in most texts on computational 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 [a1].

A vector norm is a functional on a vector which satisfies three properties:

1) , and if and only if .

2) for any scalar .

3) (the triangle inequality). A matrix norm satisfies the above three properties plus one more:

4) (the submultiplicative inequality). An operator norm is a matrix norm derived from a related vector norm:

5) . The most common vector norms are:

where denotes the th entry of the vector . The operator norms derived from these are, respectively:

where denotes the th entry of the matrix . In particular, is the "maximum absolute row sum" and is the "maximum absolute column sum" . For details, see, e.g., [a2], Sec. 2.2–2.3.

Below, the notation will denote a vector norm when applied to a vector and an operator matrix norm when applied to a matrix.

Let be a real or complex -matrix that is diagonalizable (i.e. it has a complete set of eigenvectors corresponding to eigenvalues , which need not be distinct; cf. also Eigen vector; Eigen value; Complete set). Its eigenvectors make up an -matrix ; let be the diagonal matrix. Then . Let be an arbitrary -matrix. The popular Bauer–Fike theorem states that for such and , every eigenvalue of the matrix satisfies the inequality

(a1)

where is some arbitrary eigenvalue of .

If is small, this theorem states that every eigenvalue of is close to some eigenvalue of , and that the distance between eigenvalues of and eigenvalues of varies linearly with the perturbation . But this is not an asymptotic result valid only as ; this result holds for any . In this sense, it is a very powerful localization theorem for eigenvalues.

As an illustration, consider the following situation. Let be an arbitrary -matrix, let be the diagonal part of , and define to be the matrix of all off-diagonal entries. Let be an arbitrary eigenvalue of . The matrix of eigenvectors for is just the identity matrix, so the Bauer–Fike theorem implies that , for some diagonal entry . The -norm is just the maximum absolute row sum over the off-diagonal entries of . In this norm the assertion means that every eigenvalue of lies in a circle centred at a diagonal entry of 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 [a2], sec. 7.2.1, (cf. also Gershgorin theorem).

Another simple consequence of the Bauer–Fike theorem applies to symmetric, Hermitian or normal matrices (cf. also Symmetric matrix; Normal matrix; Hermitian matrix). If is symmetric, Hermitian or normal, then the matrix of eigenvectors can be made unitary (orthogonal if real; cf. also Unitary matrix), which means that , where denotes the complex conjugate transpose of . Then , and (a1) reduces to . 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 of the perturbed matrix and the eigenvalues of the unperturbed matrix . In particular, as increases from zero, it is difficult to predict how each eigenvalue of will move, and there is no way to predict which eigenvalue of the original corresponds to any particular eigenvalue of , except in certain special cases such as symmetric or Hermitian matrices.

However, in their original paper [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 be an arbitrary -matrix, and let denote any eigenvalue of . Then either is also an eigenvalue of or

(a2)

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

Even though this may appear to be a rather technical result, it actually leads to a great many often-used results. For example, if is diagonalizable, it is easy to show that

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 is an arbitrary matrix, is the matrix consisting of the diagonal entries of , and is the matrix of off- diagonal entries. Using the norm , the leftmost inequality in (a2) then reduces to

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

References

[a1]	F.L. Bauer, C.T. Fike, "Norms and exclusion theorems" Numer. Math. , 2 (1960) pp. 137–141
[a2]	G.H. Golub, C.F. Van Loan, "Matrix computations" , Johns Hopkins Univ. Press (1996) (Edition: Third)