Mixing time of a random walk on binary matrices
Speaker:
Anna Ben-Hamou, Sorbonne Université
Date and Time:
Tuesday, May 6, 2025 - 4:00pm to 5:00pm
Location:
Fields Institute, Room 230
Abstract:
In this talk, we will consider a Markov chain on invertible n×n matrices with entries in Z2 which moves by picking an ordered pair of distinct rows and adding the first one to the other, modulo 2. This chain was first studied by Diaconis and Saloff-Coste (1996), who showed that the mixing time was O(n4). Then, Kassabov (2003) improved it to O(n3). Building on this last result, we will show that the log-Sobolev constant is O(n2), which yields an upper bound of O(n2logn) on the mixing time. Up to logarithmic factors, this matches the best known lower bound of Ω(n2/logn).