Hessenberg Matrix¶

Constrain a square matrix to be triangular except for one adjacent off-diagonal band, yielding a similarity-reachable form that preserves eigenvalues while making QR iteration and related computations substantially cheaper.

Version: v2 · 2026-09-06 · History
Domain-specific #: 1999
Origin domain: mathematics
Subdomain: numerical linear algebra
Aliases: Upper Hessenberg matrix, Lower Hessenberg matrix, Hessenberg form

Core Idea¶

An upper Hessenberg matrix is a square matrix \(H=(h_{ij})\) with \(h_{ij}=0\) whenever \(i>j+1\): it is upper triangular except that the first subdiagonal may be nonzero. A lower Hessenberg matrix is its transposed orientation, with zeros whenever \(j>i+1\). This one-band allowance is the narrowest general form to which an arbitrary nonsymmetric matrix can be reduced by stable orthogonal or unitary similarity before iterative eigenvalue computation.^[1]

The form preserves the eigenvalues of the original matrix while exposing enough zero structure to make subsequent QR steps economical. It is unreduced when every permitted adjacent off-diagonal entry is nonzero; a zero there splits the eigenvalue problem into smaller blocks.

Structural Signature¶

A square matrix over the real or complex numbers, or a stated compatible field.
An orientation: upper or lower Hessenberg.
A strict support rule with zeros beyond one neighboring off-diagonal.
A free main triangle and one permitted adjacent band.
A reduced/unreduced distinction based on the adjacent band.
A unitary or orthogonal similarity relation to an input matrix.
Preservation of characteristic polynomial and eigenvalues.
A finite reduction by Householder reflectors or Givens rotations.
Compact storage of the structured entries and optional reflector data.
Fast matrix operations that preserve the band pattern.
Deflation when an adjacent-band entry becomes zero or negligible.
A route from general matrix to Hessenberg form to Schur or triangular form.

What It Is Not¶

It is not necessarily triangular, banded on both sides, symmetric, normal, or sparse in every region. A tridiagonal matrix is Hessenberg in both orientations and is more restrictive. Hessenberg reduction is not diagonalization and does not by itself compute eigenvalues. “Unreduced” does not mean that no transformation has been applied; it means the permitted adjacent band has no zeros.

Scope of Application¶

Hessenberg form is central to nonsymmetric eigenvalue algorithms. General matrices are first reduced by orthogonal or unitary similarity; implicit shifted QR iterations then preserve the form while driving subdiagonal entries toward deflation. Householder established unitary triangularization machinery that underlies stable reductions.^[2] Francis's implicit QR work made the two-stage reduction-and-iteration architecture computationally decisive.^[3]

The form also appears in Krylov methods, companion matrices, control computations, and structured determinant or recurrence problems.

Clarity¶

Always state upper or lower orientation, indexing convention, scalar field, and whether the matrix is unreduced. Separate the matrix property from the algorithm that produces it. When numerical deflation is claimed, state the tolerance and scaling rule: a tiny computed subdiagonal is not mathematically zero without a declared criterion.

Manages Complexity¶

The form concentrates fill into one triangle plus one band. Similarity reduction pays a one-time cubic cost, after which repeated QR steps can exploit the structure rather than operating on a dense general matrix. The adjacent band also exposes block splits immediately, turning one large eigenproblem into independent smaller ones.

Abstract Reasoning¶

Confirm the input is square.
Choose upper or lower Hessenberg orientation.
Construct orthogonal or unitary transformations that annihilate forbidden entries column by column or row by row.
Apply each transformation on both sides to preserve similarity.
Store the resulting Hessenberg matrix and, if needed, the accumulated basis change.
Verify the zero pattern and backward stability.
Run structure-preserving shifted QR steps.
Deflate at zero or safely negligible adjacent-band entries.
Recover Schur vectors or eigenvectors through the stored transformations when required.

LAPACK's xGEHRD routines formalize the reflector-based reduction interface used by numerical software.^[4]

Knowledge Transfer¶

The portable pattern is transform a dense object into the least restrictive near-terminal form that preserves the invariant of interest, then exploit that form across many later iterations. The proposed immediate parent is Matrix.

Examples¶

Every upper triangular matrix is upper Hessenberg. A symmetric upper Hessenberg matrix must be tridiagonal because symmetry mirrors the single subdiagonal into a single superdiagonal. A companion matrix is commonly Hessenberg and makes polynomial roots into matrix eigenvalues.

If \(h_{k+1,k}=0\) in an upper Hessenberg matrix, the leading \(k\)-by-\(k\) block separates from the trailing block for eigenvalue purposes.

Structural Tensions¶

Dense similarity invariance versus sparse support.
One-time reduction cost versus repeated-iteration savings.
Exact zero structure versus floating-point deflation.
General nonsymmetry versus triangular endpoint.
Accumulating transformations versus minimizing memory.

Structural–Framed Character¶

Invariant-preserving simplification is structural. Matrix indices, diagonals, similarity, eigenvalues, reflectors, and QR iteration are constitutive. The abstraction is domain-specific.

Structural Core vs. Domain Accent¶

The structural core is invariant-preserving change of basis -> almost-terminal sparse form -> cheaper repeated refinement. The domain accent is one-band almost-triangular matrix structure.

Matrix is the proposed immediate domain-specific parent. Canonical Form, Transformation, Invariance, Decomposition, Sparsity, and Iteration are related primes.

The prospective queue contains one strict edge to domain_specific:matrix. No live DAG mutation is authorized.

Relationships to Other Abstractions¶

Current abstraction Hessenberg Matrix Domain-specific

Parents (1) — more general patterns this builds on

Hessenberg Matrix is a kind of Matrix Domain-specific

Matrix is the proposed immediate domain-specific parent.

Hierarchy paths (5) — routes to 5 parentless roots

Hessenberg Matrix → Matrix → Tensor → Transformation → Function (Mapping)

Show alternative paths (4)

Neighborhood in Abstraction Space¶

Hessenberg Matrix sits in a sparse region of the domain-specific corpus (90^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (1565 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With¶

A triangular matrix.
A tridiagonal matrix.
Hermite normal form.
Hessenberg reduction as an eigenvalue answer.
The QR algorithm that consumes Hessenberg form.
Numerical near-zero treated as exact zero without a criterion.

References¶

[1] Gene H. Golub and Charles F. Van Loan, Matrix Computations, 4^th ed. (Johns Hopkins University Press, 2013), chapters 7–8. registry ↩

[2] Alston S. Householder, “Unitary Triangularization of a Nonsymmetric Matrix,” Journal of the ACM 5, no. 4 (1958): 339–342, doi:10.1145/320941.320947. registry ↩

[3] J. G. F. Francis, “The QR Transformation: A Unitary Analogue to the LR Transformation—Part 1,” The Computer Journal 4, no. 3 (1961): 265–271, doi:10.1093/comjnl/4.3.265. registry ↩

[4] E. Anderson et al., LAPACK Users' Guide, 3^rd ed. (SIAM, 1999), doi:10.1137/1.9780898719604. registry ↩