What Is a Hessenberg Matrix?
source link: https://nhigham.com/2023/12/05/what-is-a-hessenberg-matrix/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
What Is a Hessenberg Matrix?
An upper Hessenberg matrix has the property that for . For , the structure is
is an upper triangular matrix with an extra subdiagonal.
A lower Hessenberg matrix 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 to Hessenberg form by unitary Householder transformations and then carry out the QR iteration on the Hessenberg form.
Because is so close to being triangular, its LU factorization and QR factorization can both be computed in flops. For example, the first stage of LU factorization needs to eliminate just one element, by adding a multiple of row to row (assuming ):
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, for all , then is said to be unreduced. In this case, for any , which means that there is one linearly independent eigenvector associated with each eigenvalue of (equivalently, no eigenvalue appears in more than one Jordan block in the Jordan canonical form of ).
Unitary Hessenberg Matrices
A unitary Hessenberg matrix with positive subdiagonal elements can be represented in terms of real parameters (the Schur parametrization), which are essentially the angles in the Givens QR factorization (note that in the QR factorization , 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 . For :
>> 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:
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.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK