Circular law theorem for random Markov matrices

By Charles Bordenave, Pietro Caputo, Djalil CHAFAÏ. Probability theory and related fields, 2008

82 citations recorded by the source corpus.

Let (Xjk)jk≥1 be i.i.d. nonnegative random variables with bounded density, mean m, and finite positive variance σ2. Let M be the n × n random Markov matrix with i.i.d. rows defined by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${M_{jk}=X_{jk}/(X_{j1}+\cdots+X_{jn})}$$\end{document}. In particular, when X11 follows an exponential law, the random matrix M belongs to the Dirichlet Markov Ensemble of random stochastic matrices. Let λ1, . . . , λn be the eigenvalues of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\sqrt{n}M}$$\end{document} i.e. the roots in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb{C}}$$\end{document} of its characteristic polynomial. Our main result states that with probability one, the counting probability measure \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\frac{1}{n}\delta_{\lambda_1}+\cdots+\frac{1}{n}\delta_{\lambda_n}}$$\end{document} converges weakly as n→∞ to the uniform law on the disk \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\{z\in\mathbb{C}:|z|\leq m^{-1}\sigma\}}$$\end{document}. The bounded density assumption is purely technical and comes from the way we control the operator norm of the resolvent.

Subfields: Computational Theory and Mathematics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/b6ab51a5b1faa9b85fbf82798a369ce1298ddc30

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Statistics and Probability

Citations in the corpus

Invertibility of Sparse non-Hermitian matrices (2015, background): “ singular values, especially the one on the smallest singular value, play a key role in obtaining the limiting spectral distribution of various non-Hermitian random matrix ensembles. For example, see [3, 6, 10, 11, 18, 24, 30, 35]. Likewise, the bounds on the smallest singular value obtained here pl”
Around the circular law (2011, background): “A circular law theorem is available for randomMarkov matrices including the Dirichlet Markov Ensemble [23], and random matrices with i.i.d. log-concave isotropic rows22 [1].”
On the singularity of adjacency matrices for random regular digraphs (2014, background): “In [5], Bordenave, Caputo and Chafäı proved the circular law for random Markov matrices, obtained by normalizing the rows of an iid matrix”