Newsgroups: sci.math.num-analysis
From: haoyuep@aol.com (Dan Hoey)
Date: Apr 15, 2000 11:40 PM
Subject: Re: Q: Inverse of large, sparse boolean matrix

[My regrets to anyone who sees this twice.  It seems AOL does not
 do crossposting.]

Robert Israel wrote:
> Dan Hoey writes:
> > Robert Israel wrote:
> > > A way to produce an NxN matrix with 3 ones in each row and
> > > column, all such matrices being equally likely is this:
> > > 1) Let p be a random permutation of 1 .. 3N.
> > > 2) For i from 1 to 3N let q[i] = ceil(p[i]/3)
> > >    (where ceil(x) is the least integer >= x)
> > > 3) If for any i from 1 to N, q[3i-2],q[3i-1] and q[3i] are not
> > >    all distinct, reject p and return to step (1).
> > > 4) For i from 1 to N let A[i,q[3i-2]], A[i,q[3i-1]] and
> > >    A[i,q[3i]] be 1.

> > Ouch!  You're going to spend a long time looking for those needles
> > in that haystack.  Lots of needles, but lots and lots of hay.

[ ... my method snipped ... ]

> Ouch yourself!  You have to calculate  Theta(N^3) of these numbers.
> My way should be (on the average) only O(N) (assuming your
> random-permutation generator is O(N)).
> For large N, the probability of a "collision" at i, i.e. q[3i-2],q[3i-1]
> and q[3i] not all distinct, is approximately 2/N.  Thus a random
> permutation will have, on average, 2 collisions.  The collisions are
> not independent, so approximation by a Poisson distribution is _not_
> justified, but it's probably OK anyway: this would indicate that the
> probability of success (i.e. no collisions) is approximately exp(-2).
> I tried a numerical example, and this seems to be right.  So my method
> requires, on average, exp(2) < 7.4 tries to get a good permutation.
> Quite feasible.

Ouch indeed.  I developed my algorithm because I didn't have this
analysis, and I wanted to know how many times your method would
attempt a permutation before finding an acceptable one.
I figured that taking f(N) as the number of NxN three-ones-per-row
three-ones-per-column matrices,  I should take (3N)! / (f(N) 3!^N) to
account for your method ignoring the order of triplets of columns.
I could see the number increasing exponentially.  But now
that you mention it,  I should have divided by another 3!^N to account
for forgetting the order of triplets of rows.  Here are some of the
results of the corrected formula:

  N (3N)! / (f(N) 36^N)

 10 8.737951
 20 8.010789
 50 7.626193
100 7.505789

which indeed seems to be about exp(2) + 11.5/N + 17/N^2.

Sorry for my mistaken analysis.

Dan Hoey (haoyuep@aol.com)  Posted and e-mailed.