On Tuesday 03 Jul 2012, Dima Pasechnik wrote:
> On Tuesday, 3 July 2012 19:55:54 UTC+8, Javier López Peña wrote:
> > On Tuesday, July 3, 2012 10:53:23 AM UTC+1, Dima Pasechnik wrote:
> >> well, it's not that small, especially for finite fields. E.g. for F_2
> >> and n=3, one only gets 168 invertible matrices out of 512=2^9 in
> >> total... (I can't resist saying that the order of GL(n,q) is
> >> (q^n-1)(q^{n-1}-1)...(q^2-1)(q-1))
> >> So it's not gonna be very fast, also note that computing the determinant
> >> comes at a nonzero cost when matrices are big...
> >
> > I stand corrected. Even in the worst case scenario (with F_2) it still
> > seems that about one in three matrices is invertible,
>
> no. As n grows, the ratio gets much, much worse: e.g. for n=2, q=2:
>
> sage:
> float((2^10-1)*(2^9-1)*(2^8-1)*(2^7-1)*(2^6-1)*(2^5-1)*(2^4-1)*7*3/2^100)
> 8.215872026646278e-15
>
> It's asymptotically 0, as is not hard to see, just look at the behaviour of
> the dominating sequence
> q^n q^{n-1}... q^2 q/q^{n^2}
This analysis doesn't seem right:
sage: j = 0
sage: for i in range(100):
A = random_matrix(GF(2),10000,10000)
if A.rank() == 10000:
j+=1
....:
sage: j
25
Indeed, the *probability* that a *random* binary matrix has full rank is
prod(1-2^i for i in range(1,infinity)) ~= 0.288.
> > so the situation is not too bad. Also, there is no need to compute the
> > determinants, knowing if the rank is full or not is enough.
>
> sure, but for F_2 rank and determinant are essentially equal problems :–)
>
> > So my point is: even if not *very* fast, still seems faster than what we
> > have now, and it is very easy to implement while we think of a better
> > solution.
>
> well, pseudorandom field element generation is not very cheap, and
> generating "good" pseudorandom elements got be be expensive, otherwise
> some (generally believed to be true) conjectures of complexity theory would
> fail.
>
> No, it's not the way to go, unless n is very small: see above.
>
> Dima
>
> > Javier
Cheers,
Martin
--
name: Martin Albrecht
_pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99
_otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF
_www: http://martinralbrecht.wordpress.com/
_jab: martinralbre...@jabber.ccc.de
--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
