On Tuesday, 3 July 2012 07:46:48 UTC+8, Martin Albrecht wrote: > > Hi, > > On Tuesday 03 Jul 2012, Simon King wrote: > > Hi! > > > > On 2012-07-02, Martin Albrecht wrote: > > > Shouldn't both give the same distribution mod p? Since every > non-singular > > > matrix A has a LU decomposition we should be able to just sample L and > U > > > separately to produce A? > > > > Sorry for my ignorance, but is it really the case that an LU > > decomposition exists for all invertible matrices? I thought there may > > only be an LUP decomposition. > > Argh, yes, you're right: should be LUP.
> > If I am not mistaken, the LU decomposition is unique if one requires > > that L (or U) has only 1 on the diagonal. Because of the uniqueness, I'd > > expect that putting 1 on the diagonal of L and choosing the entries of U > > and the remaining of L randomly equally distributed yields a reasonable > > distribution of invertible matrices. > > > > However, if it is really the case that we must consider LUP > > decompositions, then I am not totally convinced that a nicely > distributed > > random choice of a permutation matrix P on top of the choice of L and U > as > > above yields a nice distribution of invertible matrices. > > 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 :))? > P can be taken to be identity iff the leading principal minors of A are non-0. Thus LU (say, with diag(L)=(1,...,1)) gives you a random matrix from this class. So if you are content with sampling from such subclass, LU suffices. There is, in fact, a big industry in the theory of finite groups that handles these kinds of questions. Dima > > Cheers, > Martin > > -- 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
