Hessenberg matrix

An upper Hessenberg matrix has zero entries below the first subdiagonal; the lower version has zero entries above the first superdiagonal. The upper Hessenberg matrix is one of these two forms.

Without row interchanges, an upper Hessenberg matrix needs only one elimination per pivot column. Its lower factor is unit lower bidiagonal, while its upper factor is upper triangular. If the original matrix is symmetric, it is tridiagonal and the upper factor is also bidiagonal.

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.

An upper Hessenberg matrix has zero entries below its first subdiagonal: $a_{ij}=0$ whenever $i>j+1$.