On Tue, Jul 3, 2012 at 5:19 AM, Dima Pasechnik <dimp...@gmail.com> 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}
>
>
>>
>> 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.
You don't have to re-generate the entire matrix, you could likely get
away with changing one random element at a time. (And if you did so,
perhaps computing the rank would be cheaper). Still, +1 to it's much
faster than what we have now and still easy to implement.
- Robert
--
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
