<p>This is usually called the (constructive) membership problem (rather than a "factorization" problem). The membership problem is to decide whether $C \in \langle A,B \rangle$; the constructive membership problem is to actually find a word (if any) in $A,B$ that equals $C$. </p>

<p>Its complexity may depend on whether you want to allow $A^{-1}, B^{-1}$ in your word (in which case it is the membership problem for a subgroup of a general linear group) or not (in which case it is the membership problem for a sub<em>monoid</em> or sub<em>semigroup</em> of a general linear group).</p>

<p>I don't know a complete answer to your question, but here are some special cases and hopefully relevant references:</p>

<ul>
<li><p>In general, the membership problem in linear groups over infinite fields is undecidable [<a href="http://iopscience.iop.org/article/10.1070/SM1968v004n02ABEH002788" rel="nofollow noreferrer">Mihailova, 1968</a>]. I do not know whether undecidability holds for the case of 2-generated subgroups.</p></li>
<li><p>The Tits alternative implies that the group generated by $A,B$ is either solvable-by-finite, or contains a nonabelian free group. The intro of <a href="http://www.math.rwth-aachen.de/~Markus.Kirschmer/papers/freemat.pdf" rel="nofollow noreferrer">Eick-Kirschmer-Leedham-Green</a> contains pointers to algorithms that solve the Tits alternative for subgroup of $GL_n(\mathbb{Q})$, in the sense of deciding which of the two cases holds. </p></li>
<li><p>In the solvable-by-finite case, the membership problem is decidable [Kopytov, 1968].</p></li>
<li><p>In the free case less is known. Eick, Kirschmer, and Leedham-Green ("<a href="http://www.math.rwth-aachen.de/~Markus.Kirschmer/papers/freemat.pdf" rel="nofollow noreferrer">The constructive membership problem for discrete free subgroups of rank 2 of $SL_2(\mathbb{R})$</a>") give an efficient-in-practice algorithm for 2-generated subgroups of $SL_2(\mathbb{R})$ that are not only free but also discrete.</p></li>
<li><p>If $A,B$ commute, then <a href="https://doi.org/10.1109/SFCS.1994.365699" rel="nofollow noreferrer">Cai-Lipton-Zalcstein [FOCS 1994]</a> show how to solve even the constructive subsemigroup membership problem in P. If $A,B$ don't commute, it's not even clear to me whether your problem is in NP, as it's not obvious to me that the desired word is polynomial-length nor has a polynomial-length description.</p></li>
<li><p>See also the <a href="http://www.birs.ca/workshops/2014/14w5031/report14w5031.pdf" rel="nofollow noreferrer">final report of a 2014 Banff workshop on algorithms for linear groups</a>.</p></li>
</ul>

<p>(PS - If by "falls under Ladner's theorem" you mean "is likely to be NP-intermediate" (in the sense of being in NP but neither being in P nor being NP-complete), that's an unusual phrase, but I know what you meant. But, in case you're not aware, essentially <em>no</em> natural problem is known to have this status, even under standard complexity assumptions (such as PH not collapsing). See <a href="https://cstheory.stackexchange.com/q/79/129">here</a> for a list of natural problems that are currently candidates for being NP-intermediate.)</p>

CC BY-SA 3.0
2017-04-17T17:19:39.327Z
Wow, thanks for all of the references. This is perfect
Ben Kushigian
CC BY-SA 3.0
2017-04-17T17:45:51.900Z
@BenKushigian: Happy to help. If you a find a more complete answer to your specific question, I'd be interest to hear, so please post it here!
Joshua Grochow
CC BY-SA 3.0
2017-04-16T21:55:30.923Z
2017-04-18T13:42:17.193Z
2017-04-18T13:42:17.193Z
Joshua Grochow
<p>In particular, if I have some char-0 field $k$ (let's take $\mathbb C$ for now) and I consider $G = GL_2(k)$ with arbitrary nontrivial distinct $A, B \in G$. Then for some $C \in GL_2(k)$ do we know the time complexity of factoring it into a product of $A$s and $B$s is (or showing that such a factorization does not exist); that is, how long would it take to exhibit the product (or show the lack of existence)</p>

<p>$$ABBAAAB\cdots BAAB = C?$$</p>

<p>I have a feeling that this falls under Ladner's theorem but I'm not sure.</p>

<matrices><factoring><complexity>
What's the complexity of factoring over a set of generators (say in $GL_2$)?
Ben Kushigian
# What's the complexity of factoring over a set of generators (say in $GL_2$)?

(Asked by: username_0 on 2017-04-15)

In particular, if I have some char-0 field $k$ (let's take $\mathbb C$ for now) and I consider $G = GL\_2(k)$ with arbitrary nontrivial distinct $A, B \in G$. Then for some $C \in GL\_2(k)$ do we know the time complexity of factoring it into a product of $A$s and $B$s is (or showing that such a factorization does not exist); that is, how long would it take to exhibit the product (or show the lack of existence)

$$ABBAAAB\cdots BAAB = C?$$

I have a feeling that this falls under Ladner's theorem but I'm not sure.

**Tags:** matrices, factoring, complexity


---

## 1 answers

### Answer by username_1 on 2017-04-16. Score: 6 | Accepted answer

This is usually called the (constructive) membership problem (rather than a "factorization" problem). The membership problem is to decide whether $C \in \langle A,B \rangle$; the constructive membership problem is to actually find a word (if any) in $A,B$ that equals $C$.

Its complexity may depend on whether you want to allow $A^{-1}, B^{-1}$ in your word (in which case it is the membership problem for a subgroup of a general linear group) or not (in which case it is the membership problem for a sub*monoid* or sub*semigroup* of a general linear group).

I don't know a complete answer to your question, but here are some special cases and hopefully relevant references:

* In general, the membership problem in linear groups over infinite fields is undecidable [[Mihailova, 1968](http://iopscience.iop.org/article/10.1070/SM1968v004n02ABEH002788)]. I do not know whether undecidability holds for the case of 2-generated subgroups.
* The Tits alternative implies that the group generated by $A,B$ is either solvable-by-finite, or contains a nonabelian free group. The intro of [Eick-Kirschmer-Leedham-Green](http://www.math.rwth-aachen.de/~Markus.Kirschmer/papers/freemat.pdf) contains pointers to algorithms that solve the Tits alternative for subgroup of $GL\_n(\mathbb{Q})$, in the sense of deciding which of the two cases holds.
* In the solvable-by-finite case, the membership problem is decidable [Kopytov, 1968].
* In the free case less is known. Eick, Kirschmer, and Leedham-Green ("[The constructive membership problem for discrete free subgroups of rank 2 of $SL\_2(\mathbb{R})$](http://www.math.rwth-aachen.de/~Markus.Kirschmer/papers/freemat.pdf)") give an efficient-in-practice algorithm for 2-generated subgroups of $SL\_2(\mathbb{R})$ that are not only free but also discrete.
* If $A,B$ commute, then [Cai-Lipton-Zalcstein [FOCS 1994]](https://doi.org/10.1109/SFCS.1994.365699) show how to solve even the constructive subsemigroup membership problem in P. If $A,B$ don't commute, it's not even clear to me whether your problem is in NP, as it's not obvious to me that the desired word is polynomial-length nor has a polynomial-length description.
* See also the [final report of a 2014 Banff workshop on algorithms for linear groups](http://www.birs.ca/workshops/2014/14w5031/report14w5031.pdf).

(PS - If by "falls under Ladner's theorem" you mean "is likely to be NP-intermediate" (in the sense of being in NP but neither being in P nor being NP-complete), that's an unusual phrase, but I know what you meant. But, in case you're not aware, essentially *no* natural problem is known to have this status, even under standard complexity assumptions (such as PH not collapsing). See [here](https://cstheory.stackexchange.com/q/79/129) for a list of natural problems that are currently candidates for being NP-intermediate.)

> **Comments:**
> **username_0**: Wow, thanks for all of the references. This is perfect  
> **username_1**: @BenKushigian: Happy to help. If you a find a more complete answer to your specific question, I'd be interest to hear, so please post it here!  

---

