Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose we have integer matrices $A_1,\ldots,A_n\in\operatorname{GL}(n,\mathbb Z)$. Define $\varphi:F_n\to\operatorname{GL}(n,\mathbb Z)$ by $x_i\mapsto A_i$. Is there an algorithm to decide whether or not $\varphi$ is injective?

share|improve this question
7  
The corresponding problem for semigroups is undecidable for $n\geq 3$. I don't know what is known for groups. It is probably open and undecidable. –  Benjamin Steinberg Sep 1 '11 at 0:50
    
Benjamin - I'd be interested in a reference for the semi-group case, if you have one. –  HJRW Sep 1 '11 at 6:01
    
This was proved by Klarner, Birget and Satterfield in IJAC in 1991 for something like n=5 and improved to 3 and upper triangular in iml.univ-mrs.fr/~cassaign/publis/freeness.ps.gz –  Benjamin Steinberg Sep 1 '11 at 13:52
    
Thanks, Benjamin! –  HJRW Sep 1 '11 at 16:26

3 Answers 3

up vote 25 down vote accepted

For $n=1, 2$ the answer is "yes" since the group is virtually free, for $n\ge 3$ the answer is not known (an open problem).

Edit. In fact even for two $n\times n$-matrices the problem is open. Moreover the solution of the following ``easier" problem is not known: for which algebraic integers $\lambda$ the matrices $\left(\begin{array}{ll} 1 & 2\\\ 0 & 1 \end{array}\right)$ and $\left(\begin{array}{ll} 1 & 0\\\ \lambda & 1 \end{array}\right)$ generate a free group (see this paper, for example). The fact that this problem is easier follows from the trivial observation that the group generated by these two matrices is isomorphic to some effectively computable group of $n\times n$-integer matrices for some $n\ge 2$ (depending on the degree of the algebraic number $\lambda$).

share|improve this answer
1  
It's not clear for me that's it's easier. It might happen that for each n there's an algorithm in GL(n,Z) to detect free groups (as in the initial question) but that this algorithm does not depend recursively on n. –  YCor Sep 3 '11 at 21:43
1  
@Yves: The size of the matrices is the degree of the $\lambda$. There is currently no hope to resolve the problem even if the degree is 3. –  Mark Sapir Sep 4 '11 at 4:48

Here are some general facts that may be relevant.

Given a finitely presented group $G$ and a representation $\rho:G\to GL_n(\mathbb{Z})$, there is no algorithm which is uniform in $n$ that decides whether or not $\rho$ is injective.

However, this leaves open the possibility that there is such an algorithm for particular $n$. (It's easy for $n=2$, when the group is virtually free. I believe nothing is known for $n>2$.) Also, the examples we construct are not free groups, so it may be possible to say something in that case.

In another direction, given a finite presentation for a group $G$ and a solution to the word problem in $G$, one can algorithmically determine whether or not $G$ is a free group.

share|improve this answer

Some comments on the question 'Is it decidable whether or not a collection of integer matrices generates a free group?'

Given a finite set of matrices S over a field, the problem of testing whether the group H generated by S contains a free non-abelian subgroup is decidable. An algorithm solving the problem as well as its implementation (in Magma) available. Notice that the algorithms does not construct a free non-abelian subgroup in H but justifies its existence. As to testing freeness of finitely generated linear groups then the problem has quite a long history. I may recommend as a start point the paper by John Dixon Can.J Math, v. 37, n. 2, 1985, 238-259 (see p. 240 there, and then follow the references).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.