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