Statistical mechanics approach to top eigenpairs of sparse symmetric random matrices

Abstract

The aim of this thesis is to characterise the statistics of the top eigenpairs of sparse symmetric random matrices, adopting the perspective and the tools of statistical physics of disordered systems.
Our first main result is the development of a statistical mechanics formalism to compute the statistics of the top eigenpair of sparse ensembles. Framing the problem in terms of op-timisation of a quadratic form on the sphere and introducing a fictitious real temperature, we employ the cavity and the replica methods to determine the solution in terms of functional self-consistency equations, which are efficiently solved by a population dynamics algorithm. In our derivation, the structure of the density of the top eigenvector’s components is understood in terms of the heterogeneous contributions coming from nodes of different degrees.
Then, introducing a “deflation” mechanism – that maps the largest eigenvalue of a matrix to zero while leaving its eigenvectors invariant – in conjunction with the statistical mechanics framework used for the top eigenpair, we study the statistics of the second largest eigenpair of sparse ensembles assuming that the top eigenpair statistics is known. This is the second main result of this thesis. The orthogonality condition between distinct eigenvectors naturally arises in the solution and is included in an appropriately modified version of the population dynamics algorithm. We also show that the population dynamics algorithm is not able to accurately capture the thermodynamic limit N → ∞ when using a finite population size N_P. We find evidence of the existence of an optimal population size N∗_P for a given graph size N.
Our results are in perfect agreement with numerical diagonalisation of large sparse adjacency matrices, concentrating on the cases of random regular and Erdós-Rényi graphs and sparse Markov transition matrices for unbiased random walks.
Before deriving our main results, we provide an extensive presentation of the cavity and the replica methods, using the problem of the average spectral density as a case study.

Date of Award	1 Oct 2021
Original language	English
Awarding Institution	King's College London
Supervisor	Pierpaolo Vivo (Supervisor) & Reimer Kuhn (Supervisor)