How well-conditioned can the eigenvector problem be?

Beltrán, Carlos; Bétermin, Laurent; Grabner, Peter; Steinerberger, Stefan

doi:10.1090/mcom/3706

How well-conditioned can the eigenvector problem be?
HTML articles powered by AMS MathViewer

by Carlos Beltrán, Laurent Bétermin, Peter Grabner and Stefan Steinerberger HTML | PDF

Math. Comp. 91 (2022), 1237-1245 Request permission

Abstract:

The condition number for eigenvector computations is a well-studied quantity. But how small can it possibly be? Specifically, what matrices are perfectly conditioned with respect to eigenvector computations? In this note we answer this question for $n \times n$ matrices, giving a solution that is exact to first-order as $n \rightarrow \infty$.

References

R. Alam and S. Bora, On sensitivity of eigenvalues and eigendecompositions of matrices, Linear Algebra Appl. 396 (2005), 273–301. MR 2112210, DOI 10.1016/j.laa.2004.10.013
Diego Armentano, Carlos Beltrán, Peter Bürgisser, Felipe Cucker, and Michael Shub, A stable, polynomial-time algorithm for the eigenpair problem, J. Eur. Math. Soc. (JEMS) 20 (2018), no. 6, 1375–1437. MR 3801817, DOI 10.4171/JEMS/789
Jess Banks, Jorge Garza-Vargas, Archit Kulkarni, and Nikhil Srivastava, Pseudospectral shattering, the sign function, and diagonalization in nearly matrix multiplication time, 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, IEEE Computer Soc., Los Alamitos, CA, [2020] ©2020, pp. 529–540. MR 4232064, DOI 10.1109/FOCS46700.2020.00056
Peter Bürgisser and Felipe Cucker, Condition, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 349, Springer, Heidelberg, 2013. The geometry of numerical algorithms. MR 3098452, DOI 10.1007/978-3-642-38896-5
James Weldon Demmel, On condition numbers and the distance to the nearest ill-posed problem, Numer. Math. 51 (1987), no. 3, 251–289. MR 895087, DOI 10.1007/BF01400115
James W. Demmel, The probability that a numerical analysis problem is difficult, Math. Comp. 50 (1988), no. 182, 449–480. MR 929546, DOI 10.1090/S0025-5718-1988-0929546-7
L. Fejes, Über einen geometrischen Satz, Math. Z. 46 (1940), 83–85 (German). MR 1587, DOI 10.1007/BF01181430
L. Fejes, Über die dichteste Kugellagerung, Math. Z. 48 (1943), 676–684 (German). MR 9129, DOI 10.1007/BF01180035
Peter D. Lax and Ralph S. Phillips, The asymptotic distribution of lattice points in Euclidean and non-Euclidean spaces, J. Functional Analysis 46 (1982), no. 3, 280–350. MR 661875, DOI 10.1016/0022-1236(82)90050-7
A. M. Turing, Rounding-off errors in matrix processes, Quart. J. Mech. Appl. Math. 1 (1948), 287–308. MR 28100, DOI 10.1093/qjmam/1.1.287
Charles Van Loan, On estimating the condition of eigenvalues and eigenvectors, Linear Algebra Appl. 88/89 (1987), 715–732. MR 882468, DOI 10.1016/0024-3795(87)90131-5
John von Neumann and H. H. Goldstine, Numerical inverting of matrices of high order, Bull. Amer. Math. Soc. 53 (1947), 1021–1099. MR 24235, DOI 10.1090/S0002-9904-1947-08909-6
J. H. Wilkinson, Note on matrices with a very ill-conditioned eigenproblem, Numer. Math. 19 (1972), 176–178. MR 311092, DOI 10.1007/BF01402528