Householder tridiagonalization (source code)

= Householder tridiagonalization
{c}
{wiki}

<Householder tridiagonalization> reduces a real <symmetric matrix> $A$ by an <orthogonal similarity> to a real <symmetric> <tridiagonal matrix> $T$:
$$
T=Q^TAQ.
$$
At column $j$, a <Householder reflection> on coordinates $j+1,\ldots,n$ eliminates entries below row $j+1$. Apply the same reflection from the right, preserving symmetry. Since entries below the first subdiagonal become zero, symmetry also makes entries above the first superdiagonal zero. Earlier zeros are preserved by the restricted active coordinates.

The <eigenvalues> are unchanged by the <similarity transformation>; an <eigenvector> $z$ of $T$ gives the <eigenvector> $Qz$ of $A$. Dense reduction costs $O(n^3)$ <arithmetic operations> once, after which each structured <QR algorithm> step on the tridiagonal form is much cheaper than a new dense factorization. This is why eigensolvers separate reduction from iterative refinement of <eigenvalues>.