Spectral gap of sparse bistochastic matrices with exchangeable rows
type: Item
instance of: scholarly article
title: Spectral gap of sparse bistochastic matrices with exchangeable rows
zbMATH Open document ID: 1465.60006
DOI: 10.1214/20-AIHP1065
author: Charles Bordenave
author: Yanqi Qiu
author: Yiwei Zhang
published in: Annales de l'Institut Henri Poincaré. Probabilités et Statistiques
publication date: 2021-06-03T00:00:00Z
full work available at URL: https://projecteuclid.org/euclid.aihp/1603267245
review text: 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é.
Mathematics Subject Classification ID: 60B20
Mathematics Subject Classification ID: 60C05
Mathematics Subject Classification ID: 05C80
zbMATH DE Number: 7354150
zbMATH Keywords: random bistochastic matrices
zbMATH Keywords: sparsely occupied matrices
zbMATH Keywords: estimates of spectral gaps
zbMATH Keywords: high trace method
zbMATH Keywords: tangled-free paths
reviewed by: Michael Voit
MaRDI profile type: MaRDI publication profile
cites work: Circular law for the sum of random permutation matrices
cites work: A new proof of Friedman's second eigenvalue theorem and its extension to random lifts
cites work: Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs
cites work: The circular law for random regular digraphs
cites work: Harmonic analysis for anisotropic random walks on homogeneous trees
cites work: The eigenvalues of random symmetric matrices
cites work: The single ring theorem
cites work: Support convergence in the single ring theorem
cites work: Brown's spectral distribution measure for \(R\)-diagonal elements in finite von Neumann algebras
cites work: Q4595047
cites work: Structure of eigenvectors of random regular digraphs
cites work: Community detection thresholds and the weak Ramanujan property
cites work: Free probability and random matrices
cites work: Invertibility of random matrices: Unitary and orthogonal perturbations
description: scientific article; zbMATH DE number 7354150