2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Pseudonym Jul 11 at 6:24
  • $\begingroup$ @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?) $\endgroup$ – D.W. Jul 11 at 6:53
  • $\begingroup$ Oh, I didn't spot the boolean part. The decomposition may still work in $GF(2)$. $\endgroup$ – Pseudonym Jul 11 at 8:39
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.