ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sat, 02 Apr 2016 23:04:01 -0500How to efficiently test whether a matrix can be written as a certain type of wordhttp://ask.sagemath.org/question/32935/how-to-efficiently-test-whether-a-matrix-can-be-written-as-a-certain-type-of-word/ I am pretty new to Sage. I plan on learning/practicing more but for now I need a quick way of getting some data, so I'm hoping hoping to get some tips.
Suppose I have a discrete subgroup H of SL(2,C), and I have a subgroup G of H. Both of these groups are finitely generated, and I have a list of generators for each group. Given some element h of H, I want an efficient way of telling whether or not there exists an element g of G such that h=gg* where g* is the conjugate transpose of g. Note that the membership problem is decidable for SL(2,C), but this problem is much easier than finding an algorithm for that general case.
What I did so far is I computed each generator of G in terms of the generators of H by writing a script that went through by word length. I also computed a list of matrices of the form gg* up to words in G up to length 3, but the order in which these show up is not convenient.
So, let h be some element of H, given as a matrix. My plan is to write h in terms of the generators of H, so that I can more easily recognize whether it's of the form I want, by comparing it to the words for the generators of G. But my method of doing this is veeeerry slow, too slow to suit my purposes. An important factor is that there are a *lot* of elements in H that I need to check this on, so I need to be able to run this quickly. Preferably I would define lists of matrices to check, then have a program that just runs through the lists and tells me which ones meet my condition.
I feel like I may be reinventing the wheel in some parts of this, since it seems a fairly common problem to be studying words in matrices. Perhaps there is a pre-built module that has tools I could use but so far I have not found anything.
Thanks in advance.
*My original post had a typo, and said SL(2,Z) rather than SL(2,C). The answer below from @vdelecroix pertains to the original post.*Fri, 01 Apr 2016 02:39:33 -0500http://ask.sagemath.org/question/32935/how-to-efficiently-test-whether-a-matrix-can-be-written-as-a-certain-type-of-word/Answer by vdelecroix for <p>I am pretty new to Sage. I plan on learning/practicing more but for now I need a quick way of getting some data, so I'm hoping hoping to get some tips.</p>
<p>Suppose I have a discrete subgroup H of SL(2,C), and I have a subgroup G of H. Both of these groups are finitely generated, and I have a list of generators for each group. Given some element h of H, I want an efficient way of telling whether or not there exists an element g of G such that h=gg* where g* is the conjugate transpose of g. Note that the membership problem is decidable for SL(2,C), but this problem is much easier than finding an algorithm for that general case.</p>
<p>What I did so far is I computed each generator of G in terms of the generators of H by writing a script that went through by word length. I also computed a list of matrices of the form gg* up to words in G up to length 3, but the order in which these show up is not convenient.</p>
<p>So, let h be some element of H, given as a matrix. My plan is to write h in terms of the generators of H, so that I can more easily recognize whether it's of the form I want, by comparing it to the words for the generators of G. But my method of doing this is veeeerry slow, too slow to suit my purposes. An important factor is that there are a <em>lot</em> of elements in H that I need to check this on, so I need to be able to run this quickly. Preferably I would define lists of matrices to check, then have a program that just runs through the lists and tells me which ones meet my condition.</p>
<p>I feel like I may be reinventing the wheel in some parts of this, since it seems a fairly common problem to be studying words in matrices. Perhaps there is a pre-built module that has tools I could use but so far I have not found anything.</p>
<p>Thanks in advance.</p>
<p><em>My original post had a typo, and said SL(2,Z) rather than SL(2,C). The answer below from <a href="/users/87/vdelecroix/">@vdelecroix</a> pertains to the original post.</em></p>
http://ask.sagemath.org/question/32935/how-to-efficiently-test-whether-a-matrix-can-be-written-as-a-certain-type-of-word/?answer=32950#post-id-32950Hello,
There is actually the membership and word problem implemented for subgroups of SL(2,Z). Though I just discovered that there is a bug in it (see [#20347](http://trac.sagemath.org/ticket/20347)). The code can be used (in principle) as follows
sage: H = ArithmeticSubgroup_Permutation(S2="(1,2)(3,4)",S3="(1,2,3)")
sage: S = H.farey_symbol()
sage: g1, g2 = S.generators()
sage: g = g1^3 * g2
sage: g
[-1 3]
[-4 11]
sage: S.word_problem(g)
(1, 1, 1, 2)
The problem is that the group is not constructed from generators but from the action of the standard generators of SL2Z on cosets. So you have to do that part by yourself. If you indeed write such code, it would be very interesting to have your contribution in Sage source code!
Vincent
PS: the theoretical material can be found in the article of Kulkarni "An arithmetic-geometric method in the study of the subgroups of the modular group" (1991).Fri, 01 Apr 2016 17:49:32 -0500http://ask.sagemath.org/question/32935/how-to-efficiently-test-whether-a-matrix-can-be-written-as-a-certain-type-of-word/?answer=32950#post-id-32950Comment by j0equ1nn for <p>Hello,</p>
<p>There is actually the membership and word problem implemented for subgroups of SL(2,Z). Though I just discovered that there is a bug in it (see <a href="http://trac.sagemath.org/ticket/20347">#20347</a>). The code can be used (in principle) as follows</p>
<pre><code>sage: H = ArithmeticSubgroup_Permutation(S2="(1,2)(3,4)",S3="(1,2,3)")
sage: S = H.farey_symbol()
sage: g1, g2 = S.generators()
sage: g = g1^3 * g2
sage: g
[-1 3]
[-4 11]
sage: S.word_problem(g)
(1, 1, 1, 2)
</code></pre>
<p>The problem is that the group is not constructed from generators but from the action of the standard generators of SL2Z on cosets. So you have to do that part by yourself. If you indeed write such code, it would be very interesting to have your contribution in Sage source code!</p>
<p>Vincent</p>
<p>PS: the theoretical material can be found in the article of Kulkarni "An arithmetic-geometric method in the study of the subgroups of the modular group" (1991).</p>
http://ask.sagemath.org/question/32935/how-to-efficiently-test-whether-a-matrix-can-be-written-as-a-certain-type-of-word/?comment=32968#post-id-32968Interesting, I was hoping something like this had already been done. I made a typo though in my question: I meant to say "discrete subgroup of SL(2,C)" rather than "Z," which I expect makes this much more difficult. I'm going to update my question but of course am up-voting this answer.Sat, 02 Apr 2016 23:04:01 -0500http://ask.sagemath.org/question/32935/how-to-efficiently-test-whether-a-matrix-can-be-written-as-a-certain-type-of-word/?comment=32968#post-id-32968