# The effective potential of an $M$-matrix

Marcel Filoche  Marcel Filoche, Laboratoire de Physique de la Matière
Condensée, Ecole Polytechnique, CNRS, IP Paris, 91128, Palaiseau, France  ,
Svitlana Mayboroda  Svitlana Mayboroda, School of Mathematics, University of
Minnesota, Minneapolis, Minnesota, 55455, USA  and  Terence Tao  Terence Tao,
Department of Mathematics, UCLA, Los Angeles CA 90095-1555, USA

###### Abstract.

In the presence of a confining potential $V$, the eigenfunctions of a
continuous Schrödinger operator $-\Delta+V$ decay exponentially with the rate
governed by the part of $V$ which is above the corresponding eigenvalue; this
can be quantified by a method of Agmon. Analogous localization properties can
also be established for the eigenvectors of a discrete Schrödinger matrix.
This note shows, perhaps surprisingly, that one can replace a discrete
Schrödinger matrix by _any_ real symmetric $Z$-matrix and still obtain
eigenvector localization estimates. In the case of a real symmetric non-
singular $M$-matrix $A$ (which is a situation that arises in several contexts,
including random matrix theory and statistical physics), the _landscape
function_ $u=A^{-1}1$ plays the role of an effective potential of
localization. Starting from this potential, one can create an Agmon-type
distance function governing the exponential decay of the eigenfunctions away
from the “wells” of the potential, a typical eigenfunction being localized to
a single such well.

##  1\. Introduction: history and motivation

The fundamental premises of quantum physics guarantee that a potential $V$
induces exponential decay of the eigenfunctions of the Schrödinger operator
$-\Delta+V$ (on either a continuous domain ${\mathbb{R}}^{d}$ or a discrete
lattice ${\mathbb{Z}}^{d}$) as long as $V$ is larger than the eigenvalue $E$
outside of some compact region. This heuristic principle has been established
with mathematical rigor by S. Agmon [1] and has served as a foundation to many
beautiful results in semiclassical analysis and other fields (see, e.g., Refs
2, 3, 4, 5 for a glimpse of some of them). Roughly speaking, the modern
interpretation of this principle is that the eigenfunctions decay
exponentially away from the “wells” $\\{x:V(x)\leq E\\}$.

In 2012, two of the authors of the present paper introduced the concept of the
_localization landscape_. They observed in Ref. 6 that the solution $u$ to the
equation $(-\Delta+V)u=1$ appears to have an almost magical power to
“correctly” predict the regions of localization for disordered potentials $V$
and to describe a precise picture of their exponential decay. For instance, if
$V$ takes the values $0$ and $1$ randomly on a two-dimensional lattice
${\mathbb{Z}}^{2}$ (a classical setting of the Anderson–Bernoulli
localization) the eigenfunctions at the bottom of the spectrum are
exponentially localized, that is, exponentially decaying away from some small
region, but this would not be detected by the Agmon theory because the region
$\\{V\leq E\\}$ could be completely percolating and there is no “room” for the
Agmon-type decay, especially if the probability of $V=0$ is larger than the
probability of $V=1$. And indeed, the phenomenon of Anderson localization is
governed by completely different principles, relying on the interferential
rather than confining impact of $V$. On the other hand, looking at the
landscape in this example, we observe that the region $\\{\frac{1}{u}\leq
E\\}$ exhibits isolated wells and that the eigenmodes decay exponentially away
from these wells. It turns out that indeed, the reciprocal of the landscape,
$\frac{1}{u}$, plays the role of an effective potential, and in Ref. 7 Arnold,
David, Jerison, and the first two authors have proved that the eigenfunctions
of $-\Delta+V$ decay exponentially in the regions where $\\{\frac{1}{u}>E\\}$
with the rate controlled by the so-called _Agmon distance_ associated to the
landscape, a geodesic distance in the manifold determined by
$(\frac{1}{u}-E)_{+}$. The numerical experiments in Ref. 8 and physical
considerations in Ref. 9 show an astonishing precision of the emerging
estimates, although mathematically speaking in order to use these results for
factual disordered potentials one has to face, yet again, a highly non-trivial
question of resonances – see the discussion in Ref. 7. At this point we have
only successfully treated Anderson potentials via the localization landscape
in the context of a slightly different question about the integrated density
of states [10].

However, the scope of the landscape theory is not restricted to the setting of
disordered potentials. In fact, all results connecting the eigenfunctions to
the landscape are purely deterministic, and one of the key benefits of this
approach is the absence of _a priori_ assumptions on the potential $V$, which
already in Ref. 7 allowed us to rigorously treat any operator
$-\operatorname{div}A\nabla+V$ with an elliptic matrix of bounded measurable
coefficients $A$ and any non-negative bounded potential $V$, a level of the
generality not accessible within the classical Agmon theory. These ideas and
results have been extended to quantum graphs [11], to the tight-binding model
[12], and perhaps most notably, to many-body localization in Ref. 13.

This paper shows that the applicability of the landscape theory in fact
extends well beyond the scope of the Schrödinger operator, or, for that
matter, even the scope of PDEs, at least in the bottom of the spectrum where
the region $\\{\frac{1}{u}\leq E\\}$ exhibits isolated potential wells.
Indeed, let us now consider a general real symmetric positive definite
$N\times N$ matrix $A=(a_{ij})_{i,j\in[N]}$, which one can view as a self-
adjoint operator on the Hilbert space $\ell^{2}([N])$ on the domain
$[N]\coloneqq\\{1,\dots,N\\}$. In certain situations one expects $A$ to
exhibit “localization” in the following two related aspects, which we describe
informally as follows:

  * (i)

(Eigenvector localization) Each eigenvector 111One can also study the closely
related phenomenon of localization of Green’s functions $(A-z)^{-1}$. This
latter type of localization is also related to the spectrum of associated
infinite-dimensional operators consisting of pure point spectrum, thanks to
such tools as the Simons–Wolff criterion [14]. $\phi=(\phi_{k})_{k\in[N]}$ of
$A$ is localized to some index $i$ of $[N]$, so that $|\phi_{k}|$ decays when
$|k-i|$ exceeds some localization length $L\ll N$.

  * (ii)

(Poisson statistics) The local statistics of eigenvalues
$\lambda_{1},\dots,\lambda_{N}$ of $A$ asymptotically converge to a Poisson
point process in a suitably rescaled limit as $N\to\infty$.

Empirically, the phenomena (i) and (ii) are observed to occur in the same
matrix ensembles $A$; intuitively, the eigenvector localization property (i)
implies that $A$ “morally behaves like” a block-diagonal matrix, with the
different blocks of $A$ supplying “independent” sets of eigenvalues, thus
leading to the Poisson statistics in (ii). However, the two properties (i),
(ii) are not formally equivalent; for instance, conjugating $A$ by a generic
unitary matrix will most likely destroy property (i) without affecting
property (ii).

######  Example 1.1 (Gaussian band matrices).

Consider the random band matrix Gaussian models $A$, in which the entries
$a_{ij}$ are independent Gaussians for $1\leq i\leq j\leq N$ and $|i-j|\leq
W$, but vanish for $|i-j|>W$, for some $1\leq W\leq N$. We refer the reader to
Ref. 15 (§2.2) for a recent survey of this model. If the matrix is normalized
to have eigenvalues $E$ concentrated in the interval $[-2,2]$ (and expected to
obey the Wigner semicircular law
$\displaystyle\frac{1}{2\pi}(4-E^{2})_{+}^{1/2}$ for the asymptotic density of
states), it is conjectured (see e.g., Ref. 16) that the localization length
$L$ should be given by the formula

$L\sim\min(W^{2}(4-E^{2}),N);$

in particular, in the bulk of the spectrum, it is conjectured that
localization (in both senses (i), (ii)) should hold when $W\ll N^{1/2}$ (with
localization length $L\sim W^{2}$) and fail when $W\gg N^{1/2}$, while near
the edge of the spectrum (in which $4-E^{2}=O(L^{-2/3})$) localization is
expected to hold when $W\ll N^{5/6}$ and fail when $W\gg N^{5/6}$. Towards
this conjecture, it is known [17] in the bulk $4-E^{2}\sim 1$ that (i), (ii)
both fail when $W\gg N^{3/4+\varepsilon}$ for any fixed $\varepsilon>0$, while
localization in sense (i) was established for $W\ll N^{1/7}$ in Ref. 18 (see
also Ref. 19). In the edge $4-E^{2}=O(L^{-2/3})$, both directions of the
conjecture have been verified in sense (ii) in Ref. 20, but the conjecture in
sense (i) remains open. Finally, we remark that in the regime $W=O(1)$ the
classical theory of Anderson localization [21] can be used to establish both
(i) and (ii).

We now focus on the question of establishing eigenvector localization (i). Can
one deduce any uniform bound on the eigenvectors of a general matrix $A$
depicting, in particular, a structure of the exponential decay similarly to
the aforementioned considerations for a matrix of the Schrödinger operator
$-\Delta+V$? An immediate objection is that there is no “potential” that could
play the role of $V$. Even aside from the fact that the proof of the Agmon
decay relies on the presence of both kinetic and potential energy, as well as
on many PDE arguments, it is not clear whether there is a meaningful function,
analogous to $V$, which governs the behavior of eigenvectors of a general
matrix. The main result of this paper is that, surprisingly, the landscape
theory still works, at least in the class of real symmetric $Z$-matrices
(matrices with non-positive entries off the diagonal). Furthermore, when $A$
is a real symmetric non-singular $M$-matrix (a positive semi-definite
$Z$-matrix), the reciprocal $\frac{1}{u}$ of the solution to $Au=1$ gives rise
to a distance function $\rho$ on the index set $[N]$ which predicts the
exponential decay of the eigenvectors.

##  2\. Main results

We introduce an Agmon-type distance $\rho$ on the index set
$[N]\coloneqq\\{1,\dots,N\\}$ associated to an $N\times N$ matrix $A$, a
$N\times 1$ “landscape” vector $u$, and an additional spectral parameter
$E\in\mathbb{R}$:

######  Definition 2.1 (Distance).

Let $A=(a_{ij})_{i,j\in[N]}$ be a real symmetric $N\times N$ matrix, let
$u=(u_{i})_{i\in[N]}$ be a vector with all entries non-zero, and let $E$ be a
real number. We define the _effective potential_
$\overline{V}=(\overline{v}_{i})_{i\in[N]}$ by the formula

(2.2) $\overline{v}_{i}\coloneqq\frac{(Au)_{i}}{u_{i}},$

the _shifted effective potential_ by the formula

(2.3) $v_{i}\coloneqq\left(\overline{v}_{i}-E\right)_{+}$

(where $x_{+}\coloneqq\max(x,0)$), the _potential well set_ by the formula

$K_{E}\coloneqq\\{i\in[N]:v_{i}=0\\}=\left\\{i\in[N]:\frac{(Au)_{i}}{u_{i}}\leq
E\right\\},$

and the _distance function_
$\rho=\rho_{A,u,E}\colon[N]\times[N]\to[0,+\infty]$ by the formula

$\rho(i,j)\coloneqq\inf_{L\geq
0}\inf_{i_{0},\dots,i_{L}\in[N]:i_{0}=i,i_{L}=j}\left(\sum_{\ell=0}^{L}\ln\left(1+\sqrt{\frac{\sqrt{v_{i_{\ell}}v_{i_{\ell+1}}}}{|a_{i_{\ell}i_{\ell+1}}|}}\right)\right)$

