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?