1 Definition and basic properties

A square matrix \(A\in\mathbb{C}^{n\times n}\) is said to be in Hessenberg form if entries strictly below a chosen subdiagonal are zero. In the common convention used in numerical linear algebra, the matrix is upper Hessenberg when \(a_{ij}=0\) for \(i>j+1\). Equivalently, all nonzero elements can occur on the main diagonal, the first superdiagonal, and the first subdiagonal, while everything further below the first subdiagonal vanishes.

Hessenberg form is useful because it retains essential spectral features of the original matrix while introducing a structured sparsity pattern that makes subsequent computations cheaper and more stable.

1.1 Upper vs. lower Hessenberg forms

An upper Hessenberg matrix has the sparsity constraint \(a_{ij}=0\) whenever \(i>j+1\). A lower Hessenberg matrix instead enforces \(a_{ij}=0\) whenever \(j>i+1\), producing a mirrored pattern of allowable fill.

Both versions are related by transposition and complex conjugation; for example, the conjugate transpose of an upper Hessenberg matrix is lower Hessenberg.

1.2 Similarity transformations and invariance of eigenvalues

If \(H\) is obtained from \(A\) via a similarity transformation \(H = Q^{*}AQ\) with \(Q\) unitary (or orthogonal in the real case), then \(A\) and \(H\) share the same eigenvalues (including algebraic multiplicities). This invariance under similarity is the core reason Hessenberg reduction is a standard preprocessing step for eigenvalue algorithms.

Moreover, when \(A\) is diagonalizable, the eigenvectors of \(H\) can be mapped back to eigenvectors of \(A\) through the same transformation matrix \(Q\), providing a practical route to recovering eigenvectors after the structured reduction.

1.3 Sparsity pattern and degrees of freedom