where we restrict the infimum to those paths $i_{0},\dots,i_{L}$ for which
$a_{i_{\ell}i_{\ell+1}}\neq 0$ for $\ell=0,\dots,L-1$. To put it another way,
$\rho$ is the largest pseudo-metric such that

(2.4)
$\rho(i,j)\leq\ln\left(1+\sqrt{\frac{\sqrt{v_{i}v_{j}}}{|a_{ij}|}}\right)$

whenever $a_{ij}\neq 0$.

For any set $M\subset[N]$ we denote by $\rho(i,M)\coloneqq\inf_{j\in
M}\rho(i,j)$ the distance from a given index $i$ to $M$ using the distance
$\rho$ (with the convention that $\rho(i,M)=\infty$ if $M$ is empty).
Similarly, for any set $K\subset[N]$, we define $\rho(K,M)\coloneqq\inf_{i\in
K}\rho(i,M)$ for the separation between $K$ and $M$.

It is easy to see that $\rho$ is a pseudo-metric in the sense that it is
symmetric and obeys the triangle inequality with $\rho(i,i)=0$, although
without further hypotheses222For instance, if we assume that $A$ is
_irreducible_ in the sense that it cannot be expressed (after permuting
indices) as a block-diagonal matrix, then $\rho(i,j)$ will always be finite.
on $A,u,E$ it is possible that $\rho(i,j)$ could be zero or infinite for some
$i\neq j$. One can view $\rho$ as a weighted graph metric on the graph with
vertices $[N]$ and edges given by those pairs $(i,j)$ with $a_{ij}\neq 0$, and
with weights given by the right-hand side of (2.4). We discuss the comparison
between $\rho$ and the Euclidean metric in the beginning of Section 5.

We recall that a _$Z$ -matrix_ is any $N\times N$ matrix $A$ such that
$a_{ij}\leq 0$ when $i\neq j$, and a _$M$ -matrix_ is a $Z$-matrix with all
eigenvalues having non-negative real part. Our typical set-up is the case when
$A$ is a real symmetric non-singular $M$-matrix, i.e., a positive definite
matrix with non-positive off-diagonal entries, and in that case we will choose
$u$ as the landscape function, i.e., the solution to $Au=1$, with $1$ denoting
a vector with all values equal to $1$. We say that a matrix $A$ has
_connectivity_ at most ${W_{c}}$ if every row and column has at most ${W_{c}}$
non-zero non-diagonal entries. If $A$ is a real symmetric non-singular
$M$-matrix, all the principal minors are positive (see e.g., Ref. 22), and
hence by Cramér’s rule all the coefficients of the landscape $u$ will be non-
negative. In this case, a simple form of our main results is as follows.

######  Theorem 2.5 (Exponential localization using landscape function).

Let $A$ be a symmetric $N\times N$ $M$-matrix with connectivity at most
${W_{c}}$ for some ${W_{c}}\geq 2$. Let $u\coloneqq A^{-1}1$ be the landscape
function. Assume that $\varphi$ is an $\ell^{2}$-normalized eigenvector of $A$
corresponding to the eigenvalue $E$. Let $\rho=\rho_{A,u,E}$, $K=K_{E}$ be
defined by Definition 2.1. Then

$\sum_{k}\varphi_{k}^{2}\,e^{\frac{2\rho(k,K)}{\sqrt{{W_{c}}}}}\,\left(\frac{1}{u_{k}}-E\right)_{+}\leq{W_{c}}\max_{1\leq
i,j\leq N}|a_{ij}|.$

Informally, the above inequality ensures that an eigenvector $\varphi$
experiences exponential decay away from the wells of the effective potential
$\overline{V}=(\frac{1}{u_{k}})_{k\in[N]}$ cut off by the energy level $E$.
This is what typically happens for the Schrödinger operator $-\Delta+V$
(according to some version of the Agmon theory); see for instance [7,
Corollary 4.5]. However, the existence of such an effective potential for an
_arbitrary_ $M$-matrix is perhaps surprising.

In fact our results apply to the larger class of real symmetric $Z$-matrices
$A$ and more general vectors $u$, and can handle “local” eigenvectors as well
as “global” ones. We first introduce some more notation.

######  Definition 2.6 (Local eigenvectors).

Let $M\subset[N]$. We use $I_{M}$ to denote the $N\times N$ diagonal matrix
with $(I_{M})_{ii}$ equal to $1$ when $i\in M$ and $0$ otherwise. If
$\varphi\in\ell^{2}([N])$, we write $\varphi|_{M}\coloneqq I_{M}\varphi$ for
the restriction of $\varphi$ to $M$ (extending by zero outside of $M$), and
similarly if $A$ is an $N\times N$ matrix we write $A|_{M}\coloneqq
I_{M}AI_{M}$ for the restriction of $A$ to $M\times M$ (again extending by
zero). We say that a vector $\varphi\in\ell^{2}([N])$ is a _local eigenvector_
of $A$ on the domain $M$ with eigenvalue $E$ if $\varphi=\varphi|_{M}$ is an
eigenvector of $A|_{M}$ with eigenvalue $E$, thus $I_{M}\varphi=\varphi$ and
$I_{M}AI_{M}\varphi=E\varphi$.

To avoid confusion we shall sometimes refer to the original notion of an
eigenvector as a _global eigenvector_ ; this is the special case of a local
eigenvector in which $M=[N]$.

We can now state a more general form of Theorem 2.5.

######  Theorem 2.7 (Exponential localization).

Let $A$ be a symmetric $N\times N$ $Z$-matrix with connectivity at most
${W_{c}}$ for some ${W_{c}}\geq 2$, and let $u$ be some $n\times 1$ vector of
non-negative coefficients. Let $\overline{E}>0$ be an energy threshold, and
let $\rho=\rho_{A,u,\overline{E}}$, $v_{i}$, and $K_{\overline{E}}$ be defined
by Definition 2.1. Then for any subset $D$ of $[N]$ and any local eigenvector
$\varphi$ of $A$ of eigenvalue $E\leq\overline{E}$ on $D^{c}=[N]\setminus D$,
one has

(2.8) $(\overline{E}-E)\sum_{k\notin
K_{\overline{E}}}|\varphi_{k}|^{2}e^{2\alpha\rho(k,K_{\overline{E}}\setminus
D)}\\\ +\left(1-\frac{\alpha^{2}{W_{c}}}{2}\right)\sum_{k\notin
K_{\overline{E}}}|\varphi_{k}|^{2}e^{2\alpha\rho(k,K_{\overline{E}}\setminus
D)}v_{k}\\\ \leq\frac{{W_{c}}}{2}\|\varphi\|^{2}\max_{i\in
K_{\overline{E}}\setminus D,\,j\not\in K_{\overline{E}}\setminus D}|a_{ij}|,$

for any $0<\alpha\leq\sqrt{2/{W_{c}}}$. (Here and in the sequel we use
$\|\cdot\|$ to denote the $\ell^{2}([N])$ norm.)

In particular, if $\alpha=\sqrt{1/{W_{c}}}$, $\overline{E}=E$,
$D=\varnothing$, and $\varphi$ is an $\ell^{2}$-normalized (global)
eigenvector of $A$ on the entire domain $[N]$ with the eigenvalue $E$, (2.8)
implies that

(2.9)
$\sum_{k\in[N]}\varphi_{k}^{2}\,e^{\frac{2\rho(k,K_{E})}{\sqrt{{W_{c}}}}}\,v_{k}\leq{W_{c}}\max_{i,j\in[N]}|a_{ij}|.$

There are two terms on the left-hand side of (2.8), corresponding to two
different lines in the display, and they serve different purposes. The bound
for the term in the second line (which in particular yields (2.9)) asserts
roughly speaking that the eigenvector $\varphi_{k}$ experiences exponential
decay in the regime where $k$ is far from $K_{\overline{E}}$ in the sense that
$\rho(k,K_{\overline{E}})\gg\sqrt{{W_{c}}}$. Note that Theorem 2.5 is the
special case of (2.9) when $A$ is a $M$-matrix and $u=A^{-1}1$.

By taking advantage of the term in the first line of (2.8), we can proceed
further and demonstrate an approximate _diagonalization_ , or _decoupling_ ,
of $A$ on the collection of disjoint subregions defined by the landscape
function $u$, by following the arguments from Ref. 7. The details are too
technical to be put in the introduction, and we refer the reader to Section 5.
In short, the idea is that viewing $[N]$ as a graph induced by $A$ (with the
vertices connected whenever $a_{ij}\neq 0$), we can define a Voronoi-type
splitting of this graph into subgraphs, $\Omega_{\ell}$, each containing an
individual connected component of $K_{\overline{E}}$ (or sometimes merging a
few components if convenient). Then $A$ can be essentially decoupled into
smaller matrices $A|_{\Omega_{\ell}}$ with the strength of coupling
exponentially small in the $\rho_{A,u}$ distance between individual “wells”.
Related to this, the spectrum of $A$ will be exponentially close to the
combined spectrum of $A|_{\Omega_{\ell}}$’s.

Note how the geometry of the metric $\rho$ is sensitive to the spatial
distribution of the matrix $A$, and in particular to the connectivity
properties of the graph induced by the locations of the nonzero locations of
$A$. For instance, conjugating $A$ by a generic orthogonal matrix will almost
certainly destroy the localization of the eigenvectors $\varphi$, but will
also heavily scramble the metric $\rho$ (and most likely also destroy the
property of being an $M$-matrix or $Z$-matrix). On the other hand, conjugating
$A$ by a permutation matrix will simply amount to a relabeling of the
(pseudo-)metric space $([N],\rho)$, and not affect the conclusions of
Corollary 2.5 and the decoupling results in Theorem 5.2 and Corollary 5.5 in
any essential way.

We will show some results of the numerical simulations in the next section,
and then pass to the proofs, but let us say a few more words about the
particular cases which would perhaps be of most interest.

Random band matrices. Here the connectivity is ${W_{c}}=2W$. Strictly
speaking, the random Gaussian band matrix models $A$ considered in Example 1.1
do not fall under the scope of Corollary 2.5, because the matrices will not be
expected to have non-positive entries away from the diagonal, nor will they be
expected to be positive definite. However, one can modify the model to achieve
these properties (at least with high probability), by replacing the Gaussian
distributions by distributions supported on the negative real axis, and then
shifting by a suitable positive multiple of the identity to ensure positive
definiteness with high probability. These changes will likely alter the
semicircle law for the bulk distribution of eigenvalues, but in the spirit of
the universality phenomenon, one may still hope to see localization of
eigenvectors, say in the bulk of the spectrum, as long as the width $W$ of the
band matrix is small enough (in particular when $W\ll N^{1/2}$). In this case
Corollary 2.5 entails exponential decay of the eigenvectors governed by the
landscape $\frac{1}{u}$ and Theorem 5.2 and Corollary 5.5 yield the
corresponding diagonalization of $A$. Of course, the key question is the
behavior of the landscape. If the set $K_{\overline{E}}$ of wells is localized
to a short interval, then this corollary will establish localization in the
spirit of (i) above; however, if $K_{\overline{E}}$ is instead the union of
several widely separated intervals then an eigenvector could in principle
experience a resonance in which non-trivial portions of its $\ell^{2}$ energy
were distributed amongst two or more of these intervals. Whether or not this
happens is governed to some extent by Theorem 5.2 and Corollary 5.5. These
results indicate that the resonances have to be exponentially strong in the
distance between the wells, and our numerical experiments suggest that such
strong resonances are in fact quite rare.

