Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Topic: Rank of a random matrix
Replies: 6   Last Post: Jan 18, 2001 8:09 AM

 Messages: [ Previous | Next ]
 Bijan Mobasseri Posts: 56 Registered: 12/7/04
Re: Rank of a random matrix
Posted: Jan 18, 2001 8:07 AM

> George Marsaglia wrote:
>

> > danfux@my-deja.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
> > shift-register 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+m-r)-mn}\prod_{i=0}^{r-1} > > \frac{(1-2^{i-n})(1-2^{i-m})}{(1-2^{i-r})}.$$
> >
> > 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

Date Subject Author
1/16/01 George Marsaglia
1/17/01 Innocenti Maresin
1/17/01 Innocenti Maresin
1/17/01 Innocenti Maresin
1/18/01 Bijan Mobasseri
1/18/01 Bijan Mobasseri
1/18/01 khatir