Generate random matrix and its inverse I want to randomly generate a pair of invertible matrices $A,B$ that are inverses of each other.  In other words, I want to sample uniformly at random from the set of pairs $A,B$ of matrices such that $AB=BA=\text{Id}$.

Is there an efficient way to do this?  Can we do it with expected running time approaching $O(n^2)$?

Assume we are working with $n\times n$ boolean matrices (all entries 0 or 1, arithmetic done modulo 2).  I am fine with an approximate algorithm (say, it samples from a distribution exponentially close to the desired distribution).  My motivation is solely curiousity; I have no practical application in mind.



The obvious approach is to generate a random invertible matrix $A$, compute its inverse, and set $A=B^{-1}$.  This has running time $O(n^\omega)$, where $\omega$ is the matrix multiplication constant -- something in the vicinity of $O(n^3)$ in practice.  Can we do better?

An approach that occurred to me is to choose a set $T$ of simple linear transformations on matrices such that, for each $t \in T$, we can apply the modifications $M \mapsto tM$ and $M \mapsto Mt^{-1}$ in $O(1)$ time.  Then, we could set $A_0=B_0=\text{Id}$, and in step $i$, sample a random $t$ from $T$, set $A_{i+1}=tA_i$ and $B_{i+1}=B_it^{-1}$, and repeat for some number of steps (say $O(n^2 \log n)$ iterations).  However I'm not sure how we would prove how quickly this approaches the desired distribution.
Efficient Generation of Random Nonsingular Matrices by Dana Randall covers exactly this topic. In particular Corollary 1.1 states:


  We can uniformly generate a matrix and its inverse in time $2M(n) + \mathbb{E}[O(n^2)]$.


Where $M(n)$ is the time it takes to multiply two $n \times n$ matrices.

Unfortunately this is not better than what you had hoped for.