 Hessenberg reduction

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,\dots ,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.