Hessenberg matrix

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. They are named after Karl Hessenberg.
Definitions.
Upper Hessenberg matrix.
A square formula_1 matrix formula_2 is said to be in upper Hessenberg form or to be an upper Hessenberg matrix if formula_3 for all formula_4 with formula_5.
An upper Hessenberg matrix is called unreduced if all subdiagonal entries are nonzero, i.e. if formula_6 for all formula_7.
Lower Hessenberg matrix.
A square formula_1 matrix formula_2 is said to be in lower Hessenberg form or to be an lower Hessenberg matrix if its transpose formula_10 is an upper Hessenberg matrix or equivalently if formula_3 for all formula_4 with formula_13.
A lower Hessenberg matrix is called unreduced if all superdiagonal entries are nonzero, i.e. if formula_14 for all formula_7.
Examples.
Consider the following matrices.
The matrix formula_2 is an upper unreduced Hessenberg matrix, formula_20 is a lower unreduced Hessenberg matrix and formula_21 is a lower Hessenberg matrix but is not unreduced.
Computer programming.
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.
Properties.
For formula_22, it is vacuously true that every formula_23 matrix is both upper Hessenberg, and lower Hessenberg.
The product of a Hessenberg matrix with a triangular matrix is again Hessenberg. More precisely, if formula_2 is upper Hessenberg and formula_25 is upper triangular, then formula_26 and formula_27 are upper Hessenberg.
A matrix that is both upper Hessenberg and lower Hessenberg is a tridiagonal matrix, of which symmetric or Hermitian Hessenberg matrices are important examples. A Hermitian matrix can be reduced to tri-diagonal real symmetric matrices.
Hessenberg operator.
The Hessenberg operator is an infinite dimensional Hessenberg matrix. 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. In this case, the Hessenberg operator is the right-shift operator formula_28, given by 
The eigenvalues of each principal submatrix of the Hessenberg operator are given by the characteristic polynomial for that submatrix. These polynomials are called the Bergman polynomials, and provide an orthogonal polynomial basis for Bergman space.