Journal of Combinatorics

Volume 4 (2013)

Number 1

Circular law for random discrete matrices of given row sum

Pages: 1 – 30

DOI: https://dx.doi.org/10.4310/JOC.2013.v4.n1.a1

Authors

Hoi H. Nguyen (Department of Mathematics, Yale University, New Haven, Connecticut, U.S.A.)

Van H. Vu (Department of Mathematics, Yale University, New Haven, Connecticut, U.S.A.)

Abstract

Let $M_n$ be a random matrix of size $n\times n$ and let $\lambda_1,\ldots,\lambda_n$ be the eigenvalues of $M_n$. The empirical spectral distribution $\mu_{M_n}$ of $M_n$ is defined as

\[\mu_{M_n}(s,t)=\frac{1}{n}\# \{k\le n, \Re(\lambda_k)\le s; \Im(\lambda_k)\le t\}.\]

The circular law theorem in random matrix theory asserts that if the entries of $M_n$ are i.i.d. copies of a random variable with mean zero and variance $\sigma^2$, then the empirical spectral distribution of the normalized matrix $\frac{1}{\sigma\sqrt{n}}M_n$ of $M_n$ converges almost surely to the uniform distribution $\mu_{\mathbf{cir}}$ over the unit disk as $n$ tends to infinity. In this paper, we show that the empirical spectral distribution of the normalized matrix of $M_n$, a random matrix whose rows are independent random $(-1,1)$ vectors of given row-sum $s$ with some fixed integer $s$ satisfying $|s|\le(1-o(1))n$, also obeys the circular law. The key ingredient is a new polynomial estimate on the least singular value of $M_n$.

Published 16 May 2013