A Markov chain arising from Gaussian elimination
03/10/2022
Consider a Markov chain on the set of n by n invertible matrices mod 2, where in each step, two distinct rows are chosen uniformly at random, and the first row is added to the second mod 2. How does the mixing time grow with n? And how does it change if only test functions that are computable in polynomial time are allowed?