This research examines the mixing time of Markov chains involving invertible matrices and transvections, indicating significant logarithmic bounds.
We consider a Markov chain on invertible n× n matrices with entries in Z₂ which moves by picking an ordered pair of distinct rows and add the first one to the other, modulo $2$. We establish a logarithmic Sobolev inequality with constant n², which yields an upper bound of O(n²log n) on the mixing time. We also study another chain which picks a row at random and randomize it conditionally on the resulting matrix being invertible, and show that the mixing time is between nlog n and 4nlog n.
No takes yet. Share an insight, caveat, or question.
Anna Ben-Hamou (2025) studied this question.