\chapter{Actual and linearized gaps}\label{s:linearization}

The goal of this section is to prove \zcref{p:linearization}, which compares the gaps of the resampled matrix $\widetilde H$ with the linearized gaps $2 d |z_i + S_i|$. Recall from \zcref{l:reduction-identity} that, when the selected positions are distinct, the linearized gap of the pair $(i, i + 1)$ is the gap of the compression of $\widetilde H$ to the span of $u_i$ and $u_{i + 1}$. Heuristically, when $g_i$ is much smaller than the distance from $\lambda_i$ and $\lambda_{i + 1}$ to the other eigenvalues of $H$, the gap $\tilde g_i$ should be close to the linearized gap, since the remaining eigenvectors of $H$ interact with the pair only at second order in $\Delta$.

The proof has two steps. In \zcref{s:lin-deterministic}, we prove a deterministic statement, \zcref{c:deterministiclinear}, by applying \zcref{l:cluster} in the eigenbasis of $H$; the main task is to verify its hypotheses with explicit exponents. In \zcref{s:lin-proof}, we show that these hypotheses hold with probability tending to one.

Throughout this section, we set $\eps = 1/100$. Recall that $d = N^{-3/2}$, $\tau = N^{1/100}$, $s = N^{-7/5}$, and $m = 2 \lfloor \tau/8 \rfloor \le \tau/4$.

\section{A deterministic comparison}\label{s:lin-deterministic}

In \zcref{s:lin-deterministic}, $H$ denotes a deterministic real symmetric $N \times N$ matrix with eigenvalues $\lambda_1 \le \dots \le \lambda_N$, and $u_1, \dots, u_N$ denotes an orthonormal basis of $\R^N$ such that $H u_j = \lambda_j u_j$ for all $j \in [N]$. We define $g_i$ and $E_i$ for $i \in [N - 1]$, and the maps $L_i$, by the formulas of \zcref{s:reduction}, using these eigenvalues and eigenvectors.

\begin{definition}\label{d:lin-clusters}
Let $\mathfrak K(H)$ denote the set of equivalence classes of the smallest equivalence relation on $[N]$ under which $j$ and $j + 1$ are equivalent for every $j \in [N - 1]$ such that $g_j \le s$. We call the elements of $\mathfrak K(H)$ the \emph{clusters} of $H$.
\end{definition}

Observe that every cluster is a set of consecutive integers, and that for every $j \in [N - 1]$, the labels $j$ and $j + 1$ lie in the same cluster if and only if $g_j \le s$. In particular, $\mathfrak K(H)$ is a family of clusters in the sense of \zcref{s:prelim-perturbation}.

