The Spectral decomposition of sparse zero-one matrices

Simon Coste - ENS now, LPSM soon

journées MAS - Rouen, 29 août 2022.

Eigenvalues of non-Hermitian matrices

> using LinearAlgebra
> eigvals(randn(500,500))

Eigenvalues of 0/1 sparse matrices

> using LinearAlgebra
> eigvals(rand(500,500).<0.01)

A_n = an n \times n matrix whose entries are iid \mathrm{Bernoulli}(d/n) entries.

Eigenvalues of random regular digraphs

> using LinearAlgebra, Erdos
  > eigvals(random_regular_digraph(500, 3))

same with A_n = sum of d uniform n\times n permutation matrices

Reverse characteristic polynomial

q_n (z) = \det(I_n - zA_n)

the coefficients of q_n(z)=1+\Delta_1z+\Delta_2z^2+...+\Delta_{n}z^{n} are \Delta_k = (-1)^k \frac{P_k(\mathrm{trace}(A_n^1), ..., \mathrm{trace}(A_n^k))}{k!},

where the P_k are polynomials.

A very simple method

The limits of the traces of A^k_n

For every k, (\mathrm{tr}(A_n^1), ..., \mathrm{tr}(A_n^k)) \xrightarrow[n \to \infty]{\mathrm{law}} (X_1, ... , X_k). where X_k := \sum_{\ell|k} \ell Y_\ell (Y_\ell : \ell \in \mathbb{N}^*) = family of independent r.v., Y_\ell \sim \mathrm{Poi}(d^\ell / \ell).

The limits of the coefficients of q_n

\Delta_k \to a_k = (-1)^k \frac{P_k(X_1, ... , X_k)}{k!} Let F be the generating function of these random variables: F(z) = 1 + \sum_{k=1}^\infty a_k z^k

Coefficients of q_n \to coefficients of F

Do we have stronger convergence than that?

Weak convergence of analytic functions

Shirai 2012

If f_n is a sequence of random analytic functions in an open set D and if

  1. the coeffs of f_n converge towards (a_k)

  2. f_n is tight in D

then f_n \to f where f(z) = \sum a_k z^k.

Tightness in holomorphic spaces

Let f_n be a sequence of random analytic functions: f_n(z) = \sum_{k=0}^\infty a_{n,k}z^k.

If there is a c such that \sup_n \mathbf{E}[|a_{n,k}|^2] \leqslant c r^k then (f_n) is tight on d(0,\sqrt{r}).

Tightness of (q_n)

The sequence q_n is tight in D(0,\sqrt{1/d}).

  • easy for dense matrix ensembles (eg Ginibre)

  • not easy for the sparse Bernoulli model

  • difficult for the sum-of-permutations model

q_n \to F as holomorphic functions on D(0,d^{-1/2}).

Elementary properties of F

F(z) = \exp \left( -\sum_{k=1}^\infty X_k \frac{z^k}{k} \right) = \prod_{k=1}^\infty (1 - z^k)^{Y_k}

  • the radius of convergence inside the exp is 1/d.

  • the radius of convergence of F is 1/\sqrt{d} and F has one zero at 1/d.

  • F has no other zeroes inside D(0,1/\sqrt{d}).

Zeroes of q_n => zeroes of F

The zeroes are continuous wrt weak convergence on \mathbb{H}.

Zeroes of q_n inside D(0,1/\sqrt{d}) = inverse of eigenvalues of A_n outside D(0,\sqrt{d}).

Asymptotically, A_n has one eigenvalue close to d.

The other ones are smaller than \sqrt{d}.

The gaussian holomorphic chaos

G(z) = e^{-g(z)} \quad \text{where}\quad g(z) =\sum_{n=0}^\infty \red{\mathscr{N}_\mathbb{C}(0,1)}\frac{z^n}{\sqrt{n}} F(z) = e^{-f(z)} \quad \text{where}\quad f(z) = \sum_{n=0}^\infty \red{X_n} \frac{z^n}{n} covariances: \mathrm{cov}(g(z), g(w)) = -\log(1 - z\bar{w}) \mathrm{cov}(f(z), f(w)) = -\sum_{n,m \geq 1} \frac{\log(1 - d z^n \bar{w}^m)}{nm}

Generating function for G

Najnudel, Paquette, Simm, 2020 + Diaconis, Gamburd, 2004

\mathbf{E} G(z_1)...G(z_k)\overline{G(w_1)...G(w_k)} = \prod_{i,j = 1}^k \frac{1}{1 - z_i w_j}

this is the generating function of magic squares!

Note c_n the n-th coef of G.

\mathbf{E}[|c_n|^{2k}] = number of k\times k integer matrices whose rows/columns sum to n

Generating function for F

\mathbf{E} F(z_1)...F(z_k) = \frac{\prod_{S \subset [k] \text{ odd}} (1 - d\prod_{s \in S}z_s)}{ \prod_{S \subset [k], \text{ even}} (1 - d\prod_{s \in S}z_s)}

This is the generating function of… ?

The Oriented Kesten-McKay law

For random d-regular digraphs

Conjecture. If \varrho_d = the OKMC density ([CLZ eq(2.5)] ):

\frac{1}{n}\log | \det( z - A)| \to \int \log | z - w| \varrho_d(w)\mathrm{d}w =: U_d(z)

Can we study the fluctuations ?

\Phi_n(z) = \log | \det (z - A) | - n U_d(z)

\Phi_n looks like this:

from far away from the above

Note : for z>\sqrt{d}, we have \Phi_n(z) = q_n(z).

Non-orthogonal eigenvector overlaps

Bourgade, Dubach, 2018

  • u_i, v_i = left and right eigenvectors, ie \langle u_i, v_j \rangle = \delta_{i,j}.

  • Diagonal overlaps: \mathscr{O}_i = |u_i|^2 |v_i|^2 (measure of non-orthonormality):

Histogram of \frac{\mathscr{O}_i }{ n(1 - |\lambda_i|^2)} for the three models

Bourgade & Dubach, 2018

For the complex Ginibre ensemble, \frac{\mathscr{O}_i }{ n(1-|\lambda_i|^2)} \xrightarrow[n \to \infty]{\mathrm{law}} \frac{1}{\mathrm{Gamma}(2)}

Eigenvector localization / delocalization?

color of each eigenvalue = degree of localization of the eigenvector

Ewens random graphs

a = \pi_1 + ... + \pi_d where \pi_i are \mathrm{ewens}(\theta)-distributed:

\mathbf{p}(\pi = \sigma) = \frac{\theta^{\mathrm{cycles(\sigma)}}}{\theta(\theta+1)\dotsb(\theta + n)}

merci pour l’invitation !

// reveal.js plugins