# Random element in a finitely generated group

This post is a wiki. Anyone with karma >750 is welcome to improve it.

I would like to define a matrix group by some generators, e.g.

gens = [matrix(CDF,2, [1,0, -1,1]), matrix(CDF,2, [1,1,0,1])]; G = MatrixGroup(gens)


and then to generate random matrices from G. The command

G.random_element()


throws the error message: AttributeError: 'FinitelyGeneratedMatrixGroup_generic_with_category' object has no attribute 'random_element' . I think the problem is due to the fact that my group is infinite, since it works fine if I replace the complex numbers by some finite field. Is there a better solution than just randomly multiplying the generators by hands? I am especially interested in time efficiency, since I need to generate many elements.

edit retag close merge delete

Sort by » oldest newest most voted

sage: Gamma(1).random_element()

[-13  40]
[-27  83]


Never walk through the long corridors of the department where people are studying modular forms and elliptic curves with a visible book on numerical approximation. (They will immediately notice it, and kindly help you find the right department. It is so important to keep things clean and structural!)

So why use that CDF to make things uncertainly complicated?

The generators are living in a beautiful ring, ZZ, and here is the best place to make computations. Moreover, the corresponding group is the modular group SL2Z. Mention it!

Let us type some piece of code to investigate the landscape. First of all let us consider the matrices:

L = SL2Z( [1,1,0,1] )
R = SL2Z( [1,0,1,1] )
L, R


This gives:

(
[1 1]  [1 0]
[0 1], [1 1]
)


The posted generators correspond to:

sage: R^(-1), L
(
[ 1  0]  [1 1]
[-1  1], [0 1]
)


Do $L,R$ generate indeed the full modular group Gamma(1) or SL2Z? We only have to generate the (standard) generators of this group using $L,R$. For this:

from sage.modular.arithgroup.arithgroup_perm import eval_sl2z_word, sl2z_word_problem
S, T = SL2Z.gens()
S, T

wT = sl2z_word_problem( T )
wS = sl2z_word_problem( S )


This gives wT and wS and the representations:

sage: wT
[(0, 1)]
sage: wS
[(0, 1), (1, -1), (0, 1), (1, -1), (0, 1), (1, -1), (0, 1), (1, -1), (0, 1)]
sage: T == L
True
sage: S == (L*R^-1)^4*L
True


The 0 stays on the first place of the tuples in the list for the usage of L, the 1 for R. So (1, -1) means one should use the R, namely to the power -1. The evaluation does the job directly:

sage: T == eval_sl2z_word( wT )
True
sage: S == eval_sl2z_word( wS )
True


The random element generated above has the representation as follows...

sage: Z = SL2Z( [ -13, 40, -27, 83 ] )
sage: wZ = sl2z_word_problem( Z )
sage: wZ
[(1, 2),
(0, 12),
(1, 1),
(0, -4),
(0, 1),
(1, -1),
(0, 1),
(1, -1),
(0, 1),
(1, -1)]
sage: R^2 * L^12 * R * L^-4 * (R * L^-1)^3 == Z
True


Let us generate many elements, say twelve here:

sage: [ SL2Z.random_element() for _ in [1..12] ]
[
[  9  77]  [-58  79]  [-72  23]  [11 25]  [73 53]  [ 80 -11]
[-11 -94], [ 11 -15], [ 97 -31], [ 7 16], [84 61], [-29   4],

[ -6   7]  [ 15  62]  [-53  55]  [-80  73]  [ -1  -5]  [-83 -55]
[ 77 -90], [-23 -95], [-80  83], [-57  52], [-16 -81], [ 80  53]
]


They never go beyond $\pm 100$? Strange randomizer...

Let us take a closer look at the implemented method:

sage: SL2Z.random_element?
Signature:      SL2Z.random_element(bound=100, *args, **kwds)


and so on, and the first line in the doc tells us what to do. Let us do it six times!

sage: [ SL2Z.random_element( bound=2017) for _ in [1..6] ]
[
[-607  182]  [  577 -1998]  [  627 -1291]  [ 567 1340]  [ 1093  -663]
[1831 -549], [ -255   883], [ -932  1919], [-278 -657], [ 1670 -1013],

[   29 -1269]
[   33 -1444]
]

more

1

Thanks for this very complete answer. However the two matrices I have written were supposed to be just an example: I am interested in subgroups of SL(2,C) generated by some user-defined matrices, and of course SL(2,Z) was the thing to start with. Do you know if one can play in a similar way with other rank 2 subgroups of SL(2,C)?

( 2017-10-11 17:29:32 -0600 )edit