Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: Rank of a random matrix
Posted:
Jan 18, 2001 8:07 AM


Your Name wrote:
> George Marsaglia wrote: > > > danfux@mydeja.com wrote: > > > > > If one chooses at random an n by n matrix over a finite field K with > > > q=p^m elements what is the expected rank of the matrix ? > > > > > > If this is too complicated maybe I should ask : > > > if 1 <= r <= n how many matrices of rank r there are over K ? > > > > In the 60's, while finding that, for congruential generators, > > random numbers "fall mainly in the planes", I also considered > > shiftregister generators. Their points formed herringbone > > rather than linear patterns in higher dimensions, which was easy > > to picture, but difficult to characterize. An easier one was that, > > in order to ensure long periods, every successive n or fewer points > > viewed as vectors over the finite field {0,1} had to be linearly > > independent. > > So I developed the binary rank test, based on (using TeX notation): > > > > The rank of a random $m\times n$ binary matrix takes > > the value $r=1,2,\ldots,\min(m,n)$ with probability > > $$2^{r(n+mr)mn}\prod_{i=0}^{r1} > > \frac{(12^{in})(12^{im})}{(12^{ir})}.$$ > > > > For mxn matrices over a field with q elements, replace 2 by q. > > The expected rank is then the sum of r*Prob(r) > > > > George Marsaglia



