Random matrices with row constraints and eigenvalue distributions of graph Laplacians
Pawat Akara-pipattana, Oleg Evnin
Abstract
Abstract Symmetric matrices with zero row sums occur in many theoretical settings and in real-life applications. When the offdiagonal elements of such matrices are i.i.d. random variables and the matrices are large, the eigenvalue distributions converge to a peculiar universal curve <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:msub> <mml:mi>p</mml:mi> <mml:mrow> <mml:mrow> <mml:mi mathvariant="normal">z</mml:mi> <mml:mi mathvariant="normal">r</mml:mi> <mml:mi mathvariant="normal">s</mml:mi> </mml:mrow> </mml:mrow> </mml:msub> <mml:mo stretchy="false">(</mml:mo> <mml:mi>λ</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:math> that looks like a cross between the Wigner semicircle and a Gaussian distribution. An analytic theory for this curve, originally due to Fyodorov, can be developed using supersymmetry-based techniques. We extend these derivations to the case of sparse matrices, including the important case of graph Laplacians for large random graphs with N vertices of mean degree c . In the regime <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mn>1</mml:mn> <mml:mo>≪</mml:mo> <mml:mi>c</mml:mi> <mml:mo>≪</mml:mo> <mml:mi>N</mml:mi> </mml:math> , the eigenvalue distribution of the ordinary graph Laplacian (diffusion with a fixed transition rate per edge) tends to a shifted and scaled version of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:msub> <mml:mi>p</mml:mi> <mml:mrow> <mml:mrow> <mml:mi mathvariant="normal">z</mml:mi> <mml:mi mathvariant="normal">r</mml:mi> <mml:mi mathvariant="normal">s</mml:mi> </mml:mrow> </mml:mrow> </mml:msub> <mml:mo stretchy="false">(</mml:mo> <mml:mi>λ</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:math> , centered at c with width <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mrow> <mml:mo>∼</mml:mo> </mml:mrow> <mml:msqrt> <mml:mi>c</mml:mi> </mml:msqrt> </mml:math> . At smaller c , this curve receives corrections in powers of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mn>1</mml:mn> <mml:mrow> <mml:mo>/</mml:mo> </mml:mrow> <mml:msqrt> <mml:mi>c</mml:mi> </mml:msqrt> </mml:math> accurately captured by our theory. For the normalized graph Laplacian (diffusion with a fixed transition rate per vertex), the large c limit is a shifted and scaled Wigner semicircle, again with corrections captured by our analysis.