Hessenberg matrix

In linear algebra, a Hessenberg matrix is one that is "almost" triangular. To be exact, an upper Hessenberg matrix has zero entries below the first subdiagonal, and a lower Hessenberg matrix has zero entries above the first superdiagonal.

For example:

<math>\begin{bmatrix}

1 & 4 & 2 & 3 \\ 3 & 4 & 1 & 7 \\ 0 & 2 & 3 & 4 \\ 0 & 0 & 1 & 3 \\ \end{bmatrix}<math> is upper Hessenberg and

<math>\begin{bmatrix}

1 & 2 & 0 & 0 \\ 5 & 2 & 3 & 0 \\ 3 & 4 & 3 & 7 \\ 5 & 6 & 1 & 1 \\ \end{bmatrix}<math> is lower Hessenberg.

Many linear algebra algorithms require significantly less computational effort when applied to triangular matrices, and this improvement often carries over to Hessenberg matrices as well. When the constraints of a linear algebra problem don't allow a general matrix to be reduced to a triangular one, reduction to Hessenberg form is often the next best thing. In particular, many eigenvalue algorithms involve Hessenberg reduction as a first step.

A related generalization of a diagonal matrix is the tridiagonal matrix.