Month: December 2023

What Is a Hessenberg Matrix?

An n\times n upper Hessenberg matrix H has the property that h_{ij} = 0 for i>j+1. For n=4, the structure is

\notag H = \begin{bmatrix} \times & \times & \times & \times \\ \times & \times & \times & \times \\ 0 & \times & \times & \times \\ 0 & 0 & \times & \times \end{bmatrix}.

H is an upper triangular matrix with an extra subdiagonal.

A lower Hessenberg matrix H is the transpose of an upper Hessenberg matrix. In the rest of this article, the Hessenberg matrices are upper Hessenberg.

Hessenberg matrices play a key role in the QR algorithm for computing the eigenvalues of a general matrix. The first step of the algorithm is to reduce A to Hessenberg form by unitary Householder transformations and then carry out the QR iteration on the Hessenberg form.

Because H is so close to being triangular, its LU factorization and QR factorization can both be computed in O(n^2) flops. For example, the first stage of LU factorization needs to eliminate just one element, by adding a multiple of row 1 to row 2 (assuming h_{11}\ne 0):

\notag H = \begin{bmatrix} \times & \times & \times & \times \\ \times & \times & \times & \times \\ 0 & \times & \times & \times \\ 0 & 0 & \times & \times \end{bmatrix} \quad \to \quad \begin{bmatrix} \times & \times & \times & \times \\ \fbox{0} & \times & \times & \times \\ 0 & \times & \times & \times \\ 0 & 0 & \times & \times \end{bmatrix}.

Partial pivoting can be used and adds no extra flops. For QR factorization, Givens rotations are used and just two rows need to be rotated on each step.

If the subdiagonal is nonzero, that is, h_{i+1,i}\ne 0 for all i, then H is said to be unreduced. In this case, \mathrm{rank}(H - \lambda I ) \ge n-1 for any \lambda, which means that there is one linearly independent eigenvector associated with each eigenvalue of H (equivalently, no eigenvalue appears in more than one Jordan block in the Jordan canonical form of H).

Unitary Hessenberg Matrices

A unitary Hessenberg matrix H with positive subdiagonal elements can be represented in terms of 2n-1 real parameters (the Schur parametrization), which are essentially the angles in the Givens QR factorization (note that in the QR factorization H = QR, R is triangular and unitary and hence diagonal). The MATLAB function gallery('randhess',n) generates random real orthogonal Hessenberg matrices by choosing the Schur parameters randomly: 

>> n = 4; rng(1), H = gallery('randhess',n)
H =
  -8.6714e-01  -9.2330e-02  -4.8943e-01   3.5172e-04
  -4.9807e-01   1.6075e-01   8.5211e-01  -6.1236e-04
            0   9.8267e-01  -1.8538e-01   1.3322e-04
            0            0  -7.1864e-04  -1.0000e+00
>> check_unitary = norm(H'*H-eye(n))
check_unitary =
   1.1757e-16

Examples

A famous Hessenberg matrix with some interesting properties is the Frank Matrix. For example, the eigenvalues appear in reciprocal pairs (\lambda,1/\lambda). For n = 5: 

>> F = gallery('frank',5)
F =
     5     4     3     2     1
     4     4     3     2     1
     0     3     3     2     1
     0     0     2     2     1
     0     0     0     1     1

>> e = eig(F); sort([e 1./e])
ans =
   9.9375e-02   9.9375e-02
   2.8117e-01   2.8117e-01
   1.0000e+00   1.0000e+00
   3.5566e+00   3.5566e+00
   1.0063e+01   1.0063e+01

Another well-known Hessenberg matrix is the Grcar matrix, a Toeplitz matrix of the form 

>> G = gallery('grcar',5)
G =
     1     1     1     1     0
    -1     1     1     1     1
     0    -1     1     1     1
     0     0    -1     1     1
     0     0     0    -1     1

It has interesting pseudospectra.

Companion matrices are upper Hessenberg with a unit subdiagonal:

\notag C = \begin{bmatrix} a_{n-1} & a_{n-2} & \dots &\dots & a_0 \\ 1 & 0 & \dots &\dots & 0 \\ 0 & 1 & \ddots & & \vdots \\ \vdots & & \ddots & 0 & 0 \\ 0 & \dots & \dots & 1 & 0 \end{bmatrix}.

References

  • W. B. Gragg, The QR Algorithm for Unitary Hessenberg Matrices, J. Comp. Appl. Math., 16 (1986), pp. 1-8.
  • Lloyd Trefethen and Mark Embree, Spectra and Pseudospectra: The Behavior of Nonnormal Matrices and Operators, Princeton University Press, Princeton, NJ, USA, 2005. For the Grcar matrix.

Related Blog Posts

This article is part of the “What Is” series, available from https://nhigham.com/index-of-what-is-articles/ and in PDF form from the GitHub repository https://github.com/higham/what-is.