Timeline for What is the most efficient way to factor a matrix into a given set of generators?
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 1, 2016 at 21:44 | comment | added | j0equ1nn | Thanks for the info @StefanKohl, though this is the first I'm learning of RCWA groups. It seems they are quite different from the type of groups I'm working with. While some adaptation of GAP might be possible, as you said implementing the method from scratch should not be too bad, and I think for my immediate goal it would be faster. I'm in a bit of a crunch, just trying to get some data to give cool examples of things (which I know in theory are possible) for a presentation. But I think I'll have a closer look at GAP later on. | |
| Apr 1, 2016 at 12:34 | comment | added | Stefan Kohl♦ | @j0equ1nn: I have not used Sage so far. -- But Sage includes GAP, and e.g. the GAP package RCWA provides an implementation of this method (for rcwa groups, so you may need to adapt it to matrix groups). Implementing the method from scratch should also not be difficult. -- Let me know if you have further questions! | |
| Apr 1, 2016 at 0:06 | comment | added | j0equ1nn | This answer helped me say some stuff about algorithms in a theoretical sense. Now I'm interested in actually implementing them in Sage and I was wondering if you know of a module that facilitates this. Being new to Sage, I'm able to write little programs that do sub-steps of this process but I'm sure there are more efficient techniques. | |
| Oct 22, 2015 at 18:30 | comment | added | j0equ1nn | The algorithm that Stefan gave is the one that works for my purposes, and has cool tricks to reduce run-time. Since there are no other suggestions for shorter algorithms, I say this is a great answer. | |
| Oct 22, 2015 at 18:28 | vote | accept | j0equ1nn | ||
| Oct 19, 2015 at 21:35 | history | edited | Stefan Kohl♦ | CC BY-SA 3.0 |
Added clarification about metric (cf. the comments).
|
| Oct 18, 2015 at 22:48 | comment | added | j0equ1nn | I see, so while $S_1(m)$ does in fact contain the element $gm$, we would detect an intersection involving this word by only considering $mg$. | |
| Oct 18, 2015 at 22:29 | comment | added | Stefan Kohl♦ | @j0equ1nn: Multiplication from one side is enough since you can bring factors to the other side by conjugation, and since the spheres about $1$ with which you take the intersections are closed under cyclic conjugation (i.e. for example if $gh^2$ lies in the spheree, then also $h^2g = (gh^2)^g$ and $hgh = (gh^2)^{h^{-1}})$.. | |
| Oct 18, 2015 at 22:04 | comment | added | j0equ1nn | You're right, that list was incomplete, thanks for the correction. But why would we not need to consider multiplication on the other side in $S_r(m)$? | |
| Oct 18, 2015 at 21:36 | comment | added | Stefan Kohl♦ | @j0equ1nn: Yes, I mean the word metric. (Though you omitted some elements from $S_2(1)$, which is $\{g^2,gh,gh^{-1},g^{-2},g^{-1}h,g^{-1}h^{-1},hg,hg^{-1},h^2,h^{-1}g,h^{-1}g^{-1},h^{-2}\}$, and likewise $S_1(m)$ should be $m S_1(1)$ and have cardinality $4$.) | |
| Oct 18, 2015 at 21:17 | comment | added | j0equ1nn | When you say spheres of radii $r$ about the identity and $m$, I think you mean in the word metric, yes? For example if $G=\langle g,h\rangle$ then $S_1(1)=\{g,g^{-1},h,h^{-1}\}$, $S_2(1)=\{g^2, gh, gh^{-1}, hg, hg^{-1}, h^2\},\dots$ and $S_1(m)=\{gm,g^{-1}m,hm,h^{-1}m,mg,mg^{-1},mh,mh^{-1}\},\dots$. I'd been doing this only considering spheres around $1$ and waiting until I hit $m$. Your suggestion is definitely an improvement as it vastly cuts down the length on later things to check. | |
| Oct 18, 2015 at 13:44 | history | answered | Stefan Kohl♦ | CC BY-SA 3.0 |