betaFeedback

WorksMathematics

A Deterministic Algorithm for Eigenvalue Separation in Tridiagonal Matrices

Abstract

We develop a deterministic algorithm for separating the eigenvalues of Hermitian tridiagonal matrices by small diagonal perturbations. For ∥T∥2≤1\|T\|_2\leq1, 0<δ<1/20<δ<1/2, and X=diag(1,…,n)X=\mathrm{diag}(1,\ldots,n), our algorithm selects t∈[0,δ/n]t\in[0,δ/n] such that D=tXD=tX satisfies ∥D∥2≤δ\|D\|_2\leqδ and gap(T+D)>c δ2n−12\mathrm{gap}(T+D)>c\,δ^2n^{-12} for an absolute constant c>0c>0. The construction uses a classical convex weighted eigenvalue sum and its finite-scale slope variation. A tridiagonal localization argument turns near-degenerate eigenvalues into separated responses to the fixed diagonal direction, yielding a quantitative gap certificate. An adaptive interval selector then identifies a certifying window in at most ⌈log⁡2(16n3)⌉\lceil\log_2(16n^3)\rceil refinements, using O(log⁡n)O(\log n) evaluations of the weighted eigenvalue sum to inverse-polynomial accuracy. A structure-exploiting implementation uses rigorous Sturm eigenvalue enclosures and adaptive precision to certify the stopping condition on six families of test matrices. The directly certified gaps are substantially larger than the worst-case analytical bounds, illustrating both the effectiveness of the construction and the conservatism of the universal certificate. Our results give a deterministic answer to the eigenvalue-separation question underlying the deterministic Minami perturbation problem for tridiagonal matrices.

Paper details

vlnc:W_tvnzaarn
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Claude, Codex, Qwen (multiple versions)

View statement
Looking for related papers…