In linear algebra, a Hessenberg matrix is a special kind of square matrix, 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.
[1] They are named after Karl Hessenberg.
An upper Hessenberg matrix is called unreduced if all subdiagonal entries are nonzero, i.e. if
is said to be in lower Hessenberg form or to be a lower Hessenberg matrix if its transpose
is an upper Hessenberg matrix or equivalently if
A lower Hessenberg matrix is called unreduced if all superdiagonal entries are nonzero, i.e. if
is an upper unreduced Hessenberg matrix,
is a lower unreduced Hessenberg matrix and
is a lower Hessenberg matrix but is not unreduced.
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.
If the constraints of a linear algebra problem do not allow a general matrix to be conveniently reduced to a triangular one, reduction to Hessenberg form is often the next best thing.
In fact, reduction of any matrix to a Hessenberg form can be achieved in a finite number of steps (for example, through Householder's transformation of unitary similarity transforms).
Subsequent reduction of Hessenberg matrix to a triangular matrix can be achieved through iterative procedures, such as shifted QR-factorization.
In eigenvalue algorithms, the Hessenberg matrix can be further reduced to a triangular matrix through Shifted QR-factorization combined with deflation steps.
Reducing a general matrix to a Hessenberg matrix and then reducing further to a triangular matrix, instead of directly reducing a general matrix to a triangular matrix, often economizes the arithmetic involved in the QR algorithm for eigenvalue problems.
The following procedure for such a transformation is adapted from A Second Course In Linear Algebra by Garcia & Roger.
This householder matrix will map
constructed by removing the first row and the first column of
which has only zeros below the first and second entry of the subdiagonal.
constructed by removing the first row and first column of
matrix are invariant under multiplication by
Hence, any matrix can be transformed to an upper Hessenberg matrix by a similarity transformation of the form
A Jacobi rotation (also called Givens rotation) is an orthogonal matrix transformation in the form where
to satisfy the equation Now, the sequence of such Jacobi rotations with the following
to the lower Hessenberg form.
This includes the symmetric or Hermitian Hessenberg matrices.
A Hermitian matrix can be reduced to tri-diagonal real symmetric matrices.
It commonly occurs as the generalization of the Jacobi operator to a system of orthogonal polynomials for the space of square-integrable holomorphic functions over some domain—that is, a Bergman space.
The eigenvalues of each principal submatrix of the Hessenberg operator are given by the characteristic polynomial for that submatrix.