[math-fun] What is the probability that
a 32x32 array of random bits over GF(2) is singular? It appears to be non-negligible -- i.e., perhaps 10% ?? (This is mere eyeballing; I haven't done a serious Monte Carlo estimate.) My initial intuition was that it should have been negligible.
Assuming you mean "singular over GF[2]", about 71%. The chance of being non-singular is 29%, or 1/2 * 3/4 * 7/8 * 15/16 * ... cutting off the infinite product after 1 - 1/2^32. The idea: Assume the space spanned by the first 31 rows is full-rank, as large as possible. This is 2^31 vectors. What's the chance that the bottom row is in this set, making the matrix singular? 50%. What's the chance that row 31 is in the space spanned by the first 30 rows (assuming the first 30 rows are full-rank)? 25% Etc. This is a standard infinite product, equal to 1 - 1/2 - 1/4 + 1/32 + 1/128 - 1/4096 - 1/32768 + ... The exponents of 2 are pentagonal numbers, n(3n+-1)/2, and the signs are alternating pairs (after the initial 1). The sum is nice in binary. There's a slightly messier expression for the partial products. The same idea works in GF[p]. Or mod P, for us lowbrow folks. Rich --- Quoting Henry Baker <hbaker1@pipeline.com>:
a 32x32 array of random bits over GF(2) is singular?
It appears to be non-negligible -- i.e., perhaps 10% ??
(This is mere eyeballing; I haven't done a serious Monte Carlo estimate.)
My initial intuition was that it should have been negligible.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Consider the n×n matrices over GF(q). There are q^(n^2) of them. Lets count how many are nonsingular. The first row must not be all zero, so (q^n - 1) possibilities. Suppose we've selected the first k rows. Being linearly independent, they span a k-dimensional space. So there are (q^n - q^k) choices for the (k+1)-th row. Thus the number of nonsingular matrices is (q^n - 1) (q^n - q) (q^n - q^2) ... (q^n - q^(n-1)). There are n factors in this product. We divide each factor by q^n to get the probability that the matrix is nonsingular. (1 - 1/q) (1 - 1/q^2) (1 - 1/q^3) ... (1 - 1/q^n) The product converges nicely as n goes to infinity. For Henry's question, q = 2, n = 32, but n hardly matters, and the probability of being nonsingular is (1/2) (3/4) (7/8) ... = 0.288788, and 0.711212 for being singular. q P(nonsing) P(sing)2^2 0.688538 0.311462 2^3 0.859406 0.140594 2^4 0.933595 0.0664053 0.560126 0.439874 3^2 0.876560 0.123440 3^3 0.961591 0.0384095 0.760333 0.239667 5^2 0.958400 0.041600 7 0.836795 0.163205 -- Gene On Wednesday, July 12, 2017, 7:44:36 AM PDT, Henry Baker <hbaker1@pipeline.com> wrote: a 32x32 array of random bits over GF(2) is singular? It appears to be non-negligible -- i.e., perhaps 10% ?? (This is mere eyeballing; I haven't done a serious Monte Carlo estimate.) My initial intuition was that it should have been negligible.
participants (3)
-
Eugene Salamin -
Henry Baker -
rcs＠xmission.com