# 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.

• Consider the case of 1 by 1 matrices. You're looking for pairs of scalars $a$ and $b$ such that $ab=1$. What do you mean by "sample uniformly" here? Having said that, you may want to look at randomly generating a matrix decomposition, like SVD or something. – Pseudonym Jul 11 '19 at 6:24
• @Pseudonym, Note that we're working with boolean matrices. Aor $1x1$ matrices, there's only one choice: $A=B=[1]$. So, we're sampling uniformly from a set with one element -- we'll always end with the same value. Not sure if I've answerd your question. I don't quite see how to use a decomposition to solve this problem, but I'd be interested to hear if you come up with something. (For instance, we if we use that every matrix can be expressed in the form $PJP^{-1}$, where $J$ is a Jordan normal form, then we can perhaps sample $J$ but how do we sample $P,P^{-1}$ randomly?) – D.W. Jul 11 '19 at 6:53
• Oh, I didn't spot the boolean part. The decomposition may still work in $GF(2)$. – Pseudonym Jul 11 '19 at 8:39

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.