Sparse random matrices have simple spectrum

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Random graphs (graph-theoretic aspects) (05C80) Random matrices (algebraic aspects) (15B52) Random matrices (probabilistic aspects) (60B20)

Abstract: Let

M_{n}

be a class of symmetric sparse random matrices, with independent entries

M_{i j} = d e l t a_{i j} x i_{i j}

for

i l e q j

.

d e l t a_{i j}

are i.i.d. Bernoulli random variables taking the value

1

with probability

p g e q n^{- 1 + d e l t a}

for any constant

d e l t a > 0

and

x i_{i j}

are i.i.d. centered, subgaussian random variables. We show that with high probability this class of random matrices has simple spectrum (i.e. the eigenvalues appear with multiplicity one). We can slightly modify our proof to show that the adjacency matrix of a sparse ErdH{o}s-R'enyi graph has simple spectrum for

n^{- 1 + d e l t a} l e q p l e q 1 - n^{- 1 + d e l t a}

. These results are optimal in the exponent. The result for graphs has connections to the notorious graph isomorphism problem.

Recommendations

Cites work

Cited in

(12)

This page was built for publication: Sparse random matrices have simple spectrum

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2028938)