How to uniformly sample from singular matrices

Question

I would like to uniformly sample from all singular n by n Bernoulli matrices (that is each entry is 1 or 0 with probability 1/2). I could of course just sample from all n by n Bernoulli matrices and reject those that are non-singular but for any moderate n that is extremely inefficient.

As an example, of the 10000 random 100 by 100 matrices I tested, none were singular.

Is there an efficient way to do this?

Here is some test python code to show the problem.

import numpy as np
iters = 10000
n = 100
count = 0
for i in xrange(iters):
    A = np.random.randint(2, size = (n,n))
    if (np.linalg.matrix_rank(A) < n):
        count += 1
print count

Posted to https://mathoverflow.net/questions/155185/how-to-sample-uniformly-from-singular-matrices on Jan 20.

---

https://mathoverflow.net/questions/155185/how-to-sample-uniformly-from-singular-matrices now has a suggested algorithm to solve this problem. The remaining challenge is to work out how to implement it.

Answer 1

The comments drifted away a bit, so I'm posting this as an answer:

There is a paper here: http://www.researchgate.net/publication/2729950_Efficient_Generation_of_Random_Nonsingular_Matrices/file/e0b4951d5a6fcc7e67.pdf that describes how to generate non-singular, and, as an extension, singular matrices over finite fields. Since in programming real numbers are, to some extent, finite, so I think it should be applicable here.