Spectral gap of sparse bistochastic matrices with exchangeable rows (Q2028964)

The authors study random bistochastic matrices of dimension \(n\) of the form \(P=MQ\) with a random, uniformly distributed permutation matrix \(M\) and a deterministic matrix \(Q\). Then \(P\) and \(Q\) have the same Hilbert-Schmidt norm and maximal entry, and thus the same maximum \(\rho>0\) of these two values. The authors show that for sparsely occupied matrices, large \(n\), and with high probability, then \(|\lambda_2|\le\rho\) holds when the eigenvalues of \(P\) are ordered by \(\lambda_1=1\ge|\lambda_2|\ge\ldots\ge|\lambda_n|\). This is in contrast to much weaker estimates for the deterministic matrices \(Q\). This result is shown even in a more general form; moreover, several applications, e.g., on random walks on random regular digraphs are discussed. The nontrivial proofs use methods from graph theory and are based on recent papers of C. Bordenave, M. Lelarge, and L. Massoulié.