Tight-binding Schrödinger operators. When $A$ is a matrix of the tight-binding
Schrödinger operator (a standard discrete Laplacian plus a potential) in a
cube in ${\mathbb{Z}}^{d}$, the connectivity parameter ${W_{c}}$ is now the
number of nearest neighbors, $2d$, and the size of the matrix is the
sidelength of the cube to the power $d$. If the potential is non-negative, $A$
is an $M$-matrix with the entries $a_{ij}$ equal to $-1$ whenever $i\neq j$
corresponds to the nearest neighbors in the graph structure induced by
${\mathbb{Z}}^{d}$, and $a_{ii}=2d+V_{i}$. This particular case has been
considered in Ref. 12 and our results clearly cover it. However, the tight-
binding Schrödinger is only one of many examples, even when concentrating on
applications in physics. We can treat any operator in the form
$-\mathrm{div}A\nabla+V$ on any graph structure, provided that the signs of
the coefficients yield an $M$-matrix. We can also address long range hopping
for a very wide class of Hamiltonians.

Many-body system and statistical physics. Much more generally, in statistical
physics, the probability distribution over all possible microstates (or the
density matrix in the quantum setting) of a given system evolves through
elementary jumps between microstates. This evolution is a Markov process whose
transition matrix is a $Z$-matrix which is symmetric up to a multiplication by
a diagonal matrix. For a micro-reversible evolution, the matrix $A$ is
symmetric and is akin to a weighted Laplacian on the high-dimensional indirect
graph whose vertices are the microstates and whose edges are the possible
transitions.

One essential result of statistical physics is that, under condition of
irreducibility of the transition matrix, the system eventually reaches
thermodynamical equilibrium. Our approach might open the way to unravel the
structure of the eigenvectors of the Markov flow, and thus to understand how
localization of these eigenvectors can induce a many-body system to remain
“frozen” for mesoscopic times out of equilibrium. This effect is referred to
as _many-body localization_. A first successful implementation of the
landscape theory in this context has been recently achieved by V. Galitski and
collaborators [13] for a many-body system of spins with nearest-neighbor
interaction. In this work, the authors cleverly use the ideas of Ref. 23 to
transfer the problem to the Fock space and to deduce an Agmon-type decay
governed by the corresponding effective potential. Once in the Fock space,
their results are also a particular case of Theorem 2.7 and Theorem 5.2. From
that point, however, the authors of Ref. 13 go much farther to discuss, based
on physical considerations, deep implications of such an exponential decay on
many-body localization, but in the present paper we restrict ourselves to
mathematics and will not enter those dangerous waters.

Finally, we would like to mention that the idea of trying the localization
landscape and similar concepts in the generality of random matrices has
appeared before, e.g., in Refs 24 and 25. However, the authors relied on a
different principle, extending the inequality $|\varphi|\leq Eu$ from Ref. 6
to these more general contexts, which by itself, of course, does not prove
exponential decay. Ref. 24 actually deals with a different proxy for the
landscape and different inequalities, but we (and the authors) believe that
these are related to the landscape and that, again, they do not prove
exponential decay estimates. However, we would like to mention that the
importance of $M$-matrices was already suggested in Ref. 25, and it was
inspiring and reassuring to arrive at the same setting from such different
points of view.

##  3\. Numerical simulations

We ran numerical simulations to compute the localization landscape $u$, the
effective potential $\frac{1}{u}$, and the eigenvectors for several
realizations of random symmetric $M$-matrices. The diagonal coefficients are
random variables which follow a centered normal law of variance 1. The off-
diagonal coefficients belonging to the first ${W_{c}}/2$ diagonals of the
upper triangle of the matrix are minus the absolute values of random variables
following the same law. The remaining off-diagonal coefficients of the upper
triangle are taken to be zero, and the lower triangle is completed by
symmetry. This creates $A_{0}$, a $Z$-matrix of bandwidth ${W_{c}}+1$ (and
connectivity ${W_{c}}$). To ensure positivity, we add a multiple of the
identity

(3.1) $A:=A_{0}+a~{}I\qquad\textrm{where}\qquad a=\varepsilon-\lambda_{0}~{},$

$\lambda_{0}$ being the smallest eigenvalue of $A_{0}$ and $\varepsilon=0.1$.
The smallest eigenvalue of the resulting matrix $A$ is thus $\varepsilon$. The
matrices $A$ and $A_{0}$ clearly have the same eigenvectors and their spectra
differ only by a constant shift.

Below are the results of several simulations. We take $N=10^{3}$. Figures 1-4
correspond to random symmetric $M$-matrices constructed as above of
connectivity ${W_{c}}=2$, $6$, $20$, and $32$. Each figure consists of two
frames:

The top frame displays the localization landscape $u$ superimposed with the
first $5$ eigenvectors plotted in $\log_{10}$ scale. The exponential decay of
the eigenvectors can clearly be observed on this frame for ${W_{c}}=2$, $6$,
and $20$. One can see that, as expected, it starts disappearing around
${W_{c}}=32$ (${W_{c}}$ being in this case roughly equal to $\sqrt{N}$). It is
important to observe that in all cases the eigenvectors decay exponentially
except for the wells of $\frac{1}{u}$ (equivalently, the peaks of $u$) where
they stay flat. This is exactly the prediction of Theorem 2.7.

The bottom frame displays the effective potential $\frac{1}{u}$ superimposed
with the first $5$ eigenvectors plotted in linear scale. The horizontal lines
indicate the energies of the corresponding eigenvectors. One can clearly see
the localization of the eigenvectors inside the wells of the effective
potential.

Figure 1. (a) Localization landscape (blue line) and the $5$ first
eigenvectors (in $\log_{10}$ scale) for a random $3$-band symmetric
$M$-matrix. (b) Effective potential ($\frac{1}{u}$) and the first eigenvectors
(in linear scale). The baseline (the 0 of the vertical axis) is chosen
differently for each eigenvector so that it coincides with the eigenvalue of
the same eigenvector of the left axis. This convention will be used in all
Figures 1 to 4. Figure 2. (a) Localization landscape (blue line) and the $5$
first eigenvectors (in $\log_{10}$ scale) for a random $7$-band symmetric
$M$-matrix. (b) Effective potential ($\frac{1}{u}$) and the first eigenvectors
(in linear scale) Figure 3. (a) Localization landscape (blue line) and the $5$
first eigenvectors (in $\log_{10}$ scale) for a random $21$-band symmetric
$M$-matrix. (b) Effective potential ($\frac{1}{u}$) and the first eigenvectors
(in linear scale). Figure 4. (a) Localization landscape (blue line) and the
$5$ first eigenvectors (in $\log_{10}$ scale) for a random $33$-band symmetric
$M$-matrix. (b) Effective potential ($\frac{1}{u}$) and the first eigenvectors
(in linear scale).

Figure 5 provides numerical evidence for finer effects encoded in Theorems 2.7
and 5.2. The two Theorems combined prove exponential decay away from the wells
of the effective potential governed the Agmon distance associated to $1/u$, at
least in the absence of resonances. In Figure 5 we display, for several values
of connectivity ${W_{c}}$ and several eigenvectors, the values
$-\ln|\psi_{i}|$ against the distance $\rho_{A,u,E}(i,i_{\max})$, taking as
the origin the point $i_{\max}$ where $|\psi|$ is maximal, and using the
corresponding eigenvalue as the threshold $E$. The linear correspondence down
to $e^{-40}$ is quite remarkable and shows that
$e^{-c\rho_{A,u,E}(i,i_{\max})}$ is not only an upper bound, but actually an
approximation of the eigenfunction, and that the resonances are indeed
unlikely. On the other hand, the constant $c$ does not appear to be equal to
$1/\sqrt{{W_{c}}}$ which means that in this respect our analysis is probably
not optimal, at least in the class of random matrices. Indeed, we believe that
the application of the deterministic Schur test in the proof does not yield
the best possible constant for random coefficients, but since we emphasize the
universal deterministic results, this step cannot be further improved.

