2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ How about the Upper-Triangular approach, but with random row and column swaps? $\endgroup$ – Blue Jul 2 '15 at 4:24
  • $\begingroup$ Will column swaps preserve the invertibility? $\endgroup$ – Yellow Skies Jul 2 '15 at 4:28
  • $\begingroup$ Yes, column swaps preserve invertibility, just like row swaps. The reason is the same. For the determinant to be zero, the rows or columns must be linearly dependent. The rank-nullity theorem says these are equivalent. Swapping columns cannot change the dependence. $\endgroup$ – Ross Millikan Jul 2 '15 at 4:32
  • $\begingroup$ Column swaps are just row swaps of the transpose. $\endgroup$ – Blue Jul 2 '15 at 4:33
  • $\begingroup$ ah! haha! thanks! $\endgroup$ – Yellow Skies Jul 2 '15 at 4:33
1
$\begingroup$

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.

$\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.