The defining sparsity pattern constrains where nonzeros may appear. For upper Hessenberg matrices, the potentially nonzero entries lie in positions \((i,j)\) with \(j\ge i-1\). Counting these positions gives a total of \[ \#\text{possible nonzeros} = \sum_{j=1}^{n} \min(n,\,j+1) = \frac{n(n+1)}{2} + (n-1) = \frac{n^2+3n-2}{2}, \] which is substantially less than the \(n^2\) entries of a dense matrix.

This reduction in degrees of freedom is what enables algorithms with lower operation counts and improved memory locality.

2 Relationship to other matrix classes

Hessenberg form sits in a family of structured matrix representations. Its pattern is less restrictive than tridiagonal form but more structured than general dense matrices, creating a useful compromise for eigenvalue computations.

2.1 Connection to triangular and banded matrices

A triangular matrix is a special case of Hessenberg form because strict triangularity implies additional zeros beyond the first subdiagonal. Likewise, Hessenberg matrices are banded with bandwidth two in the sense that only a narrow neighborhood around the diagonal contains potentially nonzero entries (specifically, the main diagonal and the first sub/superdiagonal).

In numerical practice, banded structures can often be exploited directly in algorithms; Hessenberg form provides a related advantage without requiring the matrix to be originally banded.

2.2 Relation to bidiagonal, tridiagonal, and companion-like forms

While Hessenberg form has zeros below the first subdiagonal, tridiagonal matrices have zeros except on the main diagonal and the first super/subdiagonals. Many eigensolvers first reduce a general matrix to Hessenberg form and then further to tridiagonal form under additional symmetry constraints.

Bidiagonal forms arise naturally in singular value problems and certain reduction chains. Hessenberg reduction is conceptually aligned with these chains: a general matrix is transformed by structured orthogonal/unitary transformations into a simpler canonical-like sparse form suited to the targeted problem.

Companion-like forms (used in polynomial eigenvalue formulations and related contexts) can resemble Hessenberg patterns. Although they arise from different derivations, both exploit near-diagonal sparsity to facilitate iterative and direct methods.

2.3 Normal, symmetric, and Hermitian special cases

For normal matrices, eigenvectors can be chosen to form an orthonormal basis, and eigenvalue algorithms may have additional simplifications. For Hermitian (or real symmetric) matrices, the Hessenberg form can be reduced further to tridiagonal form while preserving symmetry, which enables faster and often more accurate eigensolvers.

In contrast, for a general nonnormal matrix, Hessenberg reduction does not impose symmetry, so the subsequent eigenvalue computation must typically account for non-normal behavior (for example, sensitivity of eigenvectors).

3 Algorithms for computing Hessenberg form

Hessenberg reduction is normally computed using orthogonal/unitary similarity transformations that preserve conditioning properties associated with norm-based measures. The transformations are designed to be cheap to apply and to introduce zeros systematically.

3.1 Orthogonal similarity transformations (general idea)

The central idea is to find a unitary \(Q\) such that \(H = Q^{*}AQ\) has zeros below the first subdiagonal. This is achieved by applying transformations that act nontrivially only on trailing subspaces.

Because \(Q\) is orthogonal/unitary, it does not amplify Euclidean norms, which supports numerical stability and allows residual-based stopping criteria to be reliable.

3.2 Householder reflections approach

Householder reflections are popular because they can annihilate multiple elements in a column or row using one structured reflector.

3.2.1 Bulge introduction and elimination

A typical Hessenberg reduction step targets entries below the first subdiagonal in a selected column. Applying a Householder reflector from the left can eliminate elements in that column but may introduce nonzeros in positions that were previously zero due to the right-side application needed to maintain similarity.

This phenomenon is sometimes described as creating a “bulge”: sparsity is temporarily disturbed in a small neighborhood. A complementary reflector applied from the right (or from the left in a subsequent stage) then eliminates the bulge and restores the intended Hessenberg structure. Repeating this process across columns progressively enforces the global sparsity pattern.

3.2.2 Accumulation of transformations (forming \(Q\))

If eigenvectors are desired, the reduction must record the cumulative transformation matrix \(Q\). In practice, \(Q\) is rarely formed as a dense matrix. Instead, the algorithm stores the Householder vectors (and scalar factors) and later applies them as needed.

When only eigenvalues are sought, implementations may avoid explicit accumulation to reduce memory traffic. When eigenvectors are required, the stored reflectors are used in a backtransformation phase after the eigenvalues (or Schur form) are computed.

3.3 Givens rotation approach

Givens rotations apply a planar rotation to eliminate specific entries while changing only two rows (or columns) at a time.

3.3.1 Numerical considerations and stability

Givens rotations are also orthogonal/unitary and thus are norm-preserving. They can be advantageous in situations where sparse structure or incremental updates are important, since each rotation affects a limited region and can be applied efficiently.

However, relative to Householder-based methods, using many Givens rotations may lead to higher overhead for dense matrices because each rotation is a finer-grained operation.

3.3.2 When to prefer Givens over Householder

Givens-based reduction may be preferred when:

  • the matrix is extremely sparse and preserving sparsity during reduction is critical,
  • one wants fine-grained control over fill-in,
  • or the environment favors a pipeline of short operations.

For typical dense problems, Householder reflections remain the standard choice due to favorable operation counts and good cache performance.

4 Exact arithmetic versus floating-point behavior

Hessenberg reduction is typically stable in floating-point arithmetic when implemented with orthogonal/unitary transformations. Nonetheless, numerical behavior depends on details such as update order, scaling, and the presence of near-zero elements.

4.1 Numerical stability considerations

Because each step uses orthogonal/unitary transformations, the computed Hessenberg form tends to incur errors that are well behaved under backward error interpretations. The reduction is often viewed as producing a nearby exact Hessenberg matrix to what would be obtained in exact arithmetic.

Stability also relates to how reflectors and rotations are applied: algorithms are designed to minimize cancellation and avoid subtracting nearly equal quantities in critical places.

4.2 Conditioning and error propagation

Even if the reduction itself is stable, subsequent eigenvalue steps can be influenced by the conditioning of the eigenvalues and eigenvectors of the original matrix. Nonnormality can cause eigenvectors to be sensitive, meaning that small perturbations can lead to noticeable changes in eigenvector directions while eigenvalues remain relatively stable.

Error propagation through the eigenvalue algorithm therefore depends not only on reduction accuracy but also on properties of the Hessenberg matrix, such as how well it supports the convergence of iterative schemes.

4.3 Computational complexity and operation counts

For dense matrices, Hessenberg reduction using Householder reflections has cubic-time complexity, typically on the order of \(O(n^{3})\) operations, though with a relatively small constant compared with many alternative preprocessing methods.

While this cost is significant, it is amortized by the fact that eigenvalue algorithms for Hessenberg matrices are much cheaper than those for fully dense matrices.

Hessenberg form is widely used as an intermediate representation for computing eigenvalues and, in many settings, the Schur form.

5.1 Why Hessenberg form accelerates eigenvalue computations

Many eigenvalue algorithms exploit the sparse structure of a Hessenberg matrix to reduce the cost of matrix-vector products, QR factorizations, and related updates. Operations that would otherwise involve the entire dense matrix become localized to a narrow band around the diagonal and a small set of auxiliary vectors.

This localization reduces both arithmetic complexity and memory movement, which is often the dominant cost in practice for large problems.

5.2 Implicit QR iteration on Hessenberg matrices

Implicit QR iteration is a key method for eigenvalues. Starting from a Hessenberg matrix \(H\), the algorithm performs a QR step without explicitly forming the full QR factors. The Hessenberg structure ensures that the QR step can be carried out efficiently using Givens rotations or bulge-chasing-like procedures.

A single QR iteration transforms the matrix while preserving the Hessenberg structure, keeping the computational workload manageable over repeated iterations.

5.3 Shift strategies and convergence behavior

Shifts are used to accelerate convergence by targeting specific parts of the spectrum. Common strategies choose a scalar shift (or sometimes more structured shifts) at each iteration so that trailing submatrices become closer to triangular form.

The convergence rate depends on the separation of eigenvalues and on how nonnormal the matrix is. For well-separated eigenvalues and appropriate shifts, convergence can be rapid; otherwise, convergence may be slower and may require careful selection of shifts.

5.4 Backtransformation and recovering eigenvectors

If eigenvectors or eigenvectors of the Schur form are required, the transformations from the Hessenberg reduction must be included. Since \(H = Q^{*}AQ\), eigenvectors \(y\) of \(H\) correspond to eigenvectors \(x = Qy\) of \(A\).

In practice, the backtransformation is performed by applying the stored reflectors or rotation sequences to the computed eigenvector vectors, typically using stable application of orthogonal/unitary factors.

6 Practical considerations in implementations

Efficient and correct implementations depend on careful handling of storage, transformation accumulation, and convergence checks.

6.1 Storage schemes for Hessenberg matrices

A Hessenberg matrix stores only the relevant band (plus the main diagonal) when memory is a concern. Even in dense storage, updates can be written to touch only the parts permitted by the sparsity pattern.

For algorithms that repeatedly access matrix elements along a narrow band, using a storage layout that aligns with column-major or row-major access patterns can improve performance.

6.2 Handling unitary/orthogonal accumulation

When forming \(Q\) explicitly is too expensive, implementations store compact representations:

  • Householder vectors with their corresponding coefficients,
  • or rotation parameters for Givens sequences.

Applying these transformations later is typically done via blocked operations to exploit level-3 BLAS routines where available, improving throughput on modern hardware.

6.3 Stopping criteria and residual checks

Eigenvalue iterations are typically terminated using criteria based on the size of subdiagonal entries (for Schur or quasi-triangular outputs) or on normwise residuals for computed eigenpairs.

Residual checks are important because eigenvalue convergence does not always guarantee that eigenvectors have converged to the desired accuracy, especially in the presence of nonnormality.

6.4 Performance considerations for large dense problems

For large dense matrices, performance is dominated by:

  • the cost of the initial reduction,
  • the number of QR iterations required,
  • and memory bandwidth and cache efficiency.

Block algorithms and careful ordering of updates can substantially reduce runtime. Additionally, using fused operations and minimizing data movement can improve scalability.

7 Variants and extensions

Hessenberg reduction generalizes in several directions, including structured matrices, generalized eigenvalue problems, and broader “almost banded” notions.

7.1 Hessenberg reduction for structured matrices

When \(A\) has additional structure (e.g., symmetry, sparsity patterns, or bandedness), reduction can be adapted:

  • exploiting symmetry to produce tridiagonal-like outcomes,
  • preserving sparsity more effectively when the structure is compatible with the annihilation pattern,
  • or using specialized kernels that reduce operation count.

These variants aim to keep the computational benefit of Hessenberg form while aligning with the matrix’s inherent properties.

7.2 Quasi-Hessenberg and generalized Hessenberg notions

Some algorithms use weaker sparsity patterns than strict Hessenberg form, producing matrices that are “almost” Hessenberg with small additional nonzeros. Such variants can arise from approximations, block reductions, or iterative schemes that maintain structure only up to a controllable tolerance.

The defining objective remains: obtain a representation where key eigenvalue operations are still efficient and stable.

7.3 Hessenberg pencils and generalized eigenvalue problems

In generalized eigenvalue problems of the form \[ A x = \lambda B x, \] where \(A\) and \(B\) are square matrices, one can reduce the pair \((A,B)\) to canonical structures via simultaneous transformations. Hessenberg-like pencils are used to localize the generalized eigenvalue computations, enabling efficient iterative methods and Schur-type decompositions.

This extension is important in applications where the eigenvalue problem naturally arises from constrained systems or linearizations of matrix polynomials.

8 Examples and worked transformations

Concrete examples help illustrate how Hessenberg reduction creates zeros systematically and how the resulting sparsity pattern can be verified.

8.1 Step-by-step reduction of a small dense matrix

Consider a small \(4\times 4\) dense matrix \(A\). A standard Hessenberg reduction proceeds as follows:

  1. Use a Householder reflector to eliminate entries in column 1 below row 2 in \(Q^{*}AQ\).
  2. Apply a second transformation (often from the right in a similarity update) to maintain similarity while controlling where new nonzeros appear.
  3. Repeat the process for column 2 to eliminate entries below the first subdiagonal in that column.
  4. Finish with the last step needed to ensure zeros below the first subdiagonal across all columns.

The end product is an upper Hessenberg matrix \(H\) such that \(H=Q^{*}AQ\) with \(Q\) unitary/orthogonal.

8.2 Interpreting the resulting sparsity pattern

After reduction, nonzero elements appear only in allowed positions: the main diagonal, the first superdiagonal, and the first subdiagonal. In the \(4\times4\) case, this means the matrix has the form \[ \begin{pmatrix} * & * & * & *\\ * & * & * & *\\ 0 & * & * & *\\ 0 & 0 & * & * \end{pmatrix}, \] where “\(*\)” denotes potentially nonzero entries and explicit zeros correspond to eliminated elements. The emergence of this pattern confirms that the reduction followed the Hessenberg constraints.

8.3 Verifying similarity (sanity checks)

To verify the similarity numerically, one can check:

  • normwise closeness of \(Q^{*}AQ\) to the computed \(H\),
- orthogonality/unitarity of \(Q\) via \(\|Q^{*}Q-I\|\),
  • equality of eigenvalues between \(A\) and \(H\) within floating-point tolerances.

These checks provide a practical confirmation that the reduction implemented the intended orthogonal/unitary similarity transformation and produced a valid Hessenberg form.