the Bauer-Fike theorem
/ BOW-er FY-keh /
Here is a question that decides whether you can trust a computed eigenvalue: if I perturb my matrix a little (which round-off always does), how far can its eigenvalues move? For symmetric matrices the answer is reassuring — they barely move. For general nonsymmetric matrices the answer can be alarming, and the Bauer-Fike theorem is the precise statement of how alarming. It bounds the displacement of eigenvalues in terms of one number: the conditioning of the eigenvector matrix.
Suppose A is diagonalizable as A = V Lambda V^(-1), so its columns of V are the eigenvectors. The Bauer-Fike theorem says that if you perturb A by a matrix E, then every eigenvalue of A + E lies within a distance kappa(V) * ||E|| of some eigenvalue of A, where kappa(V) = ||V|| * ||V^(-1)|| is the condition number of the eigenVECTOR matrix. Read that carefully: the amplification factor is kappa(V), not the condition number of A itself. If the eigenvectors are orthogonal — exactly the symmetric/normal case — then V is orthogonal, kappa(V) = 1, and eigenvalues move at most ||E||: perfectly conditioned. But if the eigenvectors are nearly parallel (the matrix is far from normal), kappa(V) can be enormous, and a round-off-level E can shove eigenvalues a long way. That is precisely why nonsymmetric eigenvalue problems can be sensitive.
The practical upshot connects directly to the master formula accuracy = conditioning x stability. The QR algorithm is backward stable, meaning it returns the exact eigenvalues of A + E with ||E|| at the round-off level. By Bauer-Fike, your computed eigenvalues are then accurate to about kappa(V) * machine-epsilon. So for a symmetric matrix you get full precision, but for a highly non-normal matrix you may lose many digits — and this is the problem's fault, not the algorithm's. There is a sharper, per-eigenvalue version using the angle between left and right eigenvectors (1/cos gives the condition number of that single eigenvalue), explaining why some eigenvalues of a matrix are well-conditioned while others, in the same matrix, are not.
Compare two matrices. A symmetric matrix has orthogonal eigenvectors, kappa(V) = 1; a 1e-15 round-off perturbation moves its eigenvalues by at most about 1e-15. Now take a strongly non-normal matrix with rows (1, 1e8) and (0, 2): its eigenvectors are nearly parallel so kappa(V) is around 1e8, and Bauer-Fike warns that a 1e-15 perturbation can move the eigenvalues by up to about 1e-7 — seven digits lost, even from a backward-stable algorithm.
Eigenvalue sensitivity is amplified by the conditioning of the eigenvector matrix, kappa(V); orthogonal eigenvectors (kappa=1) mean perfect conditioning.
Bauer-Fike bounds eigenVALUE conditioning via kappa(V), which is NOT the condition number of A (used for solving A x = b). A matrix can be perfectly conditioned for linear solving yet have terribly ill-conditioned eigenvalues, and vice versa — they are different questions. The theorem assumes A is diagonalizable; a defective matrix (with a non-trivial Jordan block) is even more sensitive.