We let $\Lambda = \diag(\lambda_1, \dots, \lambda_N)$, and we let $U = (u_1, \dots, u_N)$ denote the orthogonal $N \times N$ matrix with columns $u_1, \dots, u_N$, so that $H = U \Lambda U^T$. For $\mathcal K \in \mathfrak K(H)$, we let $U_{\mathcal K}$ denote the $N \times |\mathcal K|$ matrix whose columns are the vectors $u_j$ with $j \in \mathcal K$, in increasing order of $j$, and we set $\Lambda_{\mathcal K} = \diag(\lambda_j : j \in \mathcal K)$. For an $N \times N$ matrix $A$, we use the notation $A_{\mathcal K \mathcal K} = (A_{j j'})_{j, j' \in \mathcal K}$ of \zcref{s:prelim-perturbation}.

Recall the quantities $w_N$, $\mathscr L_N$, and $\delta_N$ from \eqref{e:reduction-lin-parameters}. Since $\eps = 1/100$, they are given by
\begin{equation}\label{e:lin-parameters}
w_N = \tau N^{-3/2 + 3 \eps}, \qquad \mathscr L_N = 2 s^{-1} \log N, \qquad \delta_N = 8 w_N^2 \mathscr L_N.
\end{equation}
Inserting the values of $\tau$, $s$, $d$, and $\eps$, and using $\delta_N/d = 8 (w_N/d) (w_N \mathscr L_N)$ and $w_N/d = \tau N^{3 \eps}$, we find
\begin{equation}\label{e:lin-ratios}
\begin{gathered}
\frac{w_N}{s} = N^{-9/100 + 3 \eps} = N^{-3/50}, \qquad w_N \mathscr L_N = 2 N^{-3/50} \log N, \\
\frac{\delta_N}{d} = 16 N^{-2/25 + 6 \eps} \log N = 16 N^{-1/50} \log N.
\end{gathered}
\end{equation}
All three quantities in \eqref{e:lin-ratios} tend to zero.

\begin{corollary}\label{c:deterministiclinear}
There exists an absolute constant $N_0 \ge 1$ such that the following holds for all $N \ge N_0$. Let $H$ and $u_1, \dots, u_N$ be as above, and suppose that
\begin{enumerate}
\item[(i)] $\|H\| \le 3$;
\item[(ii)] $|u_j(a)| \le N^{-1/2 + \eps}$ for all $a, j \in [N]$;
\item[(iii)] $\lambda_{j + 2} - \lambda_j > 4 s$ for all $j \in [N - 2]$.
\end{enumerate}
Let $\Delta$ be a real symmetric $N \times N$ matrix such that $\Delta_{aa} = 0$ for all $a \in [N]$, $|\Delta_{ab}| \le 2 N^{-1/2 + \eps}$ for all $a, b \in [N]$, and $\Delta_{ab} \neq 0$ for at most $\tau/4$ pairs $(a, b)$ with $a < b$. Then every cluster of $H$ has at most two elements, and the two-element clusters of $H$ are the sets $\{i, i + 1\}$ with $i \in [N - 1]$ and $g_i \le s$. Further, the following statements hold.
\begin{enumerate}
\item[(a)] Let $\mathcal K \in \mathfrak K(H)$. For all $j \in \mathcal K$, we have $\lambda_{\min \mathcal K} - s/4 \le \lambda_j(H + \Delta) \le \lambda_{\max \mathcal K} + s/4$. Moreover, the numbers $\lambda_j(H + \Delta)$ with $j \in \mathcal K$, in increasing order, differ by at most $\delta_N/2$ from the ordered eigenvalues of $\Lambda_{\mathcal K} + U_{\mathcal K}^T \Delta U_{\mathcal K}$.
\item[(b)] For all $\mathcal K \in \mathfrak K(H)$, we have
\begin{equation*}
\Big| \sum_{j \in \mathcal K} \big( \lambda_j(H + \Delta) - \lambda_j \big) \Big| \le |\mathcal K| (w_N + \delta_N/2).
\end{equation*}
\item[(c)] For all $j \in [N - 1]$ such that $g_j > s$, we have $\lambda_{j + 1}(H + \Delta) - \lambda_j(H + \Delta) > s/2$.
\item[(d)] For all $i \in [N - 1]$ such that $g_i \le s$, we have
\begin{equation*}
\big| \lambda_{i + 1}(H + \Delta) - \lambda_i(H + \Delta) - 2 |L_i(H + \Delta)| \big| \le \delta_N.
\end{equation*}
\end{enumerate}
\end{corollary}

\begin{proof}
We first describe the clusters. Suppose that some $\mathcal K \in \mathfrak K(H)$ has at least three elements. As $\mathcal K$ is a set of consecutive integers, there exists $j \in [N - 2]$ such that $j, j + 1, j + 2 \in \mathcal K$. Then $g_j \le s$ and $g_{j + 1} \le s$, which gives $\lambda_{j + 2} - \lambda_j \le 2 s$ and contradicts (iii). Hence every cluster has at most two elements.

If $i \in [N - 1]$ satisfies $g_i \le s$, then $i$ and $i + 1$ lie in the same cluster, which is therefore $\{i, i + 1\}$. Conversely, every two-element cluster has the form $\{i, i + 1\}$ with $g_i \le s$, since its elements are consecutive and lie in the same cluster.

Next, we rotate $\Delta$ into the eigenbasis of $H$. Set
\begin{equation*}
W = U^T \Delta U, \qquad \text{so that} \qquad W_{j j'} = u_j^T \Delta u_{j'} \qquad \text{for } j, j' \in [N].
\end{equation*}
Since $U$ is orthogonal, we have $H + \Delta = U (\Lambda + W) U^T$, and therefore
\begin{equation*}
\lambda_j(H + \Delta) = \lambda_j(\Lambda + W) \qquad \text{for all } j \in [N].
\end{equation*}
As $\Delta$ is symmetric with zero diagonal, the triangle inequality and (ii) give
\begin{equation}\label{e:lin-entrybound}
|W_{j j'}| = \Big| \sum_{1 \le a < b \le N} \Delta_{ab} \big( u_j(a) u_{j'}(b) + u_j(b) u_{j'}(a) \big) \Big| \le \frac{\tau}{4} \cdot 2 N^{-1/2 + \eps} \cdot 2 N^{-1 + 2 \eps} = w_N
\end{equation}
for all $j, j' \in [N]$. In the inequality, we used that at most $\tau/4$ of the coefficients $\Delta_{ab}$ with $a < b$ are nonzero, that each of them is bounded by $2 N^{-1/2 + \eps}$, and that the term in absolute values is bounded by $2 N^{-1 + 2 \eps}$ by (ii).

We will apply \zcref{l:cluster} with $D_y = \Lambda$ (so that $y_j = \lambda_j$), the family of clusters $\mathfrak K(H)$, and the parameters
\begin{equation*}
k_0 = 2, \qquad \vartheta = s/4, \qquad w_0 = w_N, \qquad \mathscr L = \mathscr L_N.
\end{equation*}
For $\mathcal K \in \mathfrak K(H)$, the rectangle \eqref{e:prelim-rectangle} is then
\begin{equation*}
\mathcal R_{\mathcal K} = \big\{ w \in \C : \lambda_{\min \mathcal K} - s/4 \le \Re w \le \lambda_{\max \mathcal K} + s/4, \ |\Im w| \le s/4 \big\}.
\end{equation*}

We next check that these rectangles are pairwise disjoint. Let $\mathcal K, \mathcal K' \in \mathfrak K(H)$ satisfy $\max \mathcal K + 1 = \min \mathcal K'$. Then $g_{\max \mathcal K} > s$, so the intervals $\mathcal R_{\mathcal K} \cap \R$ and $\mathcal R_{\mathcal K'} \cap \R$ are at distance $g_{\max \mathcal K} - s/2 > s/2$.

We now bound the harmonic sum in \eqref{e:prelim-cluster-harmonic}. Fix $\mathcal K \in \mathfrak K(H)$ and $w \in \mathcal R_{\mathcal K}$, and write $i_- = \min \mathcal K$ and $i_+ = \max \mathcal K$. We first consider the labels $j > i_+$, assuming that $i_+ < N$. The labels $i_+$ and $i_+ + 1$ lie in different clusters, so $g_{i_+} > s$.

Let $r \ge 0$ be an integer, and let $j \in \{i_+ + 2r + 1, i_+ + 2r + 2\}$ with $j \le N$. Then
\begin{equation*}
\lambda_j - \Re w \ge \lambda_{i_+ + 2r + 1} - \lambda_{i_+} - s/4 \ge g_{i_+} + 4 s r - s/4 > 3s/4 + 4 s r.
\end{equation*}
The first inequality follows from $\lambda_j \ge \lambda_{i_+ + 2r + 1}$ and $\Re w \le \lambda_{i_+} + s/4$, and the second follows from (iii), applied $r$ times to the labels $i_+ + 1, i_+ + 3, \dots, i_+ + 2r - 1$. Further, (i) implies that $\lambda_j - \Re w < 7$, so only integers $r$ with $4 s r < 7$ occur. Every such $r$ corresponds to at most two labels $j$, and $|\lambda_j - w| \ge |\lambda_j - \Re w|$, so
\begin{equation*}
\sum_{j = i_+ + 1}^N \frac{1}{|\lambda_j - w|} \le \sum_{0 \le r < 7/(4s)} \frac{2}{3s/4 + 4 s r} \le \frac{8}{3 s} + \frac{1}{2 s} \sum_{1 \le r < 7/(4s)} \frac{1}{r} \le \frac{1}{s} \Big( \frac{19}{6} + \frac{1}{2} \log \frac{7}{4 s} \Big),
\end{equation*}
where we compared the harmonic sum with an integral in the last step.

The same argument, with the roles of the two sides exchanged, bounds the sum over $j < i_-$ by the same quantity. Recalling that $s = N^{-7/5}$, we conclude that
\begin{equation}\label{e:lin-harmonic}
\sum_{j \notin \mathcal K} \frac{1}{|\lambda_j - w|} \le \frac{1}{s} \Big( \frac{19}{3} + \log \frac{7}{4} + \frac{7}{5} \log N \Big) \le \frac{2 \log N}{s} = \mathscr L_N
\end{equation}
for $N \ge N_0$, uniformly over all clusters $\mathcal K$ and all $w \in \mathcal R_{\mathcal K}$.

We now apply \zcref{l:cluster}. By \eqref{e:lin-entrybound}, we have $\max_{j, j'} |W_{j j'}| \le w_N$. Using \eqref{e:lin-ratios}, we see that $w_N \mathscr L_N \le 1/2$ and
\begin{equation*}
\frac{1}{s} \big( k_0 w_N + 2 k_0 w_N^2 \mathscr L_N \big) = \frac{2 w_N}{s} + \frac{4 w_N}{s} \cdot w_N \mathscr L_N = 2 N^{-3/50} + 8 N^{-3/25} \log N < \frac14
\end{equation*}
for $N \ge N_0$. Thus the hypotheses of \zcref{l:cluster} hold.

Let $\mathcal K \in \mathfrak K(H)$. Recalling that $\lambda_j(\Lambda + W) = \lambda_j(H + \Delta)$, we deduce from \zcref{l:cluster} that the numbers $\lambda_j(H + \Delta)$ with $j \in \mathcal K$ lie within distance $k_0 w_N + 2 k_0 w_N^2 \mathscr L_N < s/4$ of $[\lambda_{\min \mathcal K}, \lambda_{\max \mathcal K}]$, and that, in increasing order, they differ by at most $2 k_0 w_N^2 \mathscr L_N = \delta_N/2$ from the ordered eigenvalues of
\begin{equation*}
(\Lambda + W)_{\mathcal K \mathcal K} = \Lambda_{\mathcal K} + U_{\mathcal K}^T \Delta U_{\mathcal K}.
\end{equation*}
This proves (a).

To prove (b), we use that the sum of the eigenvalues of a matrix is its trace. Then (a) implies that
\begin{equation*}
\Big| \sum_{j \in \mathcal K} \lambda_j(H + \Delta) - \Tr \big( \Lambda_{\mathcal K} + U_{\mathcal K}^T \Delta U_{\mathcal K} \big) \Big| \le \frac{|\mathcal K| \delta_N}{2}, \qquad \Tr \big( \Lambda_{\mathcal K} + U_{\mathcal K}^T \Delta U_{\mathcal K} \big) = \sum_{j \in \mathcal K} (\lambda_j + W_{jj}).
\end{equation*}
Combining these relations with the bound $|W_{jj}| \le w_N$ from \eqref{e:lin-entrybound}, we obtain (b).

Next, we prove (c). Let $j \in [N - 1]$ satisfy $g_j > s$. Then $j$ and $j + 1$ lie in different clusters $\mathcal K$ and $\mathcal K'$, with $j = \max \mathcal K$ and $j + 1 = \min \mathcal K'$. Using (a) for $\mathcal K$ and $\mathcal K'$, we find
\begin{equation*}
\lambda_{j + 1}(H + \Delta) - \lambda_j(H + \Delta) \ge (\lambda_{j + 1} - s/4) - (\lambda_j + s/4) = g_j - s/2 > s/2.
\end{equation*}

It remains to prove (d). Let $i \in [N - 1]$ satisfy $g_i \le s$, so that $\mathcal K = \{i, i + 1\}$ is a cluster. Recalling that $u_i^T H u_i = \lambda_i$, $u_{i + 1}^T H u_{i + 1} = \lambda_{i + 1}$, and $u_i^T H u_{i + 1} = 0$, we have
\begin{equation*}
\Lambda_{\mathcal K} + U_{\mathcal K}^T \Delta U_{\mathcal K} = \big( u_j^T (H + \Delta) u_{j'} \big)_{j, j' \in \{i, i + 1\}}.
\end{equation*}
By \eqref{e:reduction-gap2x2} and the definition of $L_i$, the two eigenvalues of this matrix differ by $2 |L_i(H + \Delta)|$. By (a), the eigenvalues $\lambda_i(H + \Delta)$ and $\lambda_{i + 1}(H + \Delta)$ differ by at most $\delta_N/2$ from the smaller and the larger of them, respectively, which gives (d).
\end{proof}

\section{Proof of \texorpdfstring{\zcref{p:linearization}}{the comparison of gaps}}\label{s:lin-proof}

We now return to the random matrix $H$ and its chosen eigenvectors $u_1, \dots, u_N$, and we apply \zcref{c:deterministiclinear} to their realizations. The clusters $\mathfrak K(H)$ are then random sets, defined by \zcref{d:lin-clusters} for each realization of $H$.

\begin{proof}[Proof of \zcref{p:linearization}]
Let $N_0$ be the constant of \zcref{c:deterministiclinear}. For $N \ge N_0$, let $\mathcal A_N$ denote the event
\begin{equation}\label{e:lin-eventA}
\begin{split}
\mathcal A_N = \{ H \in \mathcal G_{\eps} \} & \cap \big\{ \lambda_{i + 2} - \lambda_i > 4 s \text{ for all } i \in [N - 2] \big\} \\
& \cap \big\{ |X_{ab}| \le N^{\eps} \text{ for all } a, b \in [N] \text{ with } a < b \big\},
\end{split}
\end{equation}
and for $N < N_0$, set $\mathcal A_N = \emptyset$. The event $\mathcal A_N$ is measurable with respect to $H$ (the condition $H \in \mathcal G_{\eps}$ concerns every unit eigenvector of $H$, not only $u_1, \dots, u_N$). Further, let $\mathcal B_N$ denote the event
\begin{equation}\label{e:lin-eventB}
\mathcal B_N = \big\{ (a_l, b_l) \neq (a_{l'}, b_{l'}) \text{ for all } l, l' \in [m] \text{ with } l \neq l' \big\} \cap \big\{ |Y_l| \le N^{\eps} \text{ for all } l \in [m] \big\},
\end{equation}
which is measurable with respect to the resampling variables. We will show that $\Prob(\mathcal A_N) \to 1$, that $\Prob(\mathcal B_N \mid H) = 1 - o(1)$ uniformly in $H$, and that the conclusions of \zcref{p:linearization} hold on $\mathcal A_N \cap \mathcal B_N$. We may assume that $N \ge N_0$.

We begin with $\mathcal A_N$. \zcref[S]{p:regularity} with $t = 0$ shows that $H \in \mathcal G_{\eps}$ with overwhelming probability. By Markov's inequality and the second statement of \zcref{p:three} with $C_1 = 1$, which applies since $4 s = 4 N^{-7/5} \ge N^{-2}$, we have
\begin{equation}\label{e:lin-nothree}
\Prob \Big( \min_{i \in [N - 2]} (\lambda_{i + 2} - \lambda_i) \le 4 s \Big) \le \E \mathcal N_3(4 s) \le C N (4 N s)^3 = 64 C N^{-1/5}.
\end{equation}
Note that \eqref{e:lin-nothree} covers all $i \in [N - 2]$, including labels at the spectral edges. This is needed, although only pairs in the bulk are used in \zcref{s:reduction}, because \zcref{l:cluster} is applied to the whole spectrum.

Finally, the standardized entries $X_{ab}$ with $a < b$ are copies of $X$, so the sub-Gaussian tail bound and a union bound over fewer than $N^2$ pairs give
\begin{equation*}
\Prob \big( |X_{ab}| > N^{\eps} \text{ for some } a, b \in [N] \text{ with } a < b \big) \le C_0 N^2 e^{-c_0 N^{2 \eps}}.
\end{equation*}
Combining these three bounds, we obtain
\begin{equation*}
\Prob(\mathcal A_N^c) \le C N^{-1/5}.
\end{equation*}

Next, we bound the conditional probability of $\mathcal B_N^c$. The selected positions and the variables $Y_l$ are independent of $H$, so $\Prob(\mathcal B_N \mid H) = \Prob(\mathcal B_N)$. For distinct $l, l' \in [m]$, the positions $(a_l, b_l)$ and $(a_{l'}, b_{l'})$ are independent and uniformly distributed on a set of $N (N - 1)/2$ pairs, so they coincide with probability $2/(N (N - 1))$. A union bound over the fewer than $m^2/2$ pairs $\{l, l'\}$ and over $l \in [m]$, together with $m \le \tau/4$, gives
\begin{equation}\label{e:lin-eventBbound}
\Prob \big( \mathcal B_N^c \mid H \big) \le \frac{m^2}{N (N - 1)} + m C_0 e^{-c_0 N^{2 \eps}} \le \frac{\tau^2}{8 N^2} + C_0 \tau e^{-c_0 N^{2 \eps}}.
\end{equation}
The right side of \eqref{e:lin-eventBbound} is deterministic and tends to zero.

We now fix a realization in $\mathcal A_N \cap \mathcal B_N$ and verify the hypotheses of \zcref{c:deterministiclinear}. As $H \in \mathcal G_{\eps}$, we have $\|H\| \le 3$, and every unit eigenvector of $H$, in particular each $u_j$, satisfies $\|u_j\|_\infty \le N^{-1/2 + \eps}$. Hypothesis (iii) holds by the definition of $\mathcal A_N$. The selected positions are distinct on $\mathcal B_N$, so \zcref{l:reduction-identity} gives
\begin{equation*}
\Delta = \sum_{l = 1}^m N^{-1/2} \big( Y_l - X_{a_l b_l} \big) V^{a_l b_l}.
\end{equation*}
Hence $\Delta$ is real symmetric with zero diagonal, $\Delta_{ab} \neq 0$ for at most $m \le \tau/4$ pairs $(a, b)$ with $a < b$, and
\begin{equation*}
|\Delta_{a_l b_l}| \le N^{-1/2} \big( |Y_l| + |X_{a_l b_l}| \big) \le 2 N^{-1/2 + \eps} \qquad \text{for all } l \in [m],
\end{equation*}
where we used the bounds on $Y_l$ and $X_{a_l b_l}$ contained in $\mathcal B_N$ and $\mathcal A_N$. Thus \zcref{c:deterministiclinear} applies to $H$ and $\Delta$, with $H + \Delta = \widetilde H$.

By \zcref{c:deterministiclinear}, every cluster of $H$ has at most two elements, and the two-element clusters are the sets $\{i, i + 1\}$ with $g_i \le s$. Statement (c) of \zcref{c:deterministiclinear} gives $\tilde g_j > s/2$ for all $j \in [N - 1]$ with $g_j > s$.

Now let $i \in [N - 1]$ satisfy $g_i \le s$, so that $\{i, i + 1\}$ is a cluster. By \zcref{l:reduction-identity}, we have $L_i(\widetilde H) = d (z_i + S_i)$. Statement (d) of \zcref{c:deterministiclinear}, statement (b) with $\mathcal K = \{i, i + 1\}$, and \eqref{e:lin-ratios} therefore give
\begin{equation}\label{e:lin-conclusion}
\Big| \frac{\tilde g_i}{d} - 2 |z_i + S_i| \Big| \le \frac{\delta_N}{d} = 16 N^{-1/50} \log N, \qquad |\widetilde E_i - E_i| \le w_N + \frac{\delta_N}{2}.
\end{equation}
Both bounds in \eqref{e:lin-conclusion} are deterministic and tend to zero by \eqref{e:lin-ratios}. Together with $\Prob(\mathcal A_N) \to 1$ and \eqref{e:lin-eventBbound}, this establishes all assertions of \zcref{p:linearization}.
\end{proof}