A Deterministic Algorithm for Eigenvalue Separation in Tridiagonal Matrices
We develop a deterministic algorithm for separating the eigenvalues of Hermitian tridiagonal matrices by small diagonal perturbations. For $\|T\|_2\leq1$, $0<\delta<1/2$, and $X=\mathrm{diag}(1,\ldots,n)$, our algorithm selects $t\in[0,\delta/n]$ such that $D=tX$ satisfies $\|D\|_2\leq\delta$ and $\mathrm{gap}(T+D)>c\,...