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.^[1] They are named after Karl Hessenberg.^[2]

Definitions[]

Upper Hessenberg matrix[]

A square ${\displaystyle n\times n}$ matrix ${\displaystyle A}$ is said to be in upper Hessenberg form or to be an upper Hessenberg matrix if ${\displaystyle a_{i,j}=0}$ for all ${\displaystyle i,j}$ with ${\displaystyle i>j+1}$.

An upper Hessenberg matrix is called unreduced if all subdiagonal entries are nonzero, i.e. if ${\displaystyle a_{i+1,i}\neq 0}$ for all ${\displaystyle i\in \{1,\ldots ,n-1\}}$.^[3]

Lower Hessenberg matrix[]

A square ${\displaystyle n\times n}$ matrix ${\displaystyle A}$ is said to be in lower Hessenberg form or to be a lower Hessenberg matrix if its transpose ${\displaystyle }$ is an upper Hessenberg matrix or equivalently if ${\displaystyle a_{i,j}=0}$ for all ${\displaystyle i,j}$ with ${\displaystyle j>i+1}$.

A lower Hessenberg matrix is called unreduced if all superdiagonal entries are nonzero, i.e. if ${\displaystyle a_{i,i+1}\neq 0}$ for all ${\displaystyle i\in \{1,\ldots ,n-1\}}$.

Examples[]

Consider the following matrices.

${\displaystyle A={\begin{bmatrix}1&4&2&3\\3&4&1&7\\0&2&3&4\\0&0&1&3\\\end{bmatrix}}}$

${\displaystyle B={\begin{bmatrix}1&2&0&0\\5&2&3&0\\3&4&3&7\\5&6&1&1\\\end{bmatrix}}}$

${\displaystyle C={\begin{bmatrix}1&2&0&0\\5&2&0&0\\3&4&3&7\\5&6&1&1\\\end{bmatrix}}}$

The matrix ${\displaystyle A}$ is an upper unreduced Hessenberg matrix, ${\displaystyle B}$ is a lower unreduced Hessenberg matrix and ${\displaystyle C}$ 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.

Reduction to Hessenberg matrix[]

Any ${\displaystyle n\times n}$ matrix can be transformed into a Hessenberg matrix by a similarity transformation using Householder transformations. The following procedure for such a transformation is adapted from 'A Second Course In Linear Algebra' by Garcia & Roger.^[4]

Let ${\displaystyle A}$ be any real or complex ${\displaystyle n\times n}$ matrix, then let ${\displaystyle A^{\prime }}$ be the ${\displaystyle (n-1)\times n}$ submatrix of ${\displaystyle A}$ constructed by removing the first row in ${\displaystyle A}$ and let ${\displaystyle \mathbf {a} _{1}^{\prime }}$ be the first column of ${\displaystyle A^{\prime }}$. Construct the ${\displaystyle (n-1)\times (n-1)}$ householder matrix ${\displaystyle V_{1}=I_{(n-1)}-2{\frac {ww^{*}}{||w||^{2}}}}$ where

${\displaystyle w={\begin{cases}||\mathbf {a} _{1}^{\prime }||_{2}\mathbf {e} _{1}-\mathbf {a} _{1}^{\prime }\;\;\;\;\;\;\;\;,\;\;\;a_{11}^{\prime }=0\\||\mathbf {a} _{1}^{\prime }||_{2}\mathbf {e} _{1}+{\frac {\overline {a_{11}^{\prime }}}{|a_{11}^{\prime }|}}\mathbf {x} \;\;\;,\;\;\;a_{11}^{\prime }\neq 0\\\end{cases}}}$

This householder matrix will map ${\displaystyle \mathbf {a} _{1}^{\prime }}$ to ${\displaystyle ||\mathbf {a} _{1}^{\prime }||\mathbf {e} _{1}}$ and as such, the block matrix ${\displaystyle U_{1}={\begin{bmatrix}1&\mathbf {0} \\\mathbf {0} &V_{1}\end{bmatrix}}}$ will map the matrix ${\displaystyle A}$ to the matrix ${\displaystyle U_{1}A}$ which has only zeros below the second entry of the first column. Now construct ${\displaystyle (n-2)\times (n-2)}$ householder matrix ${\displaystyle V_{2}}$ in a similar manner as ${\displaystyle V_{1}}$ such that ${\displaystyle V_{2}}$ maps the first column of ${\displaystyle A^{\prime \prime }}$ to ${\displaystyle ||\mathbf {a} _{1}^{\prime \prime }||\mathbf {e} _{1}}$, where ${\displaystyle A^{\prime \prime }}$ is the submatrix of ${\displaystyle A^{\prime }}$ constructed by removing the first row and the first column of ${\displaystyle A^{\prime }}$, then let ${\displaystyle U_{2}={\begin{bmatrix}1&0&0\\0&1&0\\0&0&V_{2}\end{bmatrix}}}$ which maps ${\displaystyle U_{1}A}$ to the matrix ${\displaystyle U_{2}U_{1}A}$ which has only zeros below the first and second entry of the subdiagonal. Now construct ${\displaystyle V_{3}}$ and then ${\displaystyle U_{3}}$ in a similar manner, but for the matrix ${\displaystyle A^{\prime \prime \prime }}$ constructed by removing the first row and first column of ${\displaystyle A^{\prime \prime }}$ and proceed as in the previous steps. Continue like this for a total of ${\displaystyle n-2}$ steps.

Realising that the first ${\displaystyle k}$ rows of any ${\displaystyle n\times n}$ matrix is invariant under multiplication by ${\displaystyle U_{k}^{*}}$ from the right, by construction of ${\displaystyle U_{k}}$, and so, any matrix can be transformed to an upper Hessenberg matrix by a similarity transformation of the form ${\displaystyle U_{(n-2)}(\dots (U_{2}(U_{1}AU_{1}^{*})U_{2}^{*})\dots )U_{(n-2)}^{*}=U_{(n-2)}\dots U_{2}U_{1}A(U_{(n-2)}\dots U_{2}U_{1})^{*}=UAU^{*}}$.

Properties[]

For ${\displaystyle n\in \{1,2\}}$, it is vacuously true that every ${\displaystyle n\times n}$ matrix is both upper Hessenberg, and lower Hessenberg.^[5]

The product of a Hessenberg matrix with a triangular matrix is again Hessenberg. More precisely, if ${\displaystyle A}$ is upper Hessenberg and ${\displaystyle T}$ is upper triangular, then ${\displaystyle AT}$ and ${\displaystyle TA}$ 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.^[6]

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 ${\displaystyle S}$, given by

${\displaystyle [Sf](z)=zf(z)}$.

The eigenvalues of each principal submatrix of the Hessenberg operator are given by the characteristic polynomial for that submatrix. These polynomials are called the , and provide an orthogonal polynomial basis for Bergman space.

See also[]

• Hessenberg variety

Notes[]

References[]

• Horn, Roger A.; Johnson, Charles R. (1985), Matrix Analysis, Cambridge University Press, ISBN 978-0-521-38632-6.
• Stoer, Josef; Bulirsch, Roland (2002), Introduction to Numerical Analysis (3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-0-387-95452-3.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Section 11.6.2. Reduction to Hessenberg Form", Numerical Recipes: The Art of Scientific Computing (3rd ed.), New York: Cambridge University Press, ISBN 978-0-521-88068-8

External links[]

• Hessenberg matrix at MathWorld.
• Hessenberg matrix at PlanetMath.
• High performance algorithms for reduction to condensed (Hessenberg, tridiagonal, bidiagonal) form