ASKSAGE: Sage Q&A Forum - Individual question feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 11 Oct 2017 17:29:32 -0500Random element in a finitely generated grouphttps://ask.sagemath.org/question/39117/random-element-in-a-finitely-generated-group/ 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.Wed, 11 Oct 2017 02:47:04 -0500https://ask.sagemath.org/question/39117/random-element-in-a-finitely-generated-group/Answer by dan_fulea for <p>I would like to define a matrix group by some generators, e.g.</p>
<pre><code>gens = [matrix(CDF,2, [1,0, -1,1]), matrix(CDF,2, [1,1,0,1])]; G = MatrixGroup(gens)
</code></pre>
<p>and then to generate random matrices from G. The command</p>
<pre><code>G.random_element()
</code></pre>
<p>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.</p>
https://ask.sagemath.org/question/39117/random-element-in-a-finitely-generated-group/?answer=39128#post-id-39128**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]
]Wed, 11 Oct 2017 16:07:39 -0500https://ask.sagemath.org/question/39117/random-element-in-a-finitely-generated-group/?answer=39128#post-id-39128Comment by Lor for <p><strong>Short answer:</strong></p>
<pre><code>sage: Gamma(1).random_element()
[-13 40]
[-27 83]
</code></pre>
<p><strong>Some comments:</strong></p>
<p>Never walk through the long corridors of the department where people are studying modular forms and elliptic curves with a visible book on <em>numerical approximation</em>. (They will immediately notice it, and kindly help you find the right department. It is so important to keep things clean and structural!) </p>
<p>So why use that <code>CDF</code> to make things uncertainly complicated?</p>
<p>The generators are living in a beautiful ring, <code>ZZ</code>, and here is the best place to make computations. Moreover, the corresponding group is the modular group <code>SL2Z</code>. Mention it!</p>
<p>Let us type some piece of code to investigate the landscape. First of all let us consider the matrices:</p>
<pre><code>L = SL2Z( [1,1,0,1] )
R = SL2Z( [1,0,1,1] )
L, R
</code></pre>
<p>This gives:</p>
<pre><code>(
[1 1] [1 0]
[0 1], [1 1]
)
</code></pre>
<p>The posted generators correspond to:</p>
<pre><code>sage: R^(-1), L
(
[ 1 0] [1 1]
[-1 1], [0 1]
)
</code></pre>
<p>Do $L,R$ generate indeed the full modular group <code>Gamma(1)</code> or <code>SL2Z</code>? We only have to generate the (standard) generators of this group using $L,R$. For this:</p>
<pre><code>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 )
</code></pre>
<p>This gives <code>wT</code> and <code>wS</code> and the representations:</p>
<pre><code>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
</code></pre>
<p>The <code>0</code> stays on the first place of the tuples in the list for the usage of <code>L</code>, the <code>1</code> for <code>R</code>. So <code>(1, -1)</code> means one should use the <code>R</code>, namely to the power <code>-1</code>. The evaluation does the job directly:</p>
<pre><code>sage: T == eval_sl2z_word( wT )
True
sage: S == eval_sl2z_word( wS )
True
</code></pre>
<p>The random element generated above has the representation as follows...</p>
<pre><code>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
</code></pre>
<p>Let us generate many elements, say twelve here:</p>
<pre><code>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]
]
</code></pre>
<p>They never go beyond $\pm 100$? Strange randomizer...</p>
<p>Let us take a closer look at the implemented method:</p>
<pre><code>sage: SL2Z.random_element?
Signature: SL2Z.random_element(bound=100, *args, **kwds)
</code></pre>
<p>and so on, and the first line in the doc tells us what to do. Let us do it six times! </p>
<pre><code>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]
]
</code></pre>
https://ask.sagemath.org/question/39117/random-element-in-a-finitely-generated-group/?comment=39131#post-id-39131Thanks 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)?Wed, 11 Oct 2017 17:29:32 -0500https://ask.sagemath.org/question/39117/random-element-in-a-finitely-generated-group/?comment=39131#post-id-39131