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.

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.

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. Francis's implicit QR work made the two-stage reduction-and-iteration architecture computationally decisive.

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

1. Confirm the input is square.
2. Choose upper or lower Hessenberg orientation.
3. Construct orthogonal or unitary transformations that annihilate forbidden entries column by column or row by row.
4. Apply each transformation on both sides to preserve similarity.
5. Store the resulting Hessenberg matrix and, if needed, the accumulated basis change.
6. Verify the zero pattern and backward stability.
7. Run structure-preserving shifted QR steps.

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.

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

• Nonnegative Matrix — 0.80
• Bidiagonal matrix — 0.80
• Pentadiagonal Matrix — 0.79
• Schur decomposition — 0.79
• QR Algorithm — 0.78

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