Hessenberg form

Almost triangular: every entry below the FIRST subdiagonal is zero, one diagonal's worth of extra room past strictly triangular.

A matrix is in upper Hessenberg form if $a_{ij}=0$ whenever $i>j+1$ -- zero everywhere below the first subdiagonal. A SYMMETRIC matrix in Hessenberg form is automatically tridiagonal (zero below the first subdiagonal AND above the first superdiagonal, by symmetry). Reducing $A$ to Hessenberg form by a sequence of Householder similarity transforms is a one-time cost that makes every later QR-algorithm iteration far cheaper.

Examples

A $4\times4$ Hessenberg matrix can have nonzero entries on and above the diagonal, plus the single subdiagonal -- but every entry two or more rows below the diagonal is exactly zero.