Ask Your Question

How to efficiently test whether a matrix can be written as a certain type of word

asked 2016-04-01 09:39:33 +0200

j0equ1nn gravatar image

updated 2016-04-03 06:05:51 +0200

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.

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted

answered 2016-04-02 00:49:32 +0200

vdelecroix gravatar image


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). 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!


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

edit flag offensive delete link more


Interesting, 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.

j0equ1nn gravatar imagej0equ1nn ( 2016-04-03 06:04:01 +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


Asked: 2016-04-01 09:39:33 +0200

Seen: 673 times

Last updated: Apr 03 '16