= Hessenberg reduction
{c}
{title2=$H=Q^TAQ,\quad H_{ij}=0\ (i>j+1)$}
The reduction of a real square <matrix> to upper Hessenberg form uses <orthogonal similarity transformations>. A <Householder reflector> at column $k$ acts on rows $k+1,\ldots,n$ to annihilate entries below row $k+1$, and its matching right action preserves similarity. Previous zeros are preserved. Rank-one application of each reflector gives total $O(n^3)$ work. Subsequent shifted systems with $H-\lambda I$ can be factored in $O(n^2)$ work each because only one entry per column lies below the diagonal.
Back to article page
