Perturbation of the spectrum of a matrix by adding small decaying coefficients. BACKGROUND & MOTIVATION: We consider in a complex infinite-dimensional Hilbert space a bounded operator $T$. We pick a Hilbert basis $(e_n)_{n\in\mathbb{Z}}$ and project $T$ onto it: for all $N\in\mathbb{N}^*$, we let
\begin{align*}
T_N&:=(\langle e_m,Te_n\rangle)_{|m|,|n|\leq N}
\end{align*}
where $\langle\cdot,\cdot\rangle$ is the inner product of the Hilbert space. The main motivation is to determine whether $0$ is in the spectrum of $T$ or not. We assume that $T$ is of the form $\mathrm{1}+K$ where $K$ is trace-class, so that $T$ is Fredholm of index $0$: in particular, its spectrum consists in eigenvalues and $0$ is an eigenvalue if and only if the Fredholm determinant $\det(\mathrm{1}+K)$ cancels. Since $T_N\to T$ as $N\to+\infty$ in the operator norm topology, we have:
\begin{align*}
\lim_{N\to+\infty}\det((\langle e_m,Te_n\rangle)_{|m|,|n|\leq N})&=\det(T).
\end{align*}
Since $K$ is compact, we do know that the non-zero eigenvalues of $K_N:=(\langle e_m,Ke_n\rangle)_{|m|,|n|\leq N}$ converge to non-zero eigenvalues of $K$.
Now the goal is to give an estimate on the rate of convergence of the eigenvalues of $K_N$ with, say, modulus greater than $1/4$, to their limits in the spectrum of $K$. In the literature, such an estimate relies on bounding the resolvent $(K-\lambda)^{-1}$ for $\lambda$ on a small contour enclosing an eigenvalue of $K$, which is not feasible in practice.

