How do I generate a sparse invertible 10000 by 10000 binary matrix with 30 to 50 non-zeros per row?

Question

How do I generate a sparse invertible 10000 by 10000 binary matrix with 30 to 50 non-zeros per row(uniform distribution)?

What sort of algorithm should I use to do this task?

Brute Force algorithm- Using a random generator, create a such a matrix, and test for invertibility by finding its determinant/Gaussian Elimination.

(I tried this approach, the algorithm never completes within 1 hour, so I gaved up)

Reverse ERO approach- Starting with an identity matrix, do repeated Elementary Row Operations on it until the above is fulfiled.

(I haven't tried this approach yet, it is possible that it will work, but there is simply no way to guarantee that every row will have 30-50 non-zero entries)

Upper triangular approach- Starting with an identity matrix, choose 30-50 random entries in the upper triangular part to be non-zeros, then do row swaps to make them look random

(I tried this approach, but the matrices produced turned out to look very skewed to the right.)

Can anyone think up of any other possible approaches to this problem?

Answer 1

Do you want an invertible matrix $A$ over $\mathbb{Z}/2\mathbb{Z}$ or over $\mathbb{R}$ ? In the first case, the Blue's method seems to be good. Yet, in the second case, it is not, because $\det(A)=\pm 1$ that is far from random.

EDIT. I assume that you want (although my post does not seem to excite you) an invertible matrix over $\mathbb{Q}$. That follows is a better method than above:

STEP 1. We seek randomly a matrix $B$ as you want and s.t., for every $i$, $B[i,i]=0$. Such a matrix has a non-negligible probability of being singular. Fortunately $C=B+I$ is "almost certainly" invertible; yet $C$ often admits the eigenvalue $1$.

STEP 2. Swap rows and swap columns; then the characteristic polynomial of the obtained matrix $A=PCQ$ is "almost certainly" irreducible over $\mathbb{Q}$ and, in particular, $A$ is invertible.

Note that the permutations $P,Q$ must be "dense", otherwise there remain too much $"1"$ on the diagonal and, consequently, your matrix is not random. Write each permutation as a product of $k<n$ transpositions; then the complexity of the calculation of $PC$ (for instance) is the complexity of $n$ swaps, that is $O(n^2)$. On the other hand, I do not know the complexity of the choice of a random permutation.