Chapter 82. Hessenberg Form

Hessenberg form is a nearly triangular matrix form used mainly in eigenvalue computation. It is less restrictive than triangular form, but structured enough to make algorithms faster.

A square matrix is in upper Hessenberg form if all entries below the first subdiagonal are zero. Thus an $n \times n$ matrix $H$ is upper Hessenberg when

h_{ij}=0 \qquad \text{whenever} \qquad i>j+1.

It has the pattern

H = \begin{bmatrix} h_{11} & h_{12} & h_{13} & \cdots & h_{1n} \\ h_{21} & h_{22} & h_{23} & \cdots & h_{2n} \\ 0 & h_{32} & h_{33} & \cdots & h_{3n} \\ 0 & 0 & h_{43} & \cdots & h_{4n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & h_{n,n-1} & h_{nn} \end{bmatrix}.

The upper Hessenberg form is important because the QR algorithm preserves it, and a QR step on a Hessenberg matrix costs much less than a QR step on a general dense matrix. Standard eigenvalue algorithms therefore first reduce a general matrix to Hessenberg form, then apply shifted QR iteration.

82.1 Definition

An upper Hessenberg matrix is a square matrix whose entries are zero below the first subdiagonal.

For example,

\begin{bmatrix} 2 & 1 & 4 & 3 \\ 5 & 6 & 7 & 8 \\ 0 & 9 & 1 & 2 \\ 0 & 0 & 3 & 4 \end{bmatrix}

is upper Hessenberg.

The entries immediately below the diagonal may be nonzero:

h_{21}, h_{32}, \ldots, h_{n,n-1}.

All entries below those positions must be zero.

A lower Hessenberg matrix is defined similarly, with all entries above the first superdiagonal equal to zero. In numerical eigenvalue algorithms, upper Hessenberg form is the more common convention.

82.2 Relation to Triangular Form

An upper triangular matrix has the form

u_{ij}=0 \qquad \text{whenever} \qquad i>j.

An upper Hessenberg matrix relaxes this by allowing one extra nonzero diagonal below the main diagonal:

h_{ij}=0 \qquad \text{whenever} \qquad i>j+1.

Thus every upper triangular matrix is upper Hessenberg, but not every upper Hessenberg matrix is upper triangular.

The difference is small in structure but large in algorithmic value. Hessenberg form is easier to reach by orthogonal similarity than triangular form, and it keeps enough sparsity to accelerate QR iteration.

82.3 Why Hessenberg Form Appears

Eigenvalue algorithms use similarity transformations because similarity preserves eigenvalues.

H = Q^TAQ

where $Q$ is orthogonal, then $H$ and $A$ have the same eigenvalues. Hessenberg reduction seeks such a matrix $Q$ so that $H$ is upper Hessenberg:

Q^TAQ = H.

Equivalently,

A = QHQ^T.

The purpose is not to solve a linear system. The purpose is to prepare the matrix for eigenvalue iteration. Hessenberg form is the standard intermediate form between a dense matrix and Schur form.

82.4 Orthogonal Similarity

Hessenberg reduction is usually done by orthogonal similarity transformations.

A transformation

A \mapsto Q^TAQ

is called an orthogonal similarity transformation when

Q^TQ = I.

It preserves eigenvalues because

Q^TAQ

is similar to $A$ , with change of basis matrix $Q$ .

It also preserves numerical stability because orthogonal matrices preserve Euclidean length:

\|Qx\|_2 = \|x\|_2.

This matters in floating point arithmetic. A general similarity transformation can amplify error if the change-of-basis matrix is ill-conditioned. Orthogonal similarity avoids that source of instability.

82.5 Reduction by Householder Reflections

The standard dense method for reducing a general matrix to Hessenberg form uses Householder reflections.

A Householder reflection has the form

P = I - 2vv^T,

where

\|v\|_2 = 1.

It is symmetric and orthogonal:

P^T=P, \qquad P^TP=I.

At step $k$ , a Householder reflection is chosen to zero entries below the first subdiagonal in column $k$ . That is, it zeros the entries

a_{k+2,k}, a_{k+3,k}, \ldots, a_{n,k}.

The transformation is applied from both sides:

A \leftarrow P_k A P_k.

Applying it from the left creates zeros in a column. Applying it from the right preserves similarity and therefore preserves eigenvalues.

After $n-2$ such steps, the matrix is upper Hessenberg.

82.6 A Four by Four Pattern

For a $4 \times 4$ matrix,

$$ A = \begin{bmatrix}

& * & * & * \
& * & * & * \
& * & * & * \
& * & * & * \end{bmatrix}, $$

Hessenberg reduction aims for

$$ H = \begin{bmatrix}

& * & * & * \
& * & * & * \ 0 & * & * & * \ 0 & 0 & * & * \end{bmatrix}. $$

Only two entries are forced to zero below the first subdiagonal:

h_{31}=0, \qquad h_{41}=0, \qquad h_{42}=0.

For larger matrices, the same pattern continues. Column $1$ has zeros below row $2$ . Column $2$ has zeros below row $3$ . Column $3$ has zeros below row $4$ , and so on.

82.7 Example of Hessenberg Structure

The matrix

H = \begin{bmatrix} 4 & 1 & -2 & 3 \\ 2 & 5 & 0 & 1 \\ 0 & 7 & 6 & 8 \\ 0 & 0 & -3 & 2 \end{bmatrix}

is upper Hessenberg.

The entries below the first subdiagonal are

h_{31}, h_{41}, h_{42}.

They are all zero. The entries

h_{21}, h_{32}, h_{43}

are allowed to be nonzero.

By contrast,

\begin{bmatrix} 4 & 1 & -2 & 3 \\ 2 & 5 & 0 & 1 \\ 9 & 7 & 6 & 8 \\ 0 & 0 & -3 & 2 \end{bmatrix}

is not upper Hessenberg because the entry in position $(3,1)$ is nonzero.

82.8 Symmetric Matrices Become Tridiagonal

If $A$ is symmetric and $H=Q^TAQ$ , then $H$ is also symmetric:

H^T = (Q^TAQ)^T = Q^TA^TQ = Q^TAQ = H.

If $H$ is both symmetric and upper Hessenberg, then it must be tridiagonal.

A tridiagonal matrix has nonzero entries only on the main diagonal, the first subdiagonal, and the first superdiagonal:

T = \begin{bmatrix} d_1 & e_1 & 0 & \cdots & 0 \\ e_1 & d_2 & e_2 & \cdots & 0 \\ 0 & e_2 & d_3 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & e_{n-1} \\ 0 & 0 & 0 & e_{n-1} & d_n \end{bmatrix}.

Thus Hessenberg reduction specializes to tridiagonal reduction for symmetric matrices. This is a major simplification in symmetric eigenvalue problems.

82.9 Preservation under QR Iteration

The QR algorithm repeatedly factors a matrix as

A_k = Q_kR_k

and forms

A_{k+1} = R_kQ_k.

Since

A_{k+1}=Q_k^TA_kQ_k,

each step is an orthogonal similarity transformation and preserves eigenvalues.

If $A_k$ is upper Hessenberg, then $A_{k+1}$ is also upper Hessenberg. This preservation property is the main reason Hessenberg form is used before QR iteration.

Without Hessenberg form, each QR step on a dense matrix is expensive. With Hessenberg form, the structure limits the amount of fill-in and reduces the work per iteration.

82.10 Cost Advantage

For a dense $n \times n$ matrix, reducing the matrix to upper Hessenberg form costs on the order of

n^3

operations.

This is a one-time preprocessing cost.

After reduction, each QR iteration can be performed in

O(n^2)

operations rather than

O(n^3)

operations for a general dense matrix. This is the central computational advantage. The QR algorithm becomes practical because it works on the Hessenberg form instead of the original dense matrix.

82.11 Unreduced Hessenberg Matrices

An upper Hessenberg matrix is called unreduced if all its subdiagonal entries are nonzero:

h_{21}, h_{32}, \ldots, h_{n,n-1} \ne 0.

If some subdiagonal entry is zero, say

h_{k+1,k}=0,

then the matrix splits into block upper triangular form:

H = \begin{bmatrix} H_{11} & H_{12} \\ 0 & H_{22} \end{bmatrix}.

The eigenvalues of $H$ are then the eigenvalues of $H_{11}$ together with the eigenvalues of $H_{22}$ . The eigenvalue problem separates into smaller problems.

This splitting is called deflation in eigenvalue algorithms.

82.12 Deflation

Deflation occurs when a subdiagonal entry becomes zero or small enough to treat as zero.

Suppose

h_{k+1,k} \approx 0.

Then the matrix is nearly block upper triangular:

H \approx \begin{bmatrix} H_{11} & H_{12} \\ 0 & H_{22} \end{bmatrix}.

The QR algorithm can then continue separately on the diagonal blocks. This reduces the active problem size.

In practice, deflation is one of the mechanisms that makes QR eigenvalue computation efficient. The algorithm gradually drives subdiagonal entries toward zero, allowing eigenvalues or small blocks to split off.

82.13 Real Hessenberg Form and Complex Eigenvalues

A real upper Hessenberg matrix can have complex eigenvalues. Since the matrix entries remain real, complex eigenvalues appear in conjugate pairs.

In the real QR algorithm, convergence usually produces a real Schur form rather than a fully diagonal matrix. The final form contains $1 \times 1$ blocks for real eigenvalues and $2 \times 2$ blocks for complex conjugate pairs.

Hessenberg form is therefore an intermediate form. It is not the final eigenvalue form. It is the structured form from which the QR algorithm efficiently approaches Schur form.

82.14 Algorithm

The following high-level algorithm reduces a real square matrix to upper Hessenberg form.

hessenberg_reduction(A):
    n = number of rows of A
    Q = identity matrix of size n

    for k = 1 to n - 2:
        choose a Householder reflector Pk
        that zeros A[k+2:n, k]

        A = Pk A Pk
        Q = Q Pk

    H = A
    return Q, H

The result satisfies

H = Q^TAQ.

Equivalently,

A = QHQ^T.

In practical implementations, the full Householder matrices $P_k$ are not formed explicitly. Their defining vectors are stored compactly and applied to the relevant submatrices.

82.15 Storage in Practice

Dense Hessenberg reduction commonly overwrites the original matrix.

The upper Hessenberg part stores $H$ . The Householder vectors used to construct $Q$ may be stored in the entries below the first subdiagonal, since those entries are zero in $H$ .

Object	Practical storage
$H$	Upper Hessenberg part of the array
Householder vectors	Strictly lower unused region
$Q$	Stored implicitly
Eigenvalues	Later extracted from Schur form

This is similar in spirit to Householder QR storage. The orthogonal transformations are stored implicitly unless the explicit matrix $Q$ is needed.

82.16 Hessenberg Form and Krylov Subspaces

Hessenberg matrices also appear in Krylov subspace methods.

Given a matrix $A$ and a vector $b$ , the Krylov subspace of order $k$ is

\mathcal{K}_k(A,b) = \operatorname{span} \{b, Ab, A^2b, \ldots, A^{k-1}b\}.

Arnoldi iteration constructs an orthonormal basis

q_1,\ldots,q_k

for this subspace. In that basis, the projected action of $A$ is represented by an upper Hessenberg matrix:

AQ_k = Q_{k+1}\overline{H}_k.

The Hessenberg matrix $\overline{H}_k$ is small compared with $A$ . It captures how $A$ acts on the Krylov basis. This is the foundation for many iterative eigenvalue and linear system methods.

82.17 Arnoldi Hessenberg Matrix

In Arnoldi iteration, each new vector is obtained by applying $A$ to the current basis vector and then orthogonalizing against previous basis vectors.

The recurrence has the form

Aq_j = h_{1j}q_1 + h_{2j}q_2 + \cdots + h_{j+1,j}q_{j+1}.

Only basis vectors up to $q_{j+1}$ appear. This is why the coefficient matrix is upper Hessenberg.

The Hessenberg structure encodes the short upper limit in the recurrence. It records that the $j$ -th image $Aq_j$ may create one new direction, but no more than one.

82.18 Comparison with Other Forms

Form	Pattern	Main use
Upper triangular	Zeros below diagonal	Schur form, triangular solves
Upper Hessenberg	Zeros below first subdiagonal	General eigenvalue computation
Tridiagonal	Zeros outside three diagonals	Symmetric eigenvalue computation
Bidiagonal	Nonzeros on main and one adjacent diagonal	Singular value computation
Diagonal	Nonzeros only on main diagonal	Fully decoupled action

Hessenberg form is a compromise. It is more structured than a dense matrix but less restrictive than triangular form. That compromise makes it reachable by stable transformations and useful for iterative eigenvalue algorithms.

82.19 Common Pitfalls

A Hessenberg matrix should not be confused with a triangular matrix. The first subdiagonal is allowed to contain nonzero entries.

Hessenberg reduction should also not be confused with Gaussian elimination. Gaussian elimination uses row operations and changes the eigenvalues in general. Hessenberg reduction uses similarity transformations and preserves eigenvalues.

Finally, Hessenberg form does not usually reveal eigenvalues directly. It prepares the matrix for QR iteration. The eigenvalues are obtained after further reduction toward Schur form.

82.20 Summary

An upper Hessenberg matrix has zeros below the first subdiagonal:

h_{ij}=0 \qquad \text{for} \qquad i>j+1.

Every square matrix can be reduced to upper Hessenberg form by orthogonal similarity transformations:

H = Q^TAQ.

This reduction preserves eigenvalues and improves numerical behavior. Its main use is as a preprocessing step for the QR algorithm. Since QR iteration preserves Hessenberg structure, each iteration becomes much cheaper than it would be on a dense matrix.

For symmetric matrices, Hessenberg form becomes tridiagonal form. In Krylov methods, Hessenberg matrices arise naturally from Arnoldi iteration. Thus Hessenberg form connects direct eigenvalue algorithms, iterative methods, and the structural theory of matrix computation.