Fix $N\in\mathbb{N}^*$ and $N'>N$. To simplify notations and put the problem into a general form, let $A_N\equiv A\in\mathcal{M}_{2N+1}(\mathbb{C})$ (so $A$ plays the role of $K_N$ above) and
\begin{align*}
A'&:=\begin{pmatrix}E_1&E_2&E_3\\E_4&A&E_5\\E_6&E_7&E_8\end{pmatrix}\in\mathcal{M}_{2N'+1}(\mathbb{C})
\end{align*}
where $E_1,E_3,E_6,E_8\in\mathcal{M}_{N'-N}(\mathbb{C})$, $E_2,E_7\in\mathcal{M}_{N'-N,2N+1}(\mathbb{C})$ and $E_4,E_5\in\mathcal{M}_{2N+1,N'-N}(\mathbb{C})$ have $\|\cdot\|_1$ and $\|\cdot\|_\infty$ norms $\leq\varepsilon$; we also have that $\sum_{k}|E_j|_{kk}\leq\varepsilon$ by the trace-class property of $K$. Typically, the coefficients of $A'$ decay as "we move to the exterior" of $A$', that is:
\begin{align*}
&|(E_2)_{j,k}|\lesssim\frac{1}{(N'+j)^2};&&|(E_7)_{j,k}|\lesssim\frac{1}{(N+j)^2};\\
&|(E_4)_{j,k}|\lesssim\frac{1}{(N'+k)^2};&&|(E_5)_{j,k}|\lesssim\frac{1}{(N+k)^2};\\
&|(E_1)_{j,k}|\lesssim\frac{1}{(N'+j)^2},\frac{1}{(N'+k)^2};&&|(E_6)_{j,k}|\lesssim\frac{1}{(N'+k)^2},\frac{1}{(N+j)^2};\\
&|(E_3)_{j,k}|\lesssim\frac{1}{(N'+j)^2},\frac{1}{(N+k)^2};&&|(E_8)_{j,k}|\lesssim\frac{1}{(N+k)^2},\frac{1}{(N+j)^2}.
\end{align*}
Using the formula
\begin{align*}
\lambda\mathrm{1}_{2N+1}&=\frac{1}{2\pi\mathrm{i}}\oint(A-\mu)^{-1}\mu\mathrm{d}\mu
\end{align*}
for all eigenvalue $\lambda$ of $A$, we know that there exists $\delta(\varepsilon)>0$ such that
\begin{align*}
\mathrm{Spec}(A')\setminus\overline{D(0,1/4)}\subset\mathrm{Spec}(A)\setminus\overline{D(0,1/4)}+D(0,\delta(\varepsilon))\tag{$\star$}
\end{align*}
where $\mathrm{Spec}$ denotes the spectrum of the corresponding matrix; here we removed the closed discs $\setminus\overline{D(0,1/4)}$ as we do not interest ourselves in the spectrum that accumulate at 0 (by compactness of $K$). I would like to get an explicit estimate of $\delta(\varepsilon)$. The matrix $A$ is not normal.

One way I see to prove the statement for the largest (in modulus) eigenvalues is to use the definition of the spectral radius as $\lim_{n\to+\infty}\|A^n\|^{\frac{1}{n}}$; but this implies to compute the coefficients of $A^n$: we can see that we obtain a matrix whose each line consists in a sum of $3^n$ products of the matrices $E_j$ and $A$, and indeed the term $A^n$ is obtained on the line $k$ for $N'+1\leq k\leq N'+2N+1$. I do not see a clean way to proceed then as terms containing $A^\ell$ with $\ell\leq n-1$ do not vanish at the limit $n\to+\infty$ (and could blow in norm as $n\to+\infty$).
Another thing I tried without success is the following: let $u\in\mathbb{C}^{2N+1}$ and $\lambda\in\mathbb{C}$ such that $Au=\lambda u$ with $|\lambda|>1/4$. We look for $u'\in\mathbb{C}^{2N'+1}$ and $\lambda'\in\mathbb{C}$ such that $A'u'=\lambda'u'$ of the form
\begin{align*}
u'&=\sum_{k=0}^{+\infty}\varepsilon^ku_k,\qquad\qquad\lambda'=\sum_{k=0}^{+\infty}\varepsilon^k\lambda_k
\end{align*}
where $u_0=(0,u,0)$ and $\lambda_0=\lambda$. The idea was then to eliminate terms of order $\varepsilon^k$ with an appropriate choice of $u_k$ and $\lambda_k$ -- perhaps by setting $\varepsilon^{2k}\lambda_k$ in the series defining $\lambda'$ instead of $\varepsilon^k\lambda_k$. I could not manage to do it so far.
 A: A not-completed answer.
We denote by $\,\!^TM$ the transpose of a matrix $M$ and $\mathrm{Com}(M)$ its comatrix. Let $\mu\in\mathrm{Spec}(A)$, $\lambda\in C(\mu,\delta)$ and $E:=A'-A$ (embedding $A$ in $\mathcal{M}_{2N'+1}(\mathbb{C})$ by adding zero entries; note that $E_{jk}=0$ for $-N\leq j,k\leq N$). Then:
\begin{align*}
\mathrm{I}:=\left|\det(A-\lambda)-\det(A'-\lambda)\right|&=\left|\int_0^1\mathrm{Tr}\Big\{\big[\!\,^T\mathrm{Com}\big((A-\lambda)+t(A'-A)\big)\big]\circ(A'-A)\Big\}\mathrm{d}t\right|\\
&=\left|\int_0^1\mathrm{Tr}\Big\{\big[\!\,^T\mathrm{Com}\big((A-\lambda)+tE\big)\big]\circ E\Big\}\mathrm{d}t\right|,
\end{align*}
\begin{align*}
\mathrm{II}:=\left|\det(A-\lambda)\right|&=\left|\det\big((A-\mu)-(\lambda-\mu)\big)\right|\\
&=\left|\int_0^1\mathrm{Tr}\Big\{\big[\!\,^T\mathrm{Com}\big((A-\mu)+t(\lambda-\mu)\big)\big]\circ(\lambda-\mu)\mathrm{1}_{2N'+1}\Big\}\mathrm{d}t\right|\\
&=\delta\left|\int_0^1\mathrm{Tr}\Big\{\big[\!\,^T\mathrm{Com}\big((A-\mu)+t(\lambda-\mu)\big)\big]\Big\}\mathrm{d}t\right|.
\end{align*}
The trace in the last line above is the one defined on $\mathcal{M}_{2N+1}(\mathbb{C})$ since $\!\,^T\mathrm{Com}\big(A-\mu\big)\in\mathcal{M}_{2N+1}(\mathbb{C})$. Now, very roughly speaking, the first term is $\varepsilon\left|\mathrm{Tr}\Big\{\big[\!\,^T\mathrm{Com}\big(A-\mu\big)\big]\Big\}\right|$ (where $\varepsilon\geq\|E\|$) while the second term is $\delta\left|\mathrm{Tr}\Big\{\big[\!\,^T\mathrm{Com}\big(A-\mu\big)\big]\Big\}\right|$. So if $\varepsilon\lesssim\delta$ then Rouché's theorem asserts that there are as many zeros of $\det(A'-\lambda)$ counted with multiplicity in $C(\mu,\delta)$ as $\det(A-\lambda)$, yielding the property $(\star)$ of the original post. It remains to rigorously prove that $\mathrm{I}<\mathrm{II}$. I expect that we will have to use $|\lambda|,|\mu|\leq\mathrm{spectral\ radius\ of\ }(K)+\delta$.
As we let $N'\to\infty$, we do know by the trace-class property of the original operator $K$ that small eigenvalues (say in $D(0,1/4)$) will remain in $\overline{D(0,3/4)}$ if we take $N$ large enough so that $|\mathrm{Tr}(K_N)-\mathrm{Tr}(K)|\leq1/2$ (which is something we can compute explicitly).

ADDENDUM: We denote by $\widetilde{M}_{ij}$ the matrix $M$ with the $i$-th row and $j$-th column removed. We compute:
\begin{align*}
\mathrm{Com}(A+tH)&=\Big((-1)^{i+j}\det\big((\widetilde{A+tH})_{ij}\big)\Big)_{ij}\\
%
&=\Big((-1)^{i+j}\Big[\det\big(\widetilde{A}_{ij}\big)+\int_{0}^{1}\mathrm{Tr}\Big\{\,\!^{T}\mathrm{Com}\big((\widetilde{A+stH})_{ij}\big)\circ\widetilde{tH}_{ij}\Big\}\mathrm{d}s\Big]\Big)_{ij}\\
%
&=\mathrm{Com}(A)+\Big((-1)^{i+j}\int_{0}^{1}\mathrm{Tr}\Big\{\,\!^{T}\mathrm{Com}\big((\widetilde{A+stH})_{ij}\big)\circ\widetilde{tH}_{ij}\Big\}\mathrm{d}s\Big)_{ij}.
\end{align*}
Hence:
\begin{align*}
\mathrm{I}&=\left|\int_{0}^{1}\mathrm{Tr}\Big\{\,\!^T\mathrm{Com}(A-\lambda)\circ E\Big\}\mathrm{d}t\right.\\
&\quad\left.+\int_{0}^{1}\int_{0}^{1}\mathrm{Tr}\Big\{\,\!^T\Big((-1)^{i+j}\mathrm{Tr}\Big\{\,\!^{T}\mathrm{Com}\big((\widetilde{A-\lambda+stE})_{ij}\big)\circ\widetilde{tE}_{ij}\Big\}\Big)_{ij}\circ tE\Big\}\mathrm{d}s\mathrm{d}t\right|,\\
%
\mathrm{II}&=\left|\delta\int_{0}^{1}\mathrm{Tr}\Big\{\,\!^T\mathrm{Com}(A-\lambda)\Big\}\mathrm{d}t\right.\\
&\quad\left.+\delta\int_{0}^{1}\int_{0}^{1}\mathrm{Tr}\Big\{\,\!^T\Big((-1)^{i+j}\mathrm{Tr}\Big\{\,\!^{T}\mathrm{Com}\big((\widetilde{A-\lambda+s(1+t)(\lambda-\mu)})_{ij}\big)\circ\widetilde{t(\lambda-\mu)}_{ij}\Big\}\Big)_{ij}\circ t(\lambda-\mu)\Big\}\mathrm{d}s\mathrm{d}t\right|
\end{align*}
Now observe that $\mathrm{Tr}\Big\{\,\!^T\mathrm{Com}(A-\lambda)\circ E\Big\}=0$ due to the zero coefficients of $\,\!^T\mathrm{Com}(A-\lambda)$. The problem is thus solved if can estimate the minimal size of $\|E\|$ satisfying:
\begin{align*}
&\left|\int_{0}^{1}\int_{0}^{1}\mathrm{Tr}\Big\{\,\!^T\Big((-1)^{i+j}\mathrm{Tr}\Big\{\,\!^{T}\mathrm{Com}\big((\widetilde{A-\lambda+stE})_{ij}\big)\circ\widetilde{tE}_{ij}\Big\}\Big)_{ij}\circ tE\Big\}\mathrm{d}s\mathrm{d}t\right|\\
&\quad+\delta\left|\int_{0}^{1}\int_{0}^{1}\mathrm{Tr}\Big\{\,\!^T\Big((-1)^{i+j}\mathrm{Tr}\Big\{\,\!^{T}\mathrm{Com}\big((\widetilde{A-\lambda+s(1+t)(\lambda-\mu)})_{ij}\big)\circ\widetilde{t(\lambda-\mu)}_{ij}\Big\}\Big)_{ij}\circ t(\lambda-\mu)\Big\}\mathrm{d}s\mathrm{d}t\right|<\delta\left|\mathrm{Tr}\Big\{\,\!^T\mathrm{Com}(A-\lambda)\Big\}\right|.
\end{align*}
A: The question is for me, as it stays now, not completely clear regarding the fixed $N$ from the first line, the undefined $\varepsilon$ that appears in the second line (soon used for some condition on the $E$-matrices), then the fact that in the next line $N$ (fixed) and $\varepsilon$ become variables for the estimation, and are related to each other. These lines were first written as a comment, but did not fit in the very restricted comment box, so they became an answer. I will let this unclear fact about $N$ and $\varepsilon$ as it is, and just start a particular example to illustrate my problems with the framework.

There is no specification about the shapes of the block matrices involved in $A$, so i will assume (as a particular case of the given very general situation) that the block matrices on the diagonal of $A'$ have square shape, i am conjugating with a permutation matrix, so the problem deals with the eigenvalues of the matrices $B$ (permutation conjugation of $A'$) and those of $A$, where $A,B$ are related by
$$
B=\begin{bmatrix}
A & E_{12}\\
E_{21} & E_{22}
\end{bmatrix}\ .
$$
Of course, we can now consider in full generality characteristic polynomials and try to say something about coefficients. But let us work in a simple toy example where $A$ is a diagonal matrix with (e.g. distinct, e.g. real, and best spaced with at least $2\varepsilon$ distance between them) eigenvalues $a_1<a_2<a_3<\dots$ which are "big" (e.g. around one or around $1000$), and where $E_{22}$ is diagonal with (e.g. distinct, e.g. real) "small" (i.e. bounded by $\varepsilon$) eigenvalues $\varepsilon_1,\varepsilon_2,\varepsilon_3,\dots$
and let us finally let the non-diagonal $E$-blocks vanish. Then $B$ (and $A'$) has the spectrum $\{a_1,a_2,a_3,\dots\}\cup\{\varepsilon_1,\varepsilon_2,\varepsilon_3,\dots\}$ which is not located inside an $\varepsilon$-neighbourhood of Spec$(A)=\{a_1,a_2,a_3,\dots\}$.
For my understanding, the set Spec$(A)+D(0,\delta(\varepsilon)$ is in the case of spaced $A$-eigenvalues the set
$$
\bigcup_j D(a_j, \delta(\varepsilon))\ ,
$$
and the spectrum of $B$ is not contained in the above set for a "small" $\delta(\varepsilon)$. (Since it contains also some "small" eigenvalues $
 \varepsilon_1,\varepsilon_2,\varepsilon_3,\dots$ which are far away from the $A$-eigenvalues.)

Please give some more details about the situation where the estimation should be applied. Or please show what should work in the case of a block-diagonal $A'$ with a fixed (even diagonal $A$) and diagonal remaining blocks.
