I want to randomly generate a pair of invertible matrices $ A, B $ Which are inverses to 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 the expected execution time approaching? $ O (n ^ 2) $?

Suppose we are working with $ n times n $ Boolean matrices (all entries 0 or 1, arithmetic made module 2). I'm fine with an approximate algorithm (for example, sample of an exponentially close distribution to the desired distribution). My motivation is only curiosity; I have no practical application in mind.

The obvious approach is to generate a random invertible matrix. $ A $, calculates its inverse, and establishes $ A = B ^ {- 1} $. This has execution 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?

One approach that I came up with is to choose a set. $ T $ of simple linear transformations in matrices so that, for each $ t in T $, we can apply the modifications. $ M mapsto tM $ Y $ M mapsto Mt ^ {- 1} $ in $ O (1) $ hour. Then, we could put $ A_0 = B_0 = text {Id} $, and in step $ i $, show a chance $ t $ since $ T $establish $ A_ {i + 1} = tA_i $ Y $ B_ {i + 1} = B_it ^ {- 1} $, and repeat for some steps (for example, $ O (n ^ 2 log n) $ iterations). However, I'm not sure how we would test how quickly this approaches the desired distribution.