The upper Hessenberg matrix
was introduced by Frank in 1958 as a test matrix for eigensolvers.
Taking the Laplace expansion about the first column, we obtain , and since we have .
In MATLAB, the computed determinant of the matrix and its transpose can be far from the exact values of :
>> n = 20; F = anymatrix('gallery/frank',n); >> [det(F), det(F')] ans = 1.0000e+00 -1.4320e+01 >> n = 49; F = anymatrix('gallery/frank',n); det(F) ans = -1.406934439401568e+45
This behavior illustrates the sensitivity of the determinant rather than numerical instability in the evaluation and it is very dependent on the arithmetic (different results may be obtained in different releases of MATLAB). The sensitivity can be seen by noting that
which means that changing the element from 1 to changes the determinant by .
Inverse and Condition Number
It is easily verified that
Hence is lower Hessenberg with integer entries. This factorization provides another way to see that .
From (1) we see that is singular for , which implies that
for any subordinate matrix norm, showing that the condition number grows very rapidly with . In fact, this lower bound is within a factor of the condition number for the -, -, and -norms for .
Denote by the characteristic polynomial of . By expanding about the first column one can show that
Using (3), one can show by induction that
This means that the eigenvalues of occur in reciprocal pairs, and hence that is an eigenvalue when is odd. It also follows that is palindromic when is even and anti-palindromic when is odd. Examples:
>> charpoly( anymatrix('gallery/frank',6) ) ans = 1 -21 120 -215 120 -21 1 >> charpoly( anymatrix('gallery/frank',7) ) ans = 1 -28 231 -665 665 -231 28 -1
Since has nonzero subdiagonal entries, for any , and hence is nonderogatory, that is, no eigenvalue appears in more than one Jordan block in the Jordan canonical form. It can be shown that the eigenvalues are real and positive and that they can be expressed in terms of the zeros of Hermite polynomials. Furthermore, the eigenvalues are distinct.
If each eigenvalue of an matrix undergoes a small perturbation then the determinant, being the product of the eigenvalues, undergoes a perturbation up to about times as large. From (1) we see that a change to of order can perturb by , and it follows that some eigenvalues must undergo a large relative perturbation. The condition number of a simple eigenvalue is defined as the reciprocal of the cosine of the angle between its left and right eigenvectors. For the Frank matrix it is the small eigenvalues that are ill conditioned, as shown here for .
>> n = 9; F = anymatrix('gallery/frank',n); >> [V,D,cond_evals] = condeig(F); evals = diag(D); >> [~,k] = sort(evals,'descend'); >> [evals(k) cond_evals(k)] ans = 2.2320e+01 1.9916e+00 1.2193e+01 2.3903e+00 6.1507e+00 1.5268e+00 2.6729e+00 3.6210e+00 1.0000e+00 6.8615e+01 3.7412e-01 1.5996e+03 1.6258e-01 1.1907e+04 8.2016e-02 2.5134e+04 4.4803e-02 1.4762e+04
Frank found that “gives our selected procedures difficulties” and that “accuracy was lost in the smaller roots”. The difficulties encountered by Frank’s codes were shown by Wilkinson to be caused by the inherent sensitivity of the eigenvalues to perturbations in the matrix.
This is a minimal set of references, which contain further useful references within.
- Werner Frank, Computing Eigenvalues of Complex Matrices by Determinant Evaluation and by Methods of Danilewski and Wielandt, J. Soc. Indust. Appl. Math. 6(4), 378–392, 1958.
- Efruz Özlem Mersin and Mustafa Bahçsi, Sturm Theorem for the Generalized Frank Matrix, Hacettepe Journal of Mathematics and Statistics 50, 1002–1011, 2021.
- J. H. Wilkinson, Error Analysis of Floating-Point Computation, Numer. Math. 2(1), 319–340, 1960.
- J. H. Wilkinson, The Algebraic Eigenvalue Problem, Oxford University Press, 1965, Section 5.45.