[a 32x32 array of random bits over GF(2) is singular?] Responding to Adam Goucher's praise of a sequence of Baez posts expositing q-Hypergeometric applications, I said One goodie that Baez skipped: If an m×n bitmatrix has 1s with probability p and 0s with probability q :=1-p, the matrix will have (mod 2) rank k with probability P[m,n,k] := p^k q^((k - m) (k - n)) QBinomial[m, k, q] QBinomial[n, k, q] QFactorial[k, q] . How could Baez resist presenting yet this other pun on q? I *must* have said this to math-fun because I later(?) said that (eavesdropper) George Andrews reminded me that the identity Sum[P[m,n,k],{k,Min[m,n]}] = 1 is a special case of q Chu-Vandermonde. But I can't find where I said it. m - k + 1 k + 1 (m - k) (n - k) (q ; q) (q ; q) q k n - k P(m, n, k) = --------------------------------------------------. (q; q) n - k -m -n m n + k (q , q ; q) q k = ----------------------- (q; q) k = P(n, m, q). On 2017-07-12 09:31, Eugene Salamin via math-fun wrote:
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.