Ask Your Question
1

Random element in a finitely generated group

asked 2017-10-11 09:47:04 +0200

this post is marked as community wiki

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 flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
1

answered 2017-10-11 23:07:39 +0200

dan_fulea gravatar image

Short answer:

sage: Gamma(1).random_element()

[-13  40]
[-27  83]

Some comments:

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]
]
edit flag offensive delete link more

Comments

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

Lor gravatar imageLor ( 2017-10-12 00:29:32 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2017-10-11 09:47:04 +0200

Seen: 3,990 times

Last updated: Oct 11 '17