Mixing time of a matrix random walk generated by elementary transvections

Anna Ben-Hamou · 2025

Read Mixing time of a matrix random walk generated by elementary transvections by Anna Ben-Hamou (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-08185.txt.

Introduction

Anna Ben-Hamou bounds how fast a random walk on matrices settles in a 2025 paper. The walk lives on invertible matrices over a two value field and moves by adding one row to another.

A log Sobolev bound with a clean constant drives the result. It caps the mixing time at a rate growing like the squared size times its log. Row adding steps look humble, yet they shuffle the whole matrix group evenly at that pace. Such bounds matter wherever random matrices must be sampled fairly, from coded messages to randomized algorithms.

Catalog record

CREATORAnna Ben-Hamou
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE12 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-08185

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Mixing time of a matrix random walk generated by elementary transvections Anna Ben-Hamou Abstract . We consider a Markov chain on invertible n × n n\times n matrices with entries in ℤ 2 \mathbb{Z}_{2} which moves by picking an ordered pair of distinct rows and add the first one to the other, modulo 2 2 . We establish a logarithmic Sobolev inequality with constant n 2 n^{2} , which yields an upper bound of O ⁡ ( n 2 ​ log ⁡ n ) O(n^{2}\log n) on the mixing time. 1. Setting and main result We consider a random walk on \Omega=\mathrm{SL}_{n}(\mathbb{Z}_{2}) , the set of invertible binary matrices, generated by elementary transvections: at each time, the walk proceeds by picking two distinct rows at random, and adding one to the other, modulo 2 . Letting E_{i,j} be the n\times n matrix with a 1 in position (i,j) , and 0 elsewhere, the transition matrix P of the walk is defined by P(x,y)\;=\;\begin{cases}\frac{1}{n(n-1)}&\mbox{if $y=(I+E_{i,j})x$ for some $1\leq i\neq j\leq n$,}\\ 0&\mbox{otherwise.}\end{cases} Since the elementary transvections I+E_{i,j} generate \Omega , the chain is irreducible. By symmetry of the matrix P , the uniform distribution \pi over \Omega is the unique stationary distribution. Let us point out here that \Omega is a significant subset of the set of all binary matrices. Indeed \frac{|\Omega|}{2^{n^{2}}}\;=\;\prod_{k=1}^{n}\left(1-2^{-k}\right)\;\approx\;0.288788\,. Since the chain is also aperiodic (see [ 5 , Proposition 4.4] ), the chain converges to \pi as time tends to infinity. To quantify the speed of this convergence, one usually considers the total variation mixing time defined, for all \varepsilon\in(0,1) , by t_{\mathsf{mix}}(\varepsilon)\;=\;\min\{t\geq 0\,,\,\max_{x\in\Omega}\|P^{t}(x,\cdot)-\pi\|_{\mathsf{tv}}\leq\varepsilon\}\,, where \|\mu-\nu\|_{\mathsf{tv}}=\max_{A\subset\Omega}|\mu(A)-\nu(A)| is the total-variation distance. A stronger notion is the \ell_{2} -mixing time defined, for all \varepsilon\in(0,1) , by t_{\mathsf{mix}}^{(2)}(\varepsilon)\;=\;\min\{t\geq 0\,,\,\max_{x\in\Omega}\left\|\frac{P^{t}(x,\cdot)}{\pi(\cdot)}-1\right\|_{2,\pi}\leq\varepsilon\}\,, where \|f\|_{2,\pi}=\left(\sum_{\in\Omega}\pi(x)f(x)^{2}\right)^{1/2} is the \ell_{2} -norm with respect to \pi . By Cauchy-Schwarz inequality, we have t_{\mathsf{mix}}(\varepsilon)\;\leq\;t_{\mathsf{mix}}^{(2)}(2\varepsilon)\,. We obtain the following bound. Theorem 1 . There exists absolute constants A>0 and B>0 such that for all \varepsilon>0 , the \ell_{2} -mixing time of the chain P satisfies t_{\mathsf{mix}}^{(2)}(\varepsilon)\;\leq\;An^{2}\log n+Bn\log\left(\frac{1}{\varepsilon}\right)\,. Theorem 1 comes from an upper bound of O(n^{2}) on the logarithmic Sobolev constant \mathrm{C}_{\mathsf{LS}} of the chain, defined as the smallest constant c>0 such that for all functions f\colon\Omega\to\mathbb{R} , we have \ent_{\pi}(f^{2})\;\leq\;c\,{\mathcal{E}}_{P}(f,f)\,, where \ent_{\pi}(f^{2})=\mathbb{E}_{\pi}[f^{2}\log f^{2}]-\mathbb{E}_{\pi}[f^{2}]\log\mathbb{E}_{\pi}[f^{2}] is the entropy of f^{2} , and where {\mathcal{E}}_{P}(f,f) is the Dirichlet form defined by {\mathcal{E}}_{P}(f,f)\;=\;\frac{1}{2}\sum_{x,y\in\Omega}\pi(x)P(x,y)\left(f(x)-f(y)\right)^{2}\,. By [ 4 , Corollary 3.8] , we have t_{\mathsf{mix}}^{(2)}(\varepsilon)\;\leq\;\frac{\mathrm{C}_{\mathsf{LS}}}{4}\log\log\left(\frac{1}{\pi_{\star}}\right)+\lambda_{*}^{-1}\log\left(\frac{\sqrt{1+2e^{2}}}{\varepsilon}\right)+1\,, where \pi_{\star}=\min_{x\in\Omega}\pi(x) and \lambda_{*} is the absolute spectral gap of P . By [ 5 , Proposition 4.4] and the powerful results of [ 7 , Section 3.2] , we have \lambda_{*}^{-1}=O(n) . Finally, since \pi_{\star}\asymp\frac{1}{2^{n^{2}}} , we see that Theorem 1 will follow from the following proposition. Proposition 2 . The logarithmic Sobolev constant of P satisfies \mathrm{C}_{\mathsf{LS}}\;\lesssim\;n^{2}\,. In the above proposition and in the rest of the paper, the notation u_{n}\lesssim v_{n} means that there exists an absolute constant c>0 such that for all n\geq 1 , we have u_{n}\leq cv_{n} . Interestingly, a crucial ingredient in the proof of Proposition 2 is the bound of O(n) on the Poincaré constant (inverse of the spectral gap), obtained by [ 7 ] . 2. Related work To our knowledge, the chain P was first studied by [ 5 ] , who used a comparison with another chain on \Omega studied by [ 6 ] to get an upper bound of O(n^{2}) on the relaxation time (the inverse of the spectral gap), implying an upper bound of O(n^{4}) on the \ell^{2} -mixing time. Then the results of [ 7 ] on the Kazhdan constant yield an upper bound of O(n) on the relaxation time (inverse spectral gap), and thus of O(n^{3}) on the \ell^{2} -mixing time, which was the best known upper bound for total variation mixing as well. As for the lower bound, a simple counting argument shows that the total-variation mixing time can be lower bounded by \Omega\left(\tfrac{n^{2}}{\log n}\right) (which is actually an estimate of the diameter of the underlying graph, see [ 1 , 3 ] ). It would be interesting to know whether a lower bound of \Omega(n^{2}\log n) holds, and more ambitiously, whether this chain exhibits the cutoff phenomenon. This matrix random walk has also received interest from cryptographers, who have used it in authentication protocols. In cryptography, an authentication protocol involves two parties, a verifier and a prover. The verifier’s goal is to confirm the prover’s identity and to distinguish between an honest and a dishonest prover. A significant subset of authentication protocols, known as time-based authentication protocols, relies on the time it takes the prover to respond to a challenge. Authentication is successful only if the prover answers correctly and fast enough. The protocol proposed by [ 11 ] works as follows: starting with the identity matrix in \text{SL}_{n}(\mathbb{Z}_{2}) , the prover runs the chain with kernel P for a specific duration t . The resulting matrix A_{t} is made public (acting as the public key), but only the prover knows the chain’s trajectory. Then, when he needs to authenticate, the prover requests a binary vector of length n from the verifier, and the challenge is to compute y=A_{t}x quickly. Since the prover is aware of the chain’s trajectory, he can apply the same row operations to x that were used to generate A_{t} , thus providing the correct answer in time t . On the other hand, if t is sufficiently large, a dishonest party may struggle to distinguish A_{t} from a matrix chosen uniformly at random within polynomial time (indicating that the chain is computationally mixed ). In this case, the dishonest party’s best option would be to perform regular matrix-vector multiplication, which typically requires n^{2} operations. Therefore, if the prover selects t as the computational mixing time, and if t is proven to be significantly smaller than n^{2} , the verifier can successfully distinguish between honest and dishonest parties. Given the present result on the total variation mixing time O(n^{2}\log n) , finding the computational mixing time (when only test functions that are computable in polynomial time are allowed) would be very interesting in this context. One may notice that the restricted dynamics on the first k\leq n columns of the matrix is still a Markov chain. For k=1 , [ 2 ] established a cutoff at time \tfrac{3}{2}n\log n with a window of order n . Later, the results of [ 10 ] on finite groups allowed to generalize this cutoff for a fixed number k of columns. Another related chain is the random walk on upper triangular matrices with entries in \mathbb{Z}_{q} (where q\geq 2 is an integer) and ones along the diagonal, where at each step a uniformly chosen row is added to the row above. For q=2 , [ 9 ] showed that the mixing time is O(n^{2}) , and [ 8 ] then obtained optimal bounds for the mixing time both in n and q (we refer the reader to this last paper for more reference on this process). 3. Proof of Proposition 2 Our goal is to show that for all functions f\colon\Omega\to\mathbb{R} , we have \ent_{\pi}(f^{2})\;\lesssim\;n^{2}{\mathcal{E}}_{P}(f,f)\,. So let f\colon\Omega\to\mathbb{R} and let g be the extension of f over the set \Omega^{*} of

Read the complete text