reduction to Hessenberg form
/ HESS-en-berg /
Before unleashing the QR algorithm on a matrix to find its eigenvalues, you first do a one-time cleanup that makes everything afterward dramatically cheaper. You squeeze the matrix into a nearly-triangular shape called Hessenberg form: zeros everywhere below the first subdiagonal. It still has its full upper triangle and one extra diagonal below the main one, but the rest is zero. Crucially this is done with orthogonal transformations, so the eigenvalues are preserved exactly (in exact arithmetic) while the structure becomes sparse.
The reduction uses Householder reflections, just like in QR factorization, but applied from both sides: A becomes Q^T A Q. A two-sided orthogonal transformation Q^T A Q is a similarity transformation, so it does not change the eigenvalues — that is the whole point. (Apply Householder only from the left and you would change the eigenvalues; you must sandwich it.) Column by column, each reflection zeros out the entries below the subdiagonal in one column without disturbing the zeros already created. The cost is a fixed O(n^3), done once. For a symmetric matrix the result is even better: Hessenberg-plus-symmetric forces TRIDIAGONAL form (nonzero only on the main diagonal and the two adjacent diagonals), which is extraordinarily cheap to work with.
Why bother? Because a single QR step on a full n-by-n matrix costs O(n^3), but on a Hessenberg matrix it costs only O(n^2), and on a tridiagonal matrix only O(n). Since the QR algorithm needs many steps, that reduction in per-step cost is what makes finding all eigenvalues affordable — overall O(n^3) instead of O(n^4) or worse. Hessenberg form is also preserved by QR steps (a QR step of a Hessenberg matrix stays Hessenberg), so you pay the reduction cost once and reap the savings on every subsequent iteration. It is the unglamorous but essential first move of the standard dense eigensolver.
A 4x4 full matrix has potentially 16 nonzeros. Its Hessenberg form keeps the 4+3+2+1 = 10 upper-triangle entries plus 3 subdiagonal entries — but the 3 entries in the bottom-left corner (positions (3,1),(4,1),(4,2)) are zeroed. If the matrix is symmetric, the result is tridiagonal: just the 4 diagonal and 3 off-diagonal values, 7 numbers describing the whole spectrum.
Two-sided Householder reflections compress A to Hessenberg (tridiagonal if symmetric) without changing eigenvalues.
The transformation must be applied to BOTH sides (a similarity Q^T A Q) to preserve eigenvalues; a one-sided Householder, as used in QR least squares, would change them. You cannot reduce all the way to triangular by a finite sequence of similarities — that would hand you the eigenvalues directly, which is impossible by a finite algorithm; Hessenberg is as far as a finite reduction goes.