Indeed. Out of 10 million trials, I just got 7,112,737 singular. My intuition is badly out of whack wrt matrices over GF(2). Random matrices over larger fields -- e.g., reals -- are almost never singular. So now what is the probability that a random non-zero element over GF(2^32) does NOT generate a normal basis? I guess what I'm asking is whether the problem in generating a normal basis is getting a basis at all, or whether it has to do with something else. In other words, what's the difference between foo^(2^i), i=0..31 forming a basis and 32 randomly selected elements of GF(2^32) forming a basis ? At 08:14 AM 7/12/2017, rcs@xmission.com wrote:
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.