Deterministic regularisation of the nonsymmetric eigenproblem
We give a deterministic algorithm for pseudospectral shattering in exact arithmetic. This resolves an important open problem in the complexity of the nonsymmetric eigenproblem. Given a complex contraction $A$ of order $n\ge2$ and $0<\delta<1/2$, we compute a perturbation $E$ with $\|E\|<\delta$ such that $A+E$ has simple spectrum. The ratio of its eigenbasis condition number to its minimum eigenvalue gap is at most $C(n/\delta)^{20/3}$. The algorithm also computes an exact eigensystem of $A+E$. It uses $O(n^3\log^d(n/\delta))$ real-field operations and comparisons, where $C$ and $d$ are absolute constants. We choose the rank-one perturbations using a lower bound on the circle mean of the logarithm of the discriminant modulus. A quadratic penalty controls how far the accumulated updates move the matrix. By using the same reference eigenbasis for several updates, we can estimate all the current projector norms while recovering only the directions needed for the next perturbation.
Authors
- Matthew J. Colbrook (ORCID: https://orcid.org/0000-0003-4964-9575)
Institutions
- University of Cambridge (GB)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-21
- DOI
- https://doi.org/10.5281/zenodo.24413261
- Primary Topic
- Matrix Theory and Algorithms
- Type
- preprint