Mixing time of a random walk on binary matrices
In this talk, we will consider a Markov chain on invertible $n\times n$ matrices with entries in $\mathbb{Z}_2$ 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(n^4)$. Then, Kassabov (2003) improved it to $O(n^3)$. Building on this last result, we will show that the log-Sobolev constant is $O(n^2)$, which yields an upper bound of $O(n^2\log n)$ on the mixing time. Up to logarithmic factors, this matches the best known lower bound of $\Omega(n^2/\log n)$.