Eigenvalue Problems & the SVD

the ill-conditioning of the characteristic polynomial

You learned in linear algebra that the eigenvalues of a square matrix A are the roots of its characteristic polynomial p(lambda) = det(A - lambda I). So the obvious plan to find eigenvalues numerically is: expand that determinant into a polynomial, then find its roots. This plan is a trap. Forming the polynomial and then rooting it is one of the worst ways to compute eigenvalues on a computer, and understanding why is the gateway to every serious eigenvalue algorithm.

The trouble is that the roots of a polynomial can be wildly sensitive to tiny changes in its coefficients, even when the original matrix's eigenvalues are perfectly tame. Wilkinson's famous example is the polynomial with roots at 1, 2, 3, ..., 20. Perturb the coefficient of lambda^19 by about 2^(-23) (a change in the 7th decimal place) and some roots move by several units and even split into complex pairs. So the map from matrix to coefficients to roots passes through an enormously ill-conditioned middle step: small round-off in forming or storing the coefficients gets amplified catastrophically when you root the polynomial.

The honest conclusion is that you do NOT find eigenvalues by building and solving the characteristic polynomial; that pipeline is numerically unstable even for well-conditioned matrices. Instead, every practical eigensolver works directly on the matrix through orthogonal transformations (the QR algorithm, the power method, Krylov methods). The lesson generalizes: an exact mathematical identity (eigenvalues = polynomial roots) can be a terrible computational recipe. Curiously, the relationship runs the other way too: to find the roots of a polynomial reliably, software often forms its companion matrix and computes that matrix's eigenvalues instead.

Take A as the 2x2 matrix with rows (1, 1000) and (0, 1). Its eigenvalues are both 1. Now perturb the bottom-left entry from 0 to a tiny 1e-6. The characteristic polynomial becomes lambda^2 - 2 lambda + (1 - 0.001), whose roots are 1 +/- sqrt(0.001) ~= 1.0316 and 0.9684 — a change of about 0.03 in the eigenvalues from a change of 1e-6 in an entry. The large off-diagonal entry (a non-normal matrix) has made the eigenvalues sensitive, and going through coefficients only worsens it.

Tiny matrix perturbations can move eigenvalues a lot; routing through polynomial coefficients amplifies the damage.

This is about the algorithm's instability, not the eigenvalues being meaningless: a symmetric matrix's eigenvalues are perfectly well-conditioned, yet forming its characteristic polynomial and rooting it still loses accuracy. The polynomial route is bad even when the underlying problem is good.

Also called
why not solve det(A - lambda I) = 0roots of the characteristic polynomial are unstable