Hessenberg reduction

An upper Hessenberg matrix is almost upper-triangular: it is allowed nonzeros on and above the main diagonal plus one extra subdiagonal just below it, but everything farther down is zero. It is the closest you can get to triangular by orthogonal similarity alone, without already solving the eigenvalue problem. Hessenberg reduction is the preprocessing step that transforms any matrix into this nearly-triangular shape.

The reduction is done by a sequence of Householder reflections applied on both sides: A becomes H = Q^T A Q, an orthogonal similarity, so H has exactly the same eigenvalues as A. Crucially you cannot push all the way to triangular this way — that would hand you the eigenvalues directly, which no finite algorithm can do for general matrices. One subdiagonal is the irreducible residue. The cost is a fixed O(n^3), done once.

The payoff is what it does to the QR algorithm. A QR step on a full matrix costs O(n^3), but a QR step on a Hessenberg matrix costs only O(n^2), and the Hessenberg structure is preserved by each step. So you pay O(n^3) once to reduce, then run many cheap O(n^2) iterations. Without this reduction the QR algorithm would be hopelessly slow.

Symmetry makes it even better. If A is symmetric, the Hessenberg form must also be symmetric, and a symmetric matrix with only one subdiagonal is tridiagonal. So the symmetric case reduces to a tridiagonal matrix, on which each QR step costs just O(n) and the whole eigenproblem becomes extremely cheap — the foundation of fast symmetric eigensolvers.