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: v3 · 2026-09-19 · History
Domain-specific #: 1999
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomain: Numerical Linear Algebra → Mathematics
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.

How would you explain it like I'm…

Staircase-Plus-One Grid

A Hessenberg matrix is a square grid of numbers where almost everything in the bottom corner is zero. Picture a staircase from the top-left corner to the bottom-right corner. Numbers can sit on the staircase, above it, and on one step just below it. Everything further down is zero.

Almost-Triangle Number Table

A matrix is a square grid of numbers. In an upper Hessenberg matrix, every number far below the main diagonal must be zero. The only numbers allowed below the diagonal are those in the row of spots right next to it. Mathematicians like this shape because a messy matrix can be rearranged into it without changing certain important numbers it holds. Those numbers are the eigenvalues, and this shape makes them faster to compute.

One-Subdiagonal Triangular Matrix

An upper Hessenberg matrix is a square matrix whose entry h_ij is zero whenever i > j+1. It is like an upper triangular matrix, except the first subdiagonal (the line just below the main diagonal) is allowed to be nonzero. A lower Hessenberg matrix is the transposed version. Any square matrix, even a non-symmetric one, can be converted to Hessenberg form by a stable orthogonal or unitary similarity transformation, which keeps its eigenvalues unchanged. That makes it a standard first step before iterative eigenvalue algorithms like QR. If any subdiagonal entry is zero, the problem splits into smaller independent pieces; if none are, the matrix is called unreduced.

A square matrix H is upper Hessenberg if h_ij = 0 for all i > j+1. That means it is triangular except for a single nonzero band on the first subdiagonal. Lower Hessenberg is the transpose pattern, with zeros wherever j > i+1. Every nonsymmetric matrix can be reduced to Hessenberg form by stable orthogonal or unitary similarity, for example using Householder reflections. This is the narrowest general form reachable that way before iterative eigenvalue computation begins. Because it is a similarity transformation, the eigenvalues are preserved. The zero structure makes each QR iteration economical. H is called unreduced if every subdiagonal entry h_{i+1,i} is nonzero. If one of those entries is zero, the eigenvalue problem splits into smaller independent 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.

This entry is a kind of Matrix.

Matrix is the broader abstraction it instantiates within its own domain. Canonical Form, Transformation, Invariance, Decomposition, Sparsity, and Iteration are related abstractions.

Relationships to Other Abstractions¶

Current abstraction Hessenberg Matrix Domain-specific

Parents (1) — outgoing typed relations

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 → is a kind of Matrix → is a kind of, conditional Tensor → presupposes Transformation → is a kind of, typical Function (Mapping)

Show alternative paths (4)

Neighborhood in Abstraction Space¶

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

Family — Matrix Structures & Matroids (11 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25

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 ↩ Show verification details

[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 ↩ Show verification details

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