On Tuesday, 3 July 2012 17:45:52 UTC+8, Javier López Peña wrote:
>
> I know little of random methods, but do we really need to make things so
> complicated? As the OP suggests, we might as well just generate matrices
> uniformly at random and discard if not invertible. The set of invertible
> matrices is Zariski open, so the probability of hitting a non-invertible
> matrix should be very small (0 for real or complex matrices, I don't know
> about finite fields).
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...
Dima
>
> I understand this naive method might not be the quickest possible
> algorithm but it is much faster than what we have now and just works, so
> why not implement just that, with the obvious fix so that the MatrixSpace
> doesn't get called over and over?
>
> Cheers,
> J
>
> On Tuesday, July 3, 2012 5:31:39 AM UTC+1, Dima Pasechnik wrote:
>>
>>
>>
>> On Tuesday, 3 July 2012 11:26:54 UTC+8, Dima Pasechnik wrote:
>>>
>>>
>>>
>>> On Tuesday, 3 July 2012 10:36:37 UTC+8, Dima Pasechnik wrote:
>>>>
>>>>
>>>>
>>>> On Tuesday, 3 July 2012 09:56:04 UTC+8, Charles Bouillaguet wrote:
>>>>>
>>>>> > Mhh, why not? If A = LUP we just write AP^-1 = LU, hence for each
>>>>> LU we
>>>>> > construct there are as many As as there are permutation matrices, or
>>>>> am I
>>>>> > missing something (again :))?
>>>>>
>>>>> I am not sure that the LUP decomposition is unique (I understand that
>>>>> the LU is).
>>>>
>>>>
>>>> An invertible matrix need not have an LU decomposition. E.g.
>>>> A=[[0,1],[1,1]] does not have it.
>>>>
>>>> It's evident over F_2: L can only take 2 values, and U can only take 2
>>>> values, so you can't have
>>>> more than 4 different matrices of the form LU :–)
>>>>
>>>
>>> by the way, for generating random elements it might be better to use the
>>> Bruhat decomposition, which is unique. See
>>> http://en.wikipedia.org/wiki/Bruhat_decomposition
>>>
>>>
>> I take the last part back, sorry, it makes little sense.
>> What certainly is doable is the following:
>> 1) uniformly select a random maximal flag
>> 2) uniformly select a random element U in the subgroup stabilizing the
>> "canonical" maximal flag, i.e. the one stabilized by the
>> upper triangular matrices.
>> Then an element MU, for M being a matrix mapping the "canonical" flag to
>> the flag selected at step 1, will be uniformly
>> distributed over the whole group G (as step 1 selects a coset of U in G).
>>
>>
>>
>>>>
>>>>
>>>>> If A has more distinct LUP factorizations than B, then A
>>>>> is more likely to be produced by this process than B....
>>>>>
>>>>> Charles
>>>>>
>>>>
--
To post to this group, send an email to [email protected]
To unsubscribe from this group, send an email to
[email protected]
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