Figure 5. Scatter plots of the logarithm of the absolute value of several
eigenvectors against the corresponding Agmon distance, for 3 different values
of the connectivity ${W_{c}}=2$, 6, and 20 (frames (a), (b), and (c)). For
each eigenvector (eigenvectors #1, 2, and 5 in each frame), we display
$-\ln|\psi_{i}|$ at any given point $i$ vs. the Agmon distance between the
point $i$ and the location where $|\psi|$ is maximal. The plots exhibit a
strong linear relationship between these two quantities, down to values of
$|\psi_{i}|$ around $e^{-40}$ (of the order of $10^{-18}$), which is a
signature of the exponential decay. The slope seems to depend only on $W_{c}$.

Finally, Figure 6 shows that Hypothesis 5.1 is actually fulfilled in some
realistic situations. The top frame displays the example already presented in
Figure 2. Superimposed to the eigenvectors, the set $K_{E}$ introduced in
Definition 2.1 is also drawn (grey rectangles) for $E=0.7$ (horizontal dashed
red line). The middle frame displays the plot of the Agmon distance to
$K_{E}$. Thresholding this plot at $S=2$ (green horizontal line) allows us to
draw the $S$-neighborhood of $K_{E}$ (the orange rectangles). The bottom frame
shows a possible partition of the entire domain into five subdomains
($\Omega_{1},\cdots,\Omega_{5}$), each subdomain containing at least one well
of the effective potential $1/u$. The distances
$\rho(\partial^{-}\Omega_{\ell},K_{\ell})$ defined in Hypothesis 5.1 are here
respectively 48.1584, 2.8093, 4.2169, 3.6784, 9.3756. They all are larger than
$S$, thus satisfying Hypothesis 5.1 .

Figure 6. (a) Eigenvectors in log scale, superimposed with the set $K_{E}$
defined in 2.1 (grey rectangles) for the value $E=0.7$ (indicated by the red
dashed line). (b) Plot of the Agmon distance of each point to the set $K_{E}$.
The orange rectangles correspond to the $S$-neighborhood of $K_{E}$ for $S=2$
(indicated by the green horizontal line). (c) Partition of the domain in five
subdomains. All distances $\rho(\partial^{-}\Omega_{\ell},K_{\ell})$ defined
in 5.1 are larger than $S$. This partition thus fulfills Hypothesis 5.1.

To be more precise, let us turn to the exact statements.

##  4\. The proof of the main results

In this section we prove Theorem 2.7. We will use a double commutator method.
Let $[A,B]\coloneqq AB-BA$ denote the usual commutator of $N\times N$
matrices, and $\langle,\rangle$ the usual inner product on $\ell^{2}([N])$. We
observe the general identity

(4.1) $\langle[[A,D],D]u,u\rangle=\sum_{i,j\in[N]:i\neq
j}a_{ij}u_{i}u_{j}(d_{ii}-d_{jj})^{2}.$

whenever $A=(a_{ij})_{i,j\in[N]}$ is a matrix,
$D=\mathrm{diag}(d_{11},\dots,d_{nn})$ is a diagonal matrix, and
$u=(u_{i})_{i\in[N]}$ is a vector. In particular we have

(4.2) $\langle[[A,D],D]u,u\rangle\leq 0$

whenever $A$ is a $Z$-matrix and the entries of $u$ have constant sign. It
will be this negative definiteness property that is key to our arguments. One
can compare (4.1), (4.2) to the Schrödinger operator identity

$\langle[[-\Delta+V,g],g]u,u\rangle=-2\int_{\mathbb{R}^{d}}|\nabla
g|^{2}|u|^{2}\leq 0$

for any (sufficiently well-behaved) functions
$V,g,u:\mathbb{R}^{d}\to\mathbb{R}$.

To exploit (4.1) we will use the following identity.

######  Lemma 4.3 (Double commutator identity).

Let $A,\Psi,G$ be $N\times N$ real symmetric matrices such that $\Psi
G=G\Psi$, and suppose that $u$ is an $N\times 1$ vector. Then

$\langle G[\Psi,A]u,G\Psi
u\rangle=\frac{1}{2}\langle[[A,G\Psi],G\Psi]u,u\rangle-\frac{1}{2}\langle[[A,G],G]\Psi
u,\Psi u\rangle.$

###### Proof.

By the symmetric nature of $G$ we have

$\langle[[A,G],G]\Psi u,\Psi u\rangle=2\langle GA\Psi u,G\Psi
u\rangle-2\langle AG\Psi u,G\Psi u\rangle$

and similarly from the symmetric nature of $G\Psi$ we have

$\langle[[A,G\Psi],G\Psi]u,u\rangle=2\langle G\Psi Au,G\Psi u\rangle-2\langle
AG\Psi u,G\Psi u\rangle.$

The claim follows. ∎

We can now conclude

######  Corollary 4.4.

Let $A=(a_{ij})_{i,j\in[N]}$ be a $N\times N$ real symmetric $Z$-matrix.
Assume that $D$ is some subset of $[N]$ and that $\varphi$ is a local
eigenvector of $A$ corresponding to the eigenvalue $E$ on $D^{c}=[N]\setminus
D$. Let $u=(u_{i})_{i\in[N]}$ be a vector with all positive entries, and let
$G=\mathrm{diag}(G_{11},\dots,G_{NN})$ be a real diagonal matrix. Then

(4.5)
$\sum_{k\in[N]}\varphi_{k}^{2}G_{kk}^{2}\left(\frac{(Au)_{k}}{u_{k}}-E\right)\leq-\frac{1}{2}\sum_{i,j\in[N]:i\neq
j}a_{ij}\varphi_{i}\varphi_{j}(G_{ii}-G_{jj})^{2}.$

###### Proof.

Writing $[\Psi,A]=\Psi(A-EI)-(A-EI)\Psi$, we apply Lemma 4.3 with
$\Psi\coloneqq\mathrm{diag}(\varphi_{1}/u_{1},\dots,\varphi_{N}/u_{n})$, to
get

$\langle G\Psi(A-EI)u,G\Psi u\rangle-\langle G(A-EI)\Psi u,G\Psi u\rangle\\\
=\frac{1}{2}\langle[[A,G\Psi],G\Psi]u,u\rangle-\frac{1}{2}\langle[[A,G],G]\Psi
u,\Psi u\rangle.$

By (4.2) the first term on the right-hand side above is non-positive and
hence, the entire expression is less than or equal to

$-\frac{1}{2}\langle[[A,G],G]\Psi u,\Psi
u\rangle\leq-\frac{1}{2}\sum_{i,j\in[N]:i\neq
j}a_{ij}\varphi_{i}\varphi_{j}(G_{ii}-G_{jj})^{2}.$

The latter inequality follows from (4.1) and the fact that by definition $\Psi
u=\varphi$.

Since $G$ is diagonal, and $\varphi=\Psi u$ is a local eigenvector on $D^{c}$,
the second term on the left-hand side is equal to zero. Indeed, $(\Psi
u)_{k}=(G\Psi u)_{k}=0$ for $k\in D$, and hence

$\langle G(A-EI)\Psi u,G\Psi u\rangle=\langle G(A-EI)|_{D^{c}}\Psi u,G\Psi
u\rangle=0.$

Writing

$\Psi(A-EI)u=\left(\left(\frac{(Au)_{k}}{u_{k}}-E\right)\varphi_{k}\right)_{k\in[N]}$

the claim follows. ∎

The strategy is then to apply this corollary with a sufficiently slowly
varying function $G$, so that one can hope to mostly control the right-hand
side of (4.5) by the left-hand side.

Proof of Theorem 2.7. We abbreviate $K_{\overline{E}}$ as $K$ for simplicity.
We can of course assume that $\varphi$ is not identically zero. If $K\setminus
D$ was empty we could apply Corollary 4.4 with $G_{kk}=1$ to obtain a
contradiction, so we may assume without loss of generality that $K\setminus D$
is non-empty. We apply Corollary 4.4 with

$G_{ii}\coloneqq 1_{i\not\in K\setminus
D}\,e^{\alpha\rho_{A,u,\overline{E}}(i,K\setminus D)},$

where the indicator $1_{i\not\in K\setminus D}$ is equal to zero for $i\in
K\setminus D$ and equal to $1$ otherwise. By construction, $G_{kk}$ vanishes
for $k\in K\setminus D$, and $\varphi$ vanishes on $D$, so that
$G_{kk}\varphi_{k}$ vanishes on $K$. Thus by (2.3)

(4.6) $\begin{split}\left(\overline{E}-E\right)&\sum_{k\notin
K}\varphi_{k}^{2}e^{2\alpha\rho(i,K)}+\sum_{k\notin
K}\varphi_{k}^{2}e^{2\alpha\rho(i,K)}v_{k}\\\ &=\sum_{k\notin
K}\varphi_{k}^{2}G_{kk}^{2}\left(\overline{E}-E\right)+\sum_{k\notin
K}\varphi_{k}^{2}G_{kk}^{2}\left(\frac{(Au)_{k}}{u_{k}}-\overline{E}\right)_{+}\\\
&=\sum_{k\notin
K}\varphi_{k}^{2}G_{kk}^{2}\left(\overline{E}-E\right)+\sum_{k\notin
K}\varphi_{k}^{2}G_{kk}^{2}\left(\frac{(Au)_{k}}{u_{k}}-\overline{E}\right)\\\
&=\sum_{k\in[N]}\varphi_{k}^{2}G_{kk}^{2}\left(\frac{(Au)_{k}}{u_{k}}-E\right)\\\
&\leq-\frac{1}{2}\sum_{i,j\in[N]:a_{ij}\neq 0;i\neq
j}a_{ij}\varphi_{i}\varphi_{j}(G_{ii}-G_{jj})^{2}.\end{split}$

Now we need to estimate the quantity $G_{ii}-G_{jj}$ whenever $a_{ij}\neq 0$.
We first observe from the triangle inequality and (2.4) that

$\displaystyle|e^{\alpha\rho(i,K\setminus D)}-e^{\alpha\rho(j,K\setminus D)}|$
$\displaystyle\leq e^{\alpha\rho(i,K\setminus
D)}\left(e^{\alpha\rho(i,j)}-1\right)$ $\displaystyle\leq
e^{\alpha\rho(i,K\setminus
D)}\left(\left(1+\sqrt{\frac{\sqrt{v_{i}v_{j}}}{|a_{ij}|}}\right)^{\alpha}-1\right)$
$\displaystyle\leq e^{\alpha\rho(i,K\setminus
D)}\alpha\sqrt{\frac{\sqrt{v_{i}v_{j}}}{|a_{ij}|}}$

and similarly with $i$ and $j$ reversed; in particular

$|e^{\alpha\rho(i,K\setminus D)}-e^{\alpha\rho(j,K\setminus
D)}|^{2}\leq\alpha^{2}e^{\alpha\rho(i,K\setminus D)}e^{\alpha\rho(j,K\setminus
D)}\frac{\sqrt{v_{i}v_{j}}}{|a_{ij}|}.$

Thus we have

(4.7) $(G_{ii}-G_{jj})^{2}\leq\alpha^{2}e^{\alpha\rho(i,K\setminus
D)}e^{\alpha\rho(j,K\setminus D)}\frac{\sqrt{v_{i}v_{j}}}{|a_{ij}|}$

when $i,j\not\in K\setminus D$.

Next, suppose that $i\not\in K\setminus D$, $j\in K\setminus D$. Then
$G_{jj}=0$, and from (2.4) we have

$\displaystyle\rho(i,K\setminus D)$ $\displaystyle\leq\rho(i,j)$
$\displaystyle\leq\ln\left(1+\sqrt{\frac{\sqrt{v_{i}v_{j}}}{|a_{ij}|}}\right)$
$\displaystyle=0$

since $v_{j}=0$. We conclude that $(G_{ii}-G_{jj})^{2}=1$ in this case.
Similarly if $i\in K\setminus D$ and $j\not\in K\setminus D$. Finally, if
$i,j\in K\setminus D$ then $G_{ii}=G_{jj}=0$, so that $(G_{ii}-G_{jj})^{2}=0$
in this case. Applying all of these estimates, we can bound the right-hand
side of (4.6) by

(4.8) $\begin{split}&\frac{\alpha^{2}}{2}\sum_{i,j\not\in K\setminus D:i\neq
j;\,\,a_{ij}\neq 0}|\varphi_{i}||\varphi_{j}|e^{\alpha\rho(i,K\setminus
D)}e^{\alpha\rho(j,K\setminus D)}\sqrt{v_{i}v_{j}}\\\
&\quad+\frac{1}{2}\sum_{i\in K\setminus D;j\not\in K\setminus D\hbox{ or
}i\not\in K\setminus D,j\in K\setminus D;\,\,a_{ij}\neq
0}|a_{ij}||\varphi_{i}||\varphi_{j}|.\end{split}$

Since $A$ has at most ${W_{c}}$ non-zero non-diagonal entries in each row and
column, we see from Schur’s test (or the Young inequality
$ab\leq\frac{1}{2}a^{2}+\frac{1}{2}b^{2}$) that

$\sum_{i,j\not\in K\setminus D:i\neq j;\,\,a_{ij}\neq
0}|\varphi_{i}||\varphi_{j}|e^{\alpha\rho(i,K\setminus
D)}e^{\alpha\rho(j,K\setminus
D)}\frac{\sqrt{v_{i}v_{j}}}{|a_{ij}|}\leq{W_{c}}\sum_{i\not\in K\setminus
D}|\varphi_{i}|^{2}e^{2\alpha\rho(i,K\setminus D)}v_{i}$

and

$\sum_{i\in K\setminus D;j\not\in K\setminus D\hbox{ or }i\not\in K\setminus
D,j\in K\setminus D;a_{ij}\neq
0}|a_{ij}||\varphi_{i}||\varphi_{j}|\leq{W_{c}}(\sup_{i\in K\setminus
D;j\not\in K\setminus D}|a_{ij}|)\sum_{i\in[N]}|\varphi_{i}|^{2}.$

Combining all of the above considerations, we arrive at the conclusion of the
theorem. $\Box$

##  5\. Diagonalization

Let the notation and hypotheses be as in Theorem 2.7. We abbreviate
$\rho=\rho_{A,u,\overline{E}}$ and $K=K_{\overline{E}}$. To illustrate the
decoupling phenomenon we place the following hypothesis on the potential well
set $K$:

######  Hypothesis 5.1 (Separation hypothesis).

There exists a parameter $S>0$, a partition $K=\bigcup_{\ell}K_{\ell}$ of $K$
into disjoint “wells” $K_{\ell}$, and “neighborhoods” $\Omega_{\ell}\supset
K_{\ell}$ of each well $K_{\ell}$ obeying the following axioms:

  * (i)

The neighborhoods $\Omega_{\ell}$ are all disjoint.

  * (ii)

The neighborhoods $\Omega_{\ell}$ contain the $S$-neighborhood of $K_{\ell}$,
thus $\rho(\Omega_{\ell}^{c},K_{\ell})\geq S$.

  * (iii)

For any $\ell$, we have $\rho(\partial^{-}\Omega_{\ell},K_{\ell})\geq S$,
where the inner boundary $\partial^{-}\Omega_{\ell}$ is defined as the set of
all $k\in\Omega_{\ell}$ such that $a_{kj}\neq 0$ for some
$j\notin\Omega_{\ell}$.

We remark that axioms (i), (ii), (iii) imply that the full boundary
$\partial\Omega_{\ell}$, defined as the union of the inner boundary
$\partial^{-}\Omega_{\ell}$ and the outer boundary $\partial^{+}\Omega_{\ell}$
consisting of those $j\notin\Omega_{\ell}$ such that $a_{kj}\neq 0$ for some
$k\in\Omega_{\ell}$, stays at a distance at $S$ from $K$, since every element
of an outer boundary $\partial^{+}\Omega_{\ell}$ either lies in the inner
boundary of another $\Omega_{\ell^{\prime}}$, or else lies outside of all of
the $\Omega_{\ell^{\prime}}$. We also remark that axiom (iii) is a
strengthening of axiom (ii), since if there was an element $k$ in
$\Omega_{\ell}^{c}$ at distance less than $S$ from $K_{\ell}$ then by taking a
geodesic path from $K_{\ell}$ to $k$ one would eventually encounter a
counterexample to (iii), but we choose to retain explicit mention of axiom
(ii) to facilitate the discussion below.

Informally, to obey Hypothesis 5.1, one should first partition $K$ into
“connected components” $K_{\ell}$, concatenating two such components together
if their separation $\rho$ is too small, so that the separation
$\overline{S}\coloneqq\inf_{\ell\neq\ell^{\prime}}\rho(K_{\ell},K_{\ell^{\prime}})$
is large, and then perform a Voronoi-type partition in which $\Omega_{\ell}$
consists of those $k\in[N]$ which lie closer to $K_{\ell}$ in the $\rho$
metric than any other $K_{\ell^{\prime}}$. The axioms (i), (ii) would then be
satisfied for any $S<\overline{S}/2$ thanks to the triangle inequality, and
when $\overline{S}$ is large one would expect axiom (iii) to also be obeyed if
we reduce $S$ slightly. It seems plausible that one could weaken the axiom
(iii) and still obtain decoupling results comparable to those presented here,
but in this paper we retain this (relatively strong) axiom in order to
illustrate the main ideas.

We have already demonstrated in Section 3 non-vacuousness of Hypothesis 5.1,
at least in typical numerical examples. Let us say a few more words in this
direction. Recall the simulations in Section 3. Much as there, let us assume
for the moment that we are working with a band matrix and $W$ is the band
width, that is, $a_{ij}=0$ whenever $|i-j|>W$. One can deduce a rather trivial
lower bound for the Agmon distance associated to $v$ as in Definition 2.1. If
$v_{i}\geq v_{min}$ for all $i$ in an interval
$I=[i_{1},i_{q}]\cup{\mathbb{N}}$ of length $q$, then the Agmon distance
between two components of the complement of $I$

$\rho(i_{1}-1,i_{q}+1)\geq\Bigl{\lfloor}\frac{i_{q}-i_{1}+1-W}{W}\Bigr{\rfloor}\ln\left(1+\sqrt{\frac{v_{min}}{\max_{i,j\in[N]}a_{ij}}}\right).$

Here, the lower bracket as usual stands for the floor function. The above
inequality follows directly from the observation that the number of non-
trivial components such that $v_{i_{\ell}}\neq 0$ and $v_{i_{\ell+1}}\neq 0$
and $a_{i_{\ell}i_{\ell+1}}\neq 0$ of the path from $i_{1}-1$ to $i_{q}+1$ is
at least $\Bigl{\lfloor}\frac{i_{q}-i_{1}+1-W}{W}\Bigr{\rfloor}$. Going back
to our definitions, and fixing some $\overline{E}>E$ and the respective
partition of $K_{\overline{E}}=\cup_{\ell}K_{\ell}$ into disjoint components,
we denote by $d$ the minimal “Euclidean” distance between the components,
i.e.,

$d:=\min_{\ell}\min_{i\in K_{\ell},\,j\in K_{\ell+1}}|i-j|.$

It is in our interest to make this distance (or rather the corresponding Agmon
distance) substantial, so we might combine several disjoint components into
one $K_{\ell}$. With this at hand, we choose $\Omega_{\ell}$ to be maximal
possible neighborhoods of $K_{\ell}$ which are still disjoint. Since the inner
boundary $\partial^{-}\Omega_{\ell}$ consists of $i\in\Omega_{\ell}$ such that
$j\not\in\Omega_{\ell}$ and $a_{ij}\neq 0$, that is, has “width” at most $W$,
one can see that with the aforementioned choices the “Euclidean” distance
between $K_{\ell}$ and $\partial^{-}\Omega_{\ell}$

$\min_{i\in K_{\ell},\,j\in\partial^{-}\Omega_{\ell}}\geq\frac{d}{2}-W,$

or, to be more precise, $\Bigl{\lfloor}\frac{d+1}{2}\Bigr{\rfloor}-W.$ By
design, the complement of $K_{\ell}$ in $\Omega_{\ell}$ consists of points
such that $v_{i}>\bar{E}$, that is, there is $v_{min}>0$ such that $v>v_{min}$
in $\Omega_{\ell}\setminus(\partial^{-}\Omega_{\ell}\cup K_{\ell})$. Hence, at
the very least, for this $v_{min}>0$ we have

$\rho(\partial^{-}\Omega_{\ell},K_{\ell})\geq\Bigl{\lfloor}\frac{d/2-2W-1}{W}\Bigr{\rfloor}\ln\left(1+\sqrt{\frac{v_{min}}{\max_{i,j\in[N]}a_{ij}}}\right).$

Clearly, we could take a smaller subinterval of
$\Omega_{\ell}\setminus(\partial^{-}\Omega_{\ell}\cup K_{\ell})$ and make
$v_{min}>0$ larger, not to mention that this is a trivial lower estimate which
does not take into account high values of $v$. In any case, this demonstrates
that Hypothesis 5.1 is non-vacuous.

Let $\psi^{j}$ denote the complete system of orthonormal eigenvectors of $A$
on $[N]$ with eigenvalues $\lambda_{j}$. Let $\Psi_{(a,b)}$ denote the
orthogonal projection in $\ell^{2}([N])$ onto the span of eigenvectors
$\psi^{j}$ with eigenvalue $\lambda_{j}\in(a,b)$. For a fixed $\ell$ let
$\varphi^{\ell,j}$ denote a complete orthonormal system of the local
eigenvectors of $A$ on $\Omega_{\ell}$ with eigenvalues $\mu_{\ell,j}$, and
let $\Phi_{(a,b)}$ be the orthogonal projection onto the span of the
eigenvectors $\varphi^{\ell,j}$ with eigenvalue $\mu_{\ell,j}\in(a,b)$, over
all $\ell$ and $j$.

The goal of this section is to prove that under the assumption of Hypothesis
5.1, $A$ can be almost decoupled according to $\bigcup_{\ell}\Omega_{\ell}$,
with the coupling exponentially small in $S$. More precisely, we have the
following result, which is an analogue of [7, Theorem 5.1] in the $M$-matrix
setting.

######  Theorem 5.2 (Decoupling theorem).

Assume Hypothesis 5.1. Fix $\delta>0$ and let $\varphi$ be one of the local
eigenvectors $\varphi^{\ell,j}$ with eigenvalue $\mu=\mu_{\ell,j}$ and
$\mu\leq\overline{E}-\delta$. Then

(5.3)
$\|\varphi-\Psi_{(\mu-\delta,\mu+\delta)}\varphi\|^{2}\leq\frac{{W_{c}}^{2}}{\delta^{3}}\,\max_{i,j\in[N]}|a_{i,j}|^{3}\,e^{-\frac{2S}{\sqrt{W_{c}}}}\|\varphi\|^{2}\,.$

Conversely, if $\psi$ is one of the global eigenvectors $\psi^{j}$ with
eigenvalue $\lambda=\lambda_{j}\leq\overline{E}-\delta$, then

(5.4)
$\|\psi-\Phi_{(\lambda-\delta,\lambda+\delta)}\psi\|^{2}\leq\frac{{W_{c}}^{2}}{\delta^{3}}\,\max_{i,j\in[N]}|a_{i,j}|^{3}\,e^{-\frac{2S}{\sqrt{W_{c}}}}\|\psi\|^{2}\,.$

Proof. We mimic the arguments from Ref. 7. Let us consider the residual vector

$r\coloneqq A\varphi-\mu\varphi=(A-A|_{\Omega_{\ell}})\varphi.$

Note that the expression $(A-A|_{\Omega_{\ell}})\varphi$ only depends on the
values of $\varphi$ in the boundary region $\partial\Omega_{\ell}$. From
Schur’s test one thus has

$\|r\|\leq{W_{c}}^{1/2}\max_{i,j\in[N]}|a_{i,j}|\,\|\varphi\|_{\ell^{2}(\partial\Omega_{\ell})}.$

We apply Theorem 2.7 with $E=\mu$ and $D=\Omega_{\ell}^{c}$, so that
$K\setminus D=K\cap\Omega_{\ell}=K_{\ell}$ and $\rho(k,K\setminus
D)=\rho(k,K_{\ell})\geq S$ for all $k\in\partial\Omega_{\ell}$ by Hypothesis
5.1, which then yields

$\|\varphi\|_{\ell^{2}(\partial\Omega_{\ell})}^{2}\leq e^{-2\alpha
S}\,\frac{1}{\overline{E}-\mu}\,\frac{{W_{c}}}{2}\max_{i,j\in[N]}|a_{i,j}|\,\|\varphi\|^{2}.$

Taking $\alpha\coloneqq\sqrt{2/{W_{c}}}$ and recalling that
$\overline{E}-\mu>\delta$, we have

$\|r\|^{2}\leq\frac{1}{\delta}\,\frac{{W_{c}}^{2}}{2}\max_{i,j\in[N]}|a_{i,j}|^{3}\,e^{-\frac{2S}{\sqrt{W_{c}}}}\|\varphi\|^{2}.$

From the spectral theorem one has

$\|r\|^{2}\geq\delta^{2}\|\varphi-\Psi_{(\mu-\delta,\mu+\delta)}\varphi\|^{2}$

and the claim (5.3) follows.

The proof of (5.4) is somewhat analogous. Let us define the residual vector

$\widetilde{r}\coloneqq\sum_{\ell}(A|_{\Omega_{\ell}}-\lambda
I)\psi|_{\Omega_{\ell}}=\sum_{\ell}I_{\Omega_{\ell}}[A,I_{\Omega_{\ell}}]\psi$

where the matrices $I_{\Omega_{\ell}}$ were defined in Definition 2.6. The
values $(I_{\Omega_{\ell}}[A,I_{\Omega_{\ell}}])_{ik}$ are only non-zero when
$a_{ik}\neq 0$ and $i,k\in\partial\Omega_{\ell}$. In particular, by Hypothesis
5.1, we have $\rho(k,K)\geq S$, and $\tilde{r}$ only depends on the values of
$\psi$ outside of the $S$-neighborhood of $K$. Applying Theorem 2.7 with
$E=\lambda$ and $D=\varnothing$ and applying Schur’s test as before, we
conclude that

$\|\widetilde{r}\|^{2}\leq\frac{1}{\delta}\,\frac{{W_{c}}^{2}}{2}\max_{i,j\in[N]}|a_{i,j}|^{3}\,e^{-\frac{2S}{\sqrt{W_{c}}}}\|\varphi\|^{2}.$

On the other hand, from the spectral theorem we have

$\displaystyle\|\widetilde{r}\|^{2}$
$\displaystyle=\sum_{\ell}\|(A|_{\Omega_{\ell}}-\lambda
I)\psi_{\Omega_{\ell}}\|^{2}$
$\displaystyle\geq\delta^{2}\|\psi-\Phi_{(\lambda-\delta,\lambda+\delta)}\psi\|^{2}$

and the claim (5.4) follows. $\Box$

The theorem above assures that $A$ can be essentially decoupled on the union
of $\Omega_{\ell}$’s in the sense that the eigenvectors of $A$ are
exponentially close to the span of the eigenvectors of $A|_{\Omega_{\ell}}$,
and vice versa. A direct corollary of this result is that the eigenvalues of
$A$ are also exponentially close to the combined spectrum of
$A|_{\Omega_{\ell}}$ over all $\ell$:

######  Corollary 5.5.

Assume Hypothesis 5.1. Fix some $\delta>0$. Consider the counting functions

$N(\lambda)\coloneqq\\#\\{\lambda_{j}:\lambda_{j}\leq\lambda\\};\quad
N_{0}(\mu)\coloneqq\\#\\{\mu_{\ell,j}:\mu_{\ell,j}\leq\mu\\}.$

Assume that $\mu\leq\overline{E}$ and choose a natural number $\bar{N}$ such
that

$\frac{{W_{c}}^{2}}{\delta^{3}}\,\max_{i,j\in[N]}|a_{i,j}|^{3}\,\bar{N}<e^{\frac{2S}{\sqrt{W_{c}}}}.$

Then

(5.6) $\min(\bar{N},N_{0}(\mu-\delta))\leq
N(\mu)\quad\mbox{and}\quad\min(\bar{N},N(\mu-\delta))\leq N_{0}(\mu).$

###### Proof.

Consider the first $p$ unit eigenvectors $\psi^{1},\dots,\psi^{p}$ of $A$,
where $p\coloneqq\min(\bar{N},N(\mu-\delta))$. By definition of the counting
function, the eigenvalues $\lambda_{1},\dots,\lambda_{p}$ of these eigenvalues
are less than $\mu-\delta$. Applying the second conclusion of Theorem 5.2, we
conclude that

$\|\psi^{k}-\Phi_{(0,\mu)}\psi^{k}\|^{2}\leq\frac{{W_{c}}^{2}}{\delta^{3}}\,\max_{i,j\in[N]}|a_{i,j}|^{3}\,e^{-\frac{2S}{\sqrt{W_{c}}}}$

for $k=1,\dots,p$, Hence, for any nonzero linear combination
$\psi=\sum_{j=1}^{p}\alpha_{j}\psi_{j}$, we have

$\displaystyle\|\psi-\Phi_{(0,\mu)}\psi\|$
$\displaystyle\leq\sum_{j}|\alpha_{j}|\|\psi^{j}-\Phi_{(0,\mu)}\psi^{j}\|$
$\displaystyle\leq\Big{(}\frac{{W_{c}}^{2}}{\delta^{3}}\,\max_{i,j\in[N]}|a_{i,j}|^{3}\,e^{-\frac{2S}{\sqrt{W_{c}}}}\Big{)}^{1/2}\|\psi\|p^{1/2}$
$\displaystyle\leq\Big{(}\frac{{W_{c}}^{2}}{\delta^{3}}\,\max_{i,j\in[N]}|a_{i,j}|^{3}\,e^{-\frac{2S}{\sqrt{W_{c}}}}\bar{N}\Big{)}^{1/2}\|\psi\|$
$\displaystyle<\|\psi\|.$

It follows that the restriction of $\Phi_{(0,\mu)}$ to the span of the
$\psi^{j}$, $j=1,\,\dots,\,p$, is injective, and hence the rank $N_{0}(\mu)$
of the matrix $\Phi_{(0,\mu)}$ is at least $p$. In other words,
$N_{0}(\mu)\geq p$. This establishes the latter inequality in (5.6); the
former one is established similarly. ∎

Acknowledgments

We are thankful to Guy David for many discussions in the beginning of this
project and to Sasha Sodin for providing the literature and context with
regard to the edge state localization.

M. Filoche is supported by the Simons foundation grant 601944. S. Mayboroda
was partly supported by the NSF RAISE-TAQS grant DMS-1839077 and the Simons
foundation grant 563916. T. Tao is supported by NSF grant DMS-1764034 and by a
Simons Investigator Award.

Data availability

The data that support the findings of this study are available from the
corresponding author upon reasonable request.

## References

  * [1] S. Agmon.  Lectures on exponential decay of solutions of second-order elliptic equations: bounds on eigenfunctions of N-body Schrödinger operators, volume 29 of Mathematical Notes.  Princeton University Press, Princeton, NJ; University of Tokyo Press, Tokyo, 1982.
  * [2] B. Helffer.  Semi-classical analysis for the Schrödinger operator and applications, volume 1336 of Lecture Notes in Mathematics.  Springer-Verlag, Berlin, 1988.
  * [3] B. Helffer and J. Sjöstrand.  Multiple wells in the semiclassical limit I.  Comm. Part. Diff. Eq., 9(4):337–408, 1984.
  * [4] B. Simon.  Semiclassical analysis of low lying eigenvalues. I. Nondegenerate minima: asymptotic expansions.  Ann. Inst. H. Poincaré Sect. A (N.S.), 38(3):295–308, 1983.
  * [5] B. Simon.  Semiclassical analysis of low lying eigenvalues. II. tunneling.  Ann. of Math., 120(1):89–118, 1984.
  * [6] M. Filoche and S. Mayboroda.  Universal mechanism for Anderson and weak localization.  Proc. Natl. Acad. Sci. USA, 109(37):14761–14766, 2012.
  * [7] D. N. Arnold, G. David, M. Filoche, D. Jerison, and S. Mayboroda.  Localization of eigenfunctions via an effective potential.  Comm. Part. Diff. Eq., 44:1–31, 2019.
  * [8] D. N. Arnold, G. David, M. Filoche, D. Jerison, and S. Mayboroda.  Computing spectra without solving eigenvalue problems.  SIAM J. Scient. Comp., 41:B69–B92, 2019.
  * [9] D. N. Arnold, G. David, D. Jerison, S. Mayboroda, and M. Filoche.  Effective confining potential of quantum states in disordered media.  Phys. Rev. Lett., 116:056602, 2016.
  * [10] G. David, M. Filoche, and S. Mayboroda.  The landscape law for the integrated density of states.  https://arxiv.org/abs/1909.10558, 2019.
  * [11] E. M. Harrell and A. V. Maltsev.  Localization and landscape functions on quantum graphs.  Trans. Amer. Math. Soc., 373(3):1701–1729, 2020.
  * [12] Wei Wang and Shiwen Zhang.  The exponential decay of eigenfunctions for tight binding Hamiltonians via landscape and dual landscape functions.  https://arxiv.org/abs/2003.07987, 2020.
  * [13] S. Balasubramanian, Y. Liao, and V. Galitski.  Many-body localization landscape.  Phys. Rev. B, 101:014201, 2020.
  * [14] B. Simon and T. Wolff.  Singular continuous spectrum under rank one perturbations and localization for random Hamiltonians.  Comm. Pure Appl. Math., 39:75–90, 1986.
  * [15] P. Bourgade.  Random band matrices.  In Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018, volume IV of Invited lectures, pages 2759–2784. World Sci. Publ., Hackensack, NJ, 2018.
  * [16] Y. V. Fyodorov and A. D. Mirlin.  Scaling properties of localization in random band matrices: a sigma-model approach.  Phys. Rev. Lett., 67:2405–2409, 1991.
  * [17] P. Bourgade, H.-T. Yau, and J. Yin.  Random band matrices in the delocalized phase I: Quantum unique ergodicity and universality.  Comm. Pure Appl. Math., 73:1526–1596, 2020.
  * [18] R. Peled, J. Schenker, M. Shamis, and S. Sodin.  On the Wegner orbital model.  Int. Math. Res. Not., pages 1030–1058, 2019.
  * [19] J. Schenker.  Eigenvector localization for random band matrices with power law band width.  Comm. Math. Phys., 290(3):1065–1097, 2009.
  * [20] S. Sodin.  The spectral edge of some random band matrices.  https://arxiv.org/abs/0906.4047, 2010.
  * [21] P. W. Anderson.  Absence of diffusion in certain random lattices.  Phys. Rev., 109:1492–1505, 1958.
  * [22] R. J. Plemmons.  ${M}$-matrix characterizations. I – Nonsingular ${M}$-matrices.  Linear Algebra and its Applications, 18:175–188, 1977.
  * [23] D. M. Basko, I. L. Aleiner, and B. L. Altshuler.  Metal-insulator transition in a weakly interacting many-electron system with localized single-particle states.  Ann. Phys., 321:1126–1205, 2006.
  * [24] J. Lu and S. Steinerberger.  Detecting localized eigenstates of linear operators.  Res. Math. Sci., 5(3):33, 2018.
  * [25] G. Lemut, M. J. Pacholski, O. Ovdat, A. Grabsch, J. Tworzydło, and C. W. J. Beenakker.  Localization landscape for Dirac fermions.  Phys. Rev. B, 101:081405, 2020.


$H_{k^{\prime}}$ in $O(k^{\prime}\cdot n^{\alpha})=O(n^{\alpha+\beta})$ time.
Finally, we answer the query by running Dijkstra‘s algorithm from $s$ on
$H_{s,t}$ and returning the found path (lifted to a path in $G$ by
concatenating the respective deques) in $O(n^{2\beta})$ time. The correctness
follows by the below lemma, whose easy proof is analogous to that of Lemma 8.2
and is thus omitted.

######  Lemma 9.5.

The shortest $s\to t$ path in $H_{s,t}$ corresponds to some
$(1+\epsilon^{\prime})^{O(\log{n})}$-approximately shortest path in $G$.

Now let us describe how the edges inserted in a subphase are ’’merged‘‘ into
the data structure for answering queries in $G_{0}^{\prime}$, so that the
state of the data structure is correct before the start of the next subphase.
If we proceeded as in Section 9.1, i.e., added these edges one by one, we
would end up spending $O(n^{1+\alpha})$ time per edge, which would not lead to
any improvement at all.

Instead, we proceed as follows. Our goal is to compute such paths $P_{i,u}$,
$Q_{i,v}$, $u,v\in V$, $i=1,\ldots,k^{\prime}$, that $P_{i,u}$ is an
approximate shortest $u\to u_{i}$ path in
$G_{0}^{\prime}\cup\\{u_{i}v_{i}:i=1,\ldots,k^{\prime}\\}$, and $Q_{i,v}$ is
an approximate shortest $v_{i}\to v$ path in that graph.

We first compute the approximate shortest paths between $X\cup Y$ in the graph
$G_{0}^{\prime}$. Note that since the query algorithm in Section 9.1 locates,
for a single pair $(x,y)\in X\times Y$, such an index $i\leq F$ that
$P_{i,x}\cdot e_{i}\cdot Q_{i,y}$ is minimized, doing it for all pairs $(x,y)$
is precisely computing an (exact) min-plus distance product. We do not however
need to compute it exactly; computing it approximately is sufficient if we
guarantee that not too much error will accumulate. Let us forget, for a
moment, about this issue. Then, we can find approximate shortest paths matrix
$R$ between the vertices $X\cup Y$ in $G_{0}^{\prime}$ using Theorem 9.1 in
$\widetilde{O}(n^{\omega(\beta,\alpha,\beta)}\cdot(1/\epsilon)\cdot\log{(C/\epsilon)})$
time. The matrix $R$ can be lifted to approximate shortest paths matrix
$R^{*}$ between $X\cup Y$ in
$G_{0}^{\prime}\cup\\{u_{i}v_{i}:i=1,\ldots,k^{\prime}\\}$ by repeated
squaring of the matrix $R^{\prime}$, where $R^{\prime}_{x,y}$ is set to the
shortest out of the path $R_{x,y}$ and a single-edge path $xy$, if
$xy=u_{i}v_{i}$ for some $i$ (this is completely analogous to the computation
performed in the proof of Lemma 9.2). Computing $R^{*}$ again takes
$\widetilde{O}(n^{\omega(\beta,\beta,\beta)}\cdot(1/\epsilon)\cdot\log{(C/\epsilon)})$
time.

Next, we similarly use Lemma 9.2 to compute approximate shortest paths
matrices $P^{\prime},Q^{\prime}$ between pairs in $(V\times(X\cup
Y))\cup((X\cup Y)\times V)$ in the graph $G_{0}^{\prime}$; this
takes$\widetilde{O}(n^{\omega(1,\alpha,\beta)}\cdot(1/\epsilon)\cdot\log{(C/\epsilon)})$
time using the approximate distance product. We then set
$P^{\prime}_{u_{i},v_{i}}=\min(P^{\prime}_{u_{i},v_{i}},w_{G}(u_{i}v_{i}))$
and
$Q^{\prime}_{u_{i},v_{i}}=\min(Q^{\prime}_{u_{i},v_{i}},w_{G}(u_{i}v_{i}))$.
Finally, to compute the approximate shortest paths $P_{i,u}$ in
$G_{0}^{\prime}\cup\\{u_{i}v_{i}:i=1,\ldots,k^{\prime}\\}$, it is enough to
compute one more approximate distance product of $P^{\prime}$ and $R^{*}$.
Similarly, to compute approximate shortest paths $Q_{i,u}$, it is enough to
compute one more approximate distance product of $R^{*}$ and $Q^{\prime}$.
Both these computations require
$\widetilde{O}(n^{\omega(1,\beta,\beta)}\cdot(1/\epsilon)\cdot\log{(C/\epsilon)})$
time.

To conclude, the new subphase‘s updates can be merged into the data structure
answering queries in
$\widetilde{O}(n^{\omega(1,\alpha,\beta)}\cdot(1/\epsilon)\cdot\log{(C/\epsilon)})$
time, which is a cost incurred once per a subphase, i.e., the amortized time
spent on this is
$\widetilde{O}(n^{\omega(1,\alpha,\beta)-\beta}\cdot(1/\epsilon)\cdot\log{(C/\epsilon)})$.
This is however, a slight oversimplification: to make this bound hold in the
worst-case, and make sure that the error does not accumulate too much (i.e.,
be as large as
$(1+\epsilon^{\prime})^{\Theta(F/f)}=(1+\epsilon^{\prime})^{\operatorname{poly}(n)}$),
we need to proceed similarly as in Section 9.1 with matrices $D_{b}$: merges
of sizes $f,2f,4f,\ldots,2^{i}\cdot f,\ldots,\Theta(F)$ have to be performed
every $\Theta(2^{i}\cdot f)$ updates, so that the accumulated multiplicative
error stays $(1+\epsilon^{\prime})^{\Theta(\log{n})}$.

The worst-case update time is
$\widetilde{O}((n^{\omega(1,\alpha,1)-\alpha}+n^{\omega(1,\alpha,\beta)-\beta}+n^{\alpha+\beta})\cdot(1/\epsilon)\cdot\log(C/\epsilon))$,
whereas the query time for returning a representation of a
$(1+\epsilon)$-approximate shortest path is $O(n^{\alpha+\beta})$. This is the
same trade-off as in [vdBNS19, Theorem 4.2], and with the currently known
bounds on $\omega(\cdot,\cdot,\cdot)$, one optimizes it by setting
$\alpha\approx 0.855$ and $\beta\approx 0.551$. We thus obtain the following.

######  Lemma 9.6.

Let $\epsilon\in(0,1)$. There exists a deterministic incremental data
structure supporting insertions of single edges with real weights in $[1,C]$
in $O(n^{1.407}\cdot(1/\epsilon)\cdot\log(C/\epsilon))$ worst-case time and
$(1+\epsilon)$-approximate shortest path queries in $O(n^{1.407}+|P|)$ time,
where $|P|$ is the size of the returned _not necessarily_ simple path.

Note that the $|P|$ term in the query time above can be neglected in the case
of unweighted graphs and $\epsilon=O(1)$, which can be used to obtain a
deterministic incremental reachability data structure supporting both single-
edge updates and path queries in $O(n^{1.407})$ worst-case time.

Lemmas 9.3 and 9.6 together yield Theorem 1.6.

##  10 Incremental exact shortest paths

In this section we work with incremental unweighted graphs and our goal is to
support computing shortest paths exactly. We will consider two settings:

  * •

single-edge updates and single-pair shortest path queries,

  * •

single-vertex incoming edges updates and single-source shortest paths tree
queries.

The data structures maintained by the algorithm will be the same for both
settings. We will use the following analogue of Lemma 8.1.

######  Lemma 10.1.

Let $h\leq n$ be an integer. Suppose the matrix $D$ represents exact all-pairs
distances in $G$ for pairs of vertices whose distance does not exceed the
threshold $h$. Let the matrix $P$ contain the respective underlying paths,
implemented as concatenable deques as in Section 8.2. Let $W\subseteq V$ be of
size $O(n^{\alpha})$, where $\alpha\in[0,1]$. Let $E^{+}$ be some set of edges
with heads in the set $W$.

One can construct an analogous matrix $D^{\prime}$ representing exact
distances that do not exceed $h$ in $G\cup E^{+}$, along with a matrix of
respective simple paths $P^{\prime}$, deterministically in
$\widetilde{O}(h\cdot n^{\omega(1,\alpha,1)})$ time.

###### Proof sketch..

The proof is almost identical to that of Lemma 9.2, so we merely sketch it.
One only needs to substitute every application of approximate min-plus product
$\star_{\epsilon}$ (Theorem 9.1) with exact min-plus product $\star_{\leq h}$
of matrices whose finite entries are positive integers not larger than $h$
[Zwi02, Lemma 3.3]. This bounded min-plus product can be computed in
$\widetilde{O}(hn^{\omega(1,\alpha,1)})$ time and can provide the
corresponding witnesses deterministically within the same bound. ∎

The algorithm will again operate in phases of insertions of length
$F=n^{\alpha}$. Let again $G_{0}$ denote the graph at the beginning of the
current phase, and let $E_{i}$ be the edges inserted in the $i$-th update of
the phase. Denote by $v_{i}$ the head of the edges inserted in the $i$-th
update. If just a single edge is inserted in that update, denote by $u_{i}$
the tail of that edge. Let $k$ denote the most recent update‘s number within
the current phase and let $E_{k}^{+}=\bigcup_{i=1}^{k}E_{i}$.

Whenever a phase starts, we will recompute a matrix of shortest paths $P$ up
to length $h=n/F$ using Lemma 10.1 in
$\widetilde{O}(hn^{\omega(1,\alpha,1)})=\widetilde{O}(n^{\omega(1,\alpha,1)+1-\alpha})$
time, based on the matrix from the beginning of the previous phase. The next
step is to compute a small hitting set $B\subseteq V$ of all paths in $P$ of
length _precisely_ $n/F$. Such a hitting set of size $|B|=\widetilde{O}(F)$
can be computed deterministically using a greedy algorithm in time linear in
the input size, i.e., in
$\widetilde{O}(n^{3-\alpha})=\widetilde{O}(n^{\omega(1,\alpha,1)+1-\alpha})$
time in our case (see, e.g., [Zwi02]). So the amortized time spent on
recomputation is $\widetilde{O}(n^{\omega(1,\alpha,1)+1-2\alpha})$. This can
be turned into a worst-case bound in a standard way as was already done
multiple times in the previous sections. We will use the following trivial
observation.

######  Observation 10.2.

Suppose $B$ is a hitting set of all shortest paths of length precisely $h$ in
$G_{0}$. Then, $B\cup\\{v_{i}:i=1,\ldots,k\\}$ is a hitting set of all
shortest paths of length precisely $h$ in $G_{0}\cup E_{k}^{+}$.

###  10.1 Single-edge updates, pair queries

Let $X=\\{u_{i},v_{i}:i=1,\ldots,k\\}$ denote the set of endpoints of edge
insertions in the current phase. We have $|X|=O(F)=O(n^{\alpha})$. We
construct an auxiliary graph $H_{s,t}$ with vertices $\\{s,t\\}\cup X\cup B$.
The edge set of $H_{s,t}$ includes the edges $E_{k}^{+}$ and a weighted edge
$uv$ for each $u,v\in V(H_{s,t})$ corresponding to the path $P_{u,v}$ in
$G_{0}$, if $P_{u,v}$ has length no more than $h$. Finally, we compute an
$s\to t$ shortest path in $H_{s,t}$ using Dijkstra‘s algorithm in $O(|X\cup
B|^{2})=\widetilde{O}(F^{2})=\widetilde{O}(n^{2\alpha})$ time. Clearly, such a
path in $H_{s,t}$ can be lifted to a path in $G=G_{0}\cup E^{+}_{k}$ using the
paths stored in the matrix $P$. Note that since the graph is unweighted, the
size of the returned path is $O(n)$.

The correctness follows easily by Observation 10.2 and the fact that all the
relevant paths of length no more than $h$ in $G_{0}$ are represented in
$H_{s,t}$.

######  Lemma 10.3.

Let $G$ be an unweighted digraph and let $\alpha\in(0.5,1)$. There exists a
deterministic incremental data structure supporting single-edge insertions in
$\widetilde{O}(n^{\omega(1,\alpha,1)+1-2\alpha})$ worst-case time and queries
reporting a shortest path from a given source to a given target in
$\widetilde{O}(n^{2\alpha})$ time. In particular, for $\alpha=0.81$, both
bounds are $O(n^{1.62})$.

######  Remark 10.4.

The above lemma holds even for $\alpha\leq 0.5$, but then the update time is
$\Omega(n^{2})$. However, $O(n^{2})$ worst-case update time with $O(1)$ query
time can be obtained rather trivially even for real-weighted graphs, so the
data structure behind Lemma 10.3 is inferior in that case.

###  10.2 Incoming edges updates, single-source queries

We construct an auxiliary graph $H_{s}$ with vertices $V$. Let
$Y=\\{v_{i}:i=1,\ldots,k\\}$. The edge set of $H_{s}$ includes the edges
$E_{k}^{+}$ (recall that $|E_{k}^{+}|\leq nk=O(n^{1+\alpha})$). Moreover, for
each $v\in B\cup Y\cup\\{s\\}$ and $w\in V$, we add a weighted edge $vw$
representing the path $P_{v,w}$ in $G_{0}$, unless $P_{v,w}$ has length more
than $h$. As a result, the graph $H_{s}$ has
$\widetilde{O}(nF)=\widetilde{O}(n^{1+\alpha})$ edges.

By proceeding similarly as in the proof of Lemma 8.2, it is also easy to show
that $H_{s}$ preserves distances from $s$ in $G\cup E_{k}^{+}$. All the
required paths of length no more than $h$ are represented in $H_{s}$ by the
definition of the hitting set $B$ and Observation 10.2.

A shortest paths tree $T_{s}$ from $s$ in $H_{s}$ can be computed in
$\widetilde{O}(n^{1+\alpha})$ time using Dijkstra‘s algorithm. Note that each
edge in that tree corresponds to either a path of length $\leq
h=O(n^{1-\alpha})$ in $G_{0}$, or a single edge in $E_{k}^{+}$. As a result,
by expanding the $O(n)$ edges of $T_{s}$ into paths in $G_{0}$, we obtain a
subgraph $T_{s}^{\prime}\subseteq G$ with $\widetilde{O}(n^{2-\alpha})$ edges
that is guaranteed to contain some shortest $s\to t$ path in $G$ for any $t$.
Consequently, a shortest paths tree from $s$ in $G$ can be obtained by running
Dijkstra‘s algorithm once again on $T_{s}^{\prime}$ in
$\widetilde{O}(n^{2-\alpha})$ time. For $\alpha\geq 0.5$ this is dominated by
the $\widetilde{O}(n^{1+\alpha})$ bound. Therefore, we obtain the following.

######  Lemma 10.5.

Let $G$ be an unweighted digraph and let $\alpha\in(0.5,1)$. There exists a
deterministic incremental data structure supporting insertions of incoming
edges of a single vertex in $\widetilde{O}(n^{\omega(1,\alpha,1)+1-2\alpha})$
worst-case time and queries reporting a single-source shortest paths tree from
a given source in $\widetilde{O}(n^{1+\alpha})$ time. In particular, for
$\alpha=0.724$, both bounds are $O(n^{1.724})$.

Lemmas 10.3 and 10.5 together yield Theorem 1.7.

## References

  * [AGMN92] Noga Alon, Zvi Galil, Oded Margalit, and Moni Naor.  Witnesses for boolean matrix multiplication and for shortest paths.  In 33rd Annual Symposium on Foundations of Computer Science, Pittsburgh, Pennsylvania, USA, 24-27 October 1992, pages 417–426. IEEE Computer Society, 1992.
  * [AIMN91] Giorgio Ausiello, Giuseppe F. Italiano, Alberto Marchetti-Spaccamela, and Umberto Nanni.  Incremental algorithms for minimal length paths.  J. Algorithms, 12(4):615–638, 1991.
  * [AW14] Amir Abboud and Virginia Vassilevska Williams.  Popular conjectures imply strong lower bounds for dynamic problems.  In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 434–443. IEEE Computer Society, 2014.
  * [BC18] Aaron Bernstein and Shiri Chechik.  Incremental topological sort and cycle detection in expected total time.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 21–34. SIAM, 2018.
  * [Ber16] Aaron Bernstein.  Maintaining shortest paths under deletions in weighted directed graphs.  SIAM J. Comput., 45(2):548–574, 2016.
  * [BFGT16] Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Robert E. Tarjan.  A new approach to incremental cycle detection and related problems.  ACM Trans. Algorithms, 12(2):14:1–14:22, 2016.
  * [BGS20] Aaron Bernstein, Maximilian Probst Gutenberg, and Thatchaphol Saranurak.  Deterministic decremental reachability, scc, and shortest paths via directed expanders and congestion balancing.  In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 1123–1134. IEEE, 2020.
  * [BGW20] Aaron Bernstein, Maximilian Probst Gutenberg, and Christian Wulff-Nilsen.  Near-optimal decremental SSSP in dense weighted digraphs.  In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 1112–1122. IEEE, 2020.
  * [BHG+20] Thiago Bergamaschi, Monika Henzinger, Maximilian Probst Gutenberg, Virginia Vassilevska Williams, and Nicole Wein.  New techniques and fine-grained hardness for dynamic near-additive spanners.  CoRR, abs/2010.10134, 2020.
  * [BHG+21] Thiago Bergamaschi, Monika Henzinger, Maximilian Probst Gutenberg, Virginia Vassilevska Williams, and Nicole Wein.  New techniques and fine-grained hardness for dynamic near-additive spanners.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 1836–1855. SIAM, 2021.
  * [BK20] Sayan Bhattacharya and Janardhan Kulkarni.  An improved algorithm for incremental cycle detection and topological ordering in sparse graphs.  In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 2509–2521. SIAM, 2020.
  * [BPW19] Aaron Bernstein, Maximilian Probst, and Christian Wulff-Nilsen.  Decremental strongly-connected components and single-source reachability in near-linear time.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 365–376. ACM, 2019.
  * [CK19] Julia Chuzhoy and Sanjeev Khanna.  A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 389–400. ACM, 2019.
  * [CKL07] Artur Czumaj, Miroslaw Kowaluk, and Andrzej Lingas.  Faster algorithms for finding lowest common ancestors in directed acyclic graphs.  Theor. Comput. Sci., 380(1-2):37–46, 2007.
  * [DI04] Camil Demetrescu and Giuseppe F. Italiano.  A new approach to dynamic all pairs shortest paths.  J. ACM, 51(6):968–992, 2004.
  * [DI05] Camil Demetrescu and Giuseppe F. Italiano.  Trade-offs for fully dynamic transitive closure on dags: breaking through the o(n${}^{\mbox{2}}$ barrier.  J. ACM, 52(2):147–156, 2005.
  * [DI08] Camil Demetrescu and Giuseppe F. Italiano.  Mantaining dynamic matrices for fully dynamic transitive closure.  Algorithmica, 51(4):387–427, 2008.
  * [Die89] Paul F. Dietz.  Fully persistent arrays (extended array).  In Algorithms and Data Structures, Workshop WADS ‘89, Ottawa, Canada, August 17-19, 1989, Proceedings, volume 382 of Lecture Notes in Computer Science, pages 67–74. Springer, 1989.
  * [DSST89] James R. Driscoll, Neil Sarnak, Daniel Dominic Sleator, and Robert Endre Tarjan.  Making data structures persistent.  J. Comput. Syst. Sci., 38(1):86–124, 1989.
  * [EFGW21] Jacob Evald, Viktor Fredslund-Hansen, Maximilian Probst Gutenberg, and Christian Wulff-Nilsen.  Decremental APSP in unweighted digraphs versus an adaptive adversary.  In 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), volume 198 of LIPIcs, pages 64:1–64:20. Schloss Dagstuhl \- Leibniz-Zentrum für Informatik, 2021.
  * [FMNZ01] Daniele Frigioni, Tobias Miller, Umberto Nanni, and Christos D. Zaroliagis.  An experimental study of dynamic algorithms for transitive closure.  ACM J. Exp. Algorithmics, 6:9, 2001.
  * [GIL+21] Fabrizio Grandoni, Giuseppe F. Italiano, Aleksander Lukasiewicz, Nikos Parotsidis, and Przemyslaw Uznanski.  All-pairs LCA in dags: Breaking through the _O_(_n_ ${}^{\mbox{2.5}}$) barrier.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 273–289. SIAM, 2021.
  * [GU18] Francois Le Gall and Florent Urrutia.  Improved rectangular matrix multiplication using powers of the coppersmith-winograd tensor.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1029–1046. SIAM, 2018.
  * [GWW20] Maximilian Probst Gutenberg, Virginia Vassilevska Williams, and Nicole Wein.  New algorithms and hardness for incremental single-source shortest paths in directed graphs.  In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 153–166. ACM, 2020.
  * [Ita86] Giuseppe F. Italiano.  Amortized efficiency of a path retrieval data structure.  Theor. Comput. Sci., 48(3):273–281, 1986.
  * [KŁ19] Adam Karczmarz and Jakub Łącki.  Reliable hubs for partially-dynamic all-pairs shortest paths in directed graphs.  In 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany, volume 144 of LIPIcs, pages 65:1–65:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019\.
  * [KŁ20] Adam Karczmarz and Jakub Łącki.  Simple label-correcting algorithms for partially dynamic approximate shortest paths in directed graphs.  In 3rd Symposium on Simplicity in Algorithms, SOSA 2020, Salt Lake City, UT, USA, January 6-7, 2020, pages 106–120. SIAM, 2020.
  * [KS02] Valerie King and Garry Sagert.  A fully dynamic algorithm for maintaining the transitive closure.  J. Comput. Syst. Sci., 65(1):150–167, 2002.
  * [KT99] Haim Kaplan and Robert E Tarjan.  Purely functional, real-time deques with catenation.  Journal of the ACM (JACM), 46(5):577–603, 1999.
  * [ŁS13] Jakub Łącki and Piotr Sankowski.  Reachability in graph timelines.  In Innovations in Theoretical Computer Science, ITCS ‘13, Berkeley, CA, USA, January 9-12, 2013, pages 257–268. ACM, 2013.
  * [NS17] Danupon Nanongkai and Thatchaphol Saranurak.  Dynamic spanning forest with worst-case update time: adaptive, las vegas, and o(n${}^{\mbox{1/2 - {$\epsilon$}}}$)-time.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 1122–1129. ACM, 2017.
  * [Rod08] Liam Roditty.  A faster and simpler fully dynamic transitive closure.  ACM Trans. Algorithms, 4(1):6:1–6:16, 2008.
  * [RZ16] Liam Roditty and Uri Zwick.  A fully dynamic reachability algorithm for directed graphs with an almost linear update time.  SIAM J. Comput., 45(3):712–733, 2016.
  * [San04] Piotr Sankowski.  Dynamic transitive closure via dynamic matrix inverse (extended abstract).  In 45th Symposium on Foundations of Computer Science (FOCS 2004), 17-19 October 2004, Rome, Italy, Proceedings, pages 509–517. IEEE Computer Society, 2004.
  * [San05] Piotr Sankowski.  Subquadratic algorithm for dynamic shortest distances.  In Computing and Combinatorics, 11th Annual International Conference, COCOON 2005, Kunming, China, August 16-29, 2005, Proceedings, volume 3595 of Lecture Notes in Computer Science, pages 461–470. Springer, 2005.
  * [San07] Piotr Sankowski.  Faster dynamic matchings and vertex connectivity.  In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007, pages 118–126. SIAM, 2007.
  * [Sch80] Jacob T. Schwartz.  Fast probabilistic algorithms for verification of polynomial identities.  J. ACM, 27(4):701–717, 1980.
  * [Tho04] Mikkel Thorup.  Fully-dynamic all-pairs shortest paths: Faster and allowing negative cycles.  In Algorithm Theory - SWAT 2004, 9th Scandinavian Workshop on Algorithm Theory, Humlebaek, Denmark, July 8-10, 2004, Proceedings, volume 3111 of Lecture Notes in Computer Science, pages 384–396. Springer, 2004\.
  * [vdBFN21] Jan van den Brand, Sebastian Forster, and Yasamin Nazari.  Fast deterministic fully dynamic distance approximation.  CoRR, abs/2111.03361, 2021.
  * [vdBN19] Jan van den Brand and Danupon Nanongkai.  Dynamic approximate shortest paths and beyond: Subquadratic and worst-case update time.  In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 436–455. IEEE Computer Society, 2019.
  * [vdBNS19] Jan van den Brand, Danupon Nanongkai, and Thatchaphol Saranurak.  Dynamic matrix inverse: Improved algorithms and matching conditional lower bounds.  In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 456–480. IEEE Computer Society, 2019.
  * [Zip79] Richard Zippel.  Probabilistic algorithms for sparse polynomials.  In Symbolic and Algebraic Computation, EUROSAM ‘79, An International Symposiumon Symbolic and Algebraic Computation, Marseille, France, June 1979, Proceedings, volume 72 of Lecture Notes in Computer Science, pages 216–226. Springer, 1979.
  * [Zwi02] Uri Zwick.  All pairs shortest paths using bridging sets and rectangular matrix multiplication.  J. ACM, 49(3):289–317, 2002.