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
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 5, 2016 at 10:18 | comment | added | Al Tal | To j0equ1nn: the upshot was that if we could find a computable estimation to solve the expressibility (in the case when we know the element is expressible!), we would be able to use it to solve the membership problem in $SL(4,\mathbb{Z})$, which is undecidable. Factually it means that in the bad cases the length of the expression of your element is not bounded by any recursive function (polynomial, exponential, tower exponential...) on the data you are given (norms of the matrices). Still, it might be that you deal with the good cases, when the generator matrices give a nice subgroup. | |
| Apr 1, 2016 at 21:38 | comment | added | j0equ1nn | BTW while this is an informative answer, it does not address the specific question because in the given setup, one knows that the $g$ is generated by the given generators. So we are not trying to determine membership, but rather an efficient way of finding a word of minimal length, knowing that one does exist. | |
| Oct 20, 2015 at 19:13 | comment | added | HJRW | The membership problem for lattices in $PSL_2(\mathbb{C})$ is decidable: see arXiv:1401.2648 . | |
| Oct 20, 2015 at 17:36 | comment | added | j0equ1nn | I suppose that in the algothithm suggested here by @StefanKohl , an upper bound could be expressed exponentially in terms of $n$ and the length of $g$, but since we don't know the length of $g$ this is a moot point. In my application I expect that the $g$ I need to test will be rather short, and I expect I can get the results I need with his algorithm. Also I get to use $\mathrm{PSL}_2(\mathbb{C})$. What might be known about decidability of membership for dimension $m=2$? | |
| Oct 20, 2015 at 15:55 | history | edited | Al Tal | CC BY-SA 3.0 |
added 14 characters in body
|
| Oct 20, 2015 at 12:44 | history | answered | Al Tal | CC BY-SA 3.0 |