% The characteristic polynomial of sparse zero-one matrices % Simon Coste - INRIA % Journées MAS 2021

Eigenvalues of non-Hermitian matrices

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

Example: random regular digraph

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

My favourite example: Bernoulli, sparse

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

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

Reverse characteristic polynomial

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

The coefficients of qn(z)=1+Δ1z+Δ2z2+...+Δnznq_n(z)=1+\Delta_1z+\Delta_2z^2+...+\Delta_{n}z^{n} are

Δk=(1)kPk(trace(An1),...,trace(Ank))k!,\Delta_k = (-1)^k \frac{P_k(\mathrm{trace}(A_n^1), ..., \mathrm{trace}(A_n^k))}{k!},

where the PkP_k are polynomials.

The simplest method: traces + tightness

The limits of the traces of AnkA^k_n

::: {.theorem}

For every kk,

(tr(An1),...,tr(Ank))nlaw(X1,...,Xk).(\mathrm{tr}(A_n^1), ..., \mathrm{tr}(A_n^k)) \xrightarrow[n \to \infty]{\mathrm{law}} (X_1, ... , X_k).


Xk:=kYX_k := \sum_{\ell|k} \ell Y_\ell

(Y:N)(Y_\ell : \ell \in \mathbb{N}^*) = family of independent r.v., YPoi(d/)Y_\ell \sim \mathrm{Poi}(d^\ell / \ell). :::

The limits of the coefficients of qnq_n

Δkak=(1)kPk(X1,...,Xk)k!\Delta_k \to a_k = (-1)^k \frac{P_k(X_1, ... , X_k)}{k!}

Let FF be the log-generating function of these random variables:

F(z)=1+k=1akzkF(z) = 1 + \sum_{k=1}^\infty a_k z^k

:::{.theorem} Coefficients of qnq_n \to Coefficients of FF :::

Do we have stronger convergence than that?

Weak convergence of analytic functions

::: {.theorem}

Shirai 2012

If fnf_n is a sequence of random analytic functions in an open set DD and if

  1. The coeffs of fnf_n converge towards (ak)(a_k)

  2. fnf_n is tight in DD

Then fnff_n \to f where f(z)=akzkf(z) = \sum a_k z^k.


Tightness in holomorphic spaces

Let fnf_n be a sequence of random analytic functions:

fn(z)=k=0an,kzk.f_n(z) = \sum_{k=0}^\infty a_{n,k}z^k.

::: {.theorem}

If there is a cc such that

supnE[an,k2]crk \sup_n \mathbf{E}[|a_{n,k}|^2] \leqslant c r^k

then (fn)(f_n) is tight on D(0,r)D(0,\sqrt{r}).


Tightness of (qn)(q_n)

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

::: {.proof} Proof. We must bound the 2-norm of the coefficients of qnq_n, the Δk\Delta_k.

We use Δk=I[n],I=kdet(A(I))\Delta_k = \sum_{I \subset [n], |I|=k}\det(A(I)) then develop Δk2|\Delta_k|^2.

We get a double sum of E[det(A(I))det(A(J))]\mathbf{E}[\det(A(I))\det(A(J))] with I,JI,J subsets of [n][n].

The value of each summand depends on the size of IJI\cap J.

E[Δk2]=(n)k(d/n)k(1d/n)k1(1kd/np+kdk2d/n)=O(dk)\mathbf{E}[|\Delta_k|^2] = (n)_k (d/n)^k (1-d/n)^{k-1}(1 - kd/n -p + kd - k^2d/n) =O(d^k)


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

Extras on FF

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

Zeroes of qnq_n => zeroes of FF

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

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

Asymptotically, AnA_n has one eigenvalue close to dd.

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

Friedman theorems everywhere

Can you have a short proof of Friedman's 2d12\sqrt{d-1}-theorem?

  1. Prove that the non-backtracking traces converge towards something [Dumitriu et al 2012]

  2. Prove that qnq_n is tight...

Bonne rentrée à tous !