Circular law for the sum of random permutation matrices

Abstract

Let $P_n^1,\dots ,P_n^d$ be $n\times n$ permutation matrices drawn independently and uniformly at random, and set $S_n^d:={\sum }_{\ell =1}^d{P}_n^{\ell }$. We show that if ${\log }^{12}n/(\log \log n{)}^4\le d=O(n)$, then the empirical spectral distribution of $S_n^d/\sqrt{d}$ converges weakly to the circular law in probability as $n\to \infty$.

arXiv comment50 pages, to appear in EJP