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).
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
