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}
> 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
>
--
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
