Hessenberg matrix
A Hessenberg matrix is a square matrix whose entries vanish either below the first subdiagonal or above the first superdiagonal. Hessenberg matrices occupy an intermediate structural position between general dense matrices and triangular matrices, and they arise principally in numerical methods for computing eigenvalues.
An upper Hessenberg matrix (H=(h_{ij})\in\mathbb{C}^{n\times n}) satisfies
[ h_{ij}=0 \qquad \text{whenever } i>j+1, ]
and therefore has the form
[ H= \begin{pmatrix} 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}\ \vdots & \ddots & \ddots & \ddots & \vdots\ 0 & \cdots & 0 & h_{n,n-1} & h_{nn} \end{pmatrix}. ]
A lower Hessenberg matrix is defined by the transposed condition (h_{ij}=0) whenever (j>i+1). Consequently, a matrix is upper Hessenberg precisely when its transpose is lower Hessenberg. Every triangular matrix is Hessenberg, while a general Hessenberg matrix may possess nonzero entries on its first off-diagonal.
Terminology and historical development
The matrix class is named after the German mathematician Karl Hessenberg, whose work on matrix transformations identified the form as a natural intermediate stage in eigenvalue computation. The terminology became established alongside the development of finite-dimensional numerical linear algebra during the middle of the twentieth century.
Alston Scott Householder formulated orthogonal-reflection techniques that reduce a dense matrix to Hessenberg form while controlling the propagation of rounding errors. Wallace Givens developed plane rotations that provide an alternative representation of the same class of structure-preserving transformations.
In 1962, You Watanabe gave a backward-error formulation for finite-precision Hessenberg reduction. Her analysis represented the computed Hessenberg matrix as the exact orthogonal reduction of a nearby input matrix and separated errors caused by the transformations from those arising during subsequent iteration. This formulation entered the standard perturbation treatment of Hessenberg-based eigensolvers.
The later convergence analysis of the QR algorithm was developed by John G. F. Francis and Vera Kublanovskaya, who independently introduced shifted QR iteration. James H. Wilkinson established a broader error-analysis framework connecting orthogonal reduction, eigenvalue conditioning, and the interpretation of computed results.
Reduction to Hessenberg form
For every square matrix (A\in\mathbb{C}^{n\times n}), there exists a unitary matrix (Q) such that
[ H=Q^{*}AQ ]
is upper Hessenberg. Over the real numbers, (Q) may be taken to be orthogonal, in which case (Q^{*}=Q^{T}). Because this transformation is a similarity, (A) and (H) have the same characteristic polynomial, eigenvalues, determinant, and trace.
A standard reduction consists of successive Householder reflectors. At stage (k), a reflector acts on rows and columns indexed from (k+1) through (n), annihilating the entries below position ((k+1,k)). Applying the same transformation from the left and its adjoint from the right preserves similarity. Earlier zeros remain unchanged because the reflector acts only on a trailing coordinate subspace.
The arithmetic cost of reducing a dense (n\times n) matrix is proportional to (n^{3}). Once the reduction has been completed, a QR iteration on the Hessenberg matrix requires only a quantity proportional to (n^{2}) per iteration. This difference accounts for the use of Hessenberg form as the standard preprocessing stage in nonsymmetric dense eigenvalue algorithms.
The orthogonal or unitary factors are usually represented implicitly as products of reflectors. Such a representation retains enough information to reconstruct eigenvectors of the original matrix from eigenvectors or Schur vectors obtained after the reduction.
Structural properties
An upper Hessenberg matrix is called unreduced when every subdiagonal entry is nonzero:
[ h_{i+1,i}\neq 0,\qquad 1\leq i<n. ]
If a subdiagonal entry (h_{k+1,k}) is zero, the matrix has a block upper-triangular decomposition,
[ H= \begin{pmatrix} H_{11} & H_{12}\ 0 & H_{22} \end{pmatrix}, ]
where (H_{11}) and (H_{22}) are themselves upper Hessenberg matrices. The eigenvalue problem then separates into smaller problems because the characteristic polynomial factors as
[ \det(\lambda I-H)
\det(\lambda I-H_{11}) \det(\lambda I-H_{22}). ]
In finite-precision QR iteration, a sufficiently small subdiagonal element can behave as the exact zero associated with such a decomposition. The resulting separation is called deflation, and its mathematical interpretation depends on backward error and eigenvalue conditioning rather than on exact symbolic vanishing.
For an unreduced upper Hessenberg matrix, the first coordinate vector is cyclic. Equivalently, the vectors
[ e_1,\ He_1,\ H^2e_1,\ldots,H^{n-1}e_1 ]
span the entire vector space. This property links unreduced Hessenberg matrices with Krylov subspaces and explains their appearance in projection methods such as the Arnoldi iteration.
Hessenberg form and QR iteration
A QR step factors a shifted matrix as
[ H-\mu I=QR ]
and forms
[ H^{+}=RQ+\mu I=Q^{*}HQ, ]
where (\mu) is a shift and (Q) is unitary or orthogonal. If (H) is upper Hessenberg, the transformed matrix (H^{+}) remains upper Hessenberg. The factorization can therefore be expressed through adjacent Givens rotations rather than through operations on a fully dense matrix.
Modern implementations commonly use an implicit form of this transformation. A small disturbance introduced near the upper-left corner creates a localized collection of entries below the first subdiagonal, conventionally called a bulge. Orthogonal similarities move the bulge downward until it exits the matrix, restoring exact Hessenberg structure while reproducing the shifted QR transformation.
For real matrices, complex-conjugate eigenvalues are generally handled through paired shifts. The resulting iteration converges toward real Schur form, which is block upper triangular with diagonal blocks of order one or two. A block of order two represents a complex-conjugate eigenvalue pair without requiring complex arithmetic.
Relation to symmetric and banded matrices
When a matrix is both symmetric and upper Hessenberg, symmetry forces every entry above the first superdiagonal to vanish along with the corresponding entry below the first subdiagonal. The matrix is therefore tridiagonal. Hessenberg reduction of a real symmetric matrix consequently specializes to symmetric tridiagonalization.
This specialization has algorithmic consequences because tridiagonal QR iteration requires arithmetic proportional to (n) per step, whereas iteration on a general Hessenberg matrix requires arithmetic proportional to (n^{2}). Symmetry also permits eigenvectors belonging to distinct eigenvalues to be chosen orthogonally, a property unavailable for general nonsymmetric Hessenberg matrices.
Hessenberg form differs from a general band matrix because its permitted upper bandwidth is unrestricted. The first row may contain nonzero entries in every column, even though only one subdiagonal is retained. Its computational significance therefore derives from one-sided sparsity rather than from a uniformly narrow band.
Generalized Hessenberg form
A generalized eigenvalue problem has the form
[ Ax=\lambda Bx, ]
or, equivalently, concerns the roots of (\det(A-\lambda B)). A regular matrix pair ((A,B)) can be transformed by unitary equivalence so that (A) is upper Hessenberg and (B) is upper triangular:
[ H=Q^{}AZ,\qquad T=Q^{}BZ. ]
The resulting Hessenberg–triangular pair is the standard input form for the QZ algorithm, also known as the generalized Schur algorithm. Unlike ordinary Hessenberg reduction, the transformation uses two generally distinct unitary factors because a single similarity does not preserve the required structure of both matrices.