Finitely presented sub-groups of $\operatorname{GL}(n,C)$ Here are two questions about finitely generated and finitely presented groups (FP):

*

*Is there an example of an FP group that does not admit a homomorphism to $\operatorname{GL}(n,C)$ with trivial kernel for any n?

The second question is modified according to the sujestion of Greg below.


*For which $n$ given two subgroups of $\operatorname{GL}(n,C)$ generated by explicit lists of matrices, together with finite lists of relations and the promise that they are sufficient, is there an algorithm to determine if they are isomorphic as groups?"

In both cases we don't impose any conidtion on the group (apart from been FP), in particular it need not be discrete in $\operatorname{GL}(n,C)$.
 A: This survey by Chuck Miller discusses among other things the isomorphism problem for linear groups (and for other classes of groups as well). The flow chart on page 31 states that for finitely generated linear groups the isomorphism problem is generally unsolvable, while it seems that for finitely presented linear groups the isomorphism problem is open. 
Incidentally, finitely presented groups are by definition finitely generated (they have finite presentation), so I think FGFP is just FP. 
A: Here is a more complete picture to go with David's and Richard's answers.
It is a theorem of Malcev that a finitely presented group $G$ is residually linear if and only if it is residually finite.  The proof is very intuitive:  The equations for a matrix representation of $G$ are algebraic, so there is an algebraic solution if there is any solution.  Then you can reduce the field of the solution to a finite field, as long as you avoid all primes that occur in the denominators of the matrices.
The same proof shows that $G$ has no non-trivial linear representations if and only if it has no subgroups of finite index.  So Higman's group has this property.
A refined question is to find a finitely presented group which is residually finite, but nonetheless isn't "linear" in the sense of having a single faithful finite-dimensional representation.  It seems that the automorphism group of a finitely generated free group, $\text{Aut}(F_n)$, is an example.  Nielsen found a finite presentation for this group, it is also known to be residually finite, yet Formanek and Procesi showed that it is not linear when $n \ge 3$.  More recently, Drutu and Sapir found an example with two generators and one relator.
A: The following counterexample is due to Higman; I learned about it from Terry Tao's blog.
Consider the group with generators $a$, $b$, $c$ and $d$, and relations
$ab=b^2a$, $bc=c^2 b$, $cd=d^2c$ and $da=a^2d$. This group is infinite (in fact, the subgroup generated by $a$ and $c$ is free), but it has no nontrivial map to $GL_{n}(\mathbb{C})$. 
See Terry's post, especially Remark 2, for a very nice exposition of this fact.
A: Another nice example is the Baumslag-Solitar group $\langle a,b \ | \ ab^2a^{-1} = b^3 \rangle$, which isn't hopfian, and so isn't residually finite, and so can't be linear.
A: You can combine the Bridson--Miller paper that Agol mentions with recent work of Haglund and Wise to show that the algorithmic problem in part (2) of the question is not always solvable.  Haglund and Wise's version of the Rips Construction takes as input any finitely presented group Q and outputs a short exact sequence
1 -> K -> G -> Q -> 1
where K is finitely generated (and infinite) and G is a torsion-free, word-hyperbolic subgroup of GL(n,Z).  Taking Q to be a non-abelian free group, the resulting G will work as input for the Bridson--Miller result.
So you don't need to prove that mapping class groups are linear!
Remarks


*

*It's not clear how small you can take n to be.  It will be fairly large in this construction.

*In forthcoming work of Bridson and yours truly in a similar vein, we show that the hypotheses of part (2) are actually quite difficult to achieve.  We produce a sequence of finite sets of integer matrices that each generate a finitely presentable group, but such that there is no algorithm to compute a presentation for these groups.

A: I just wanted to make a comment on Mal'cev's theorem (if I could leave this as a comment, I would).
Mal'cev's paper is a great exposition of the theorem, as well as a lot of other related material, all written in a basic yet enlightening style.
Also, if you know a little commutative algebra (as in the Nullstellensatz, the one given in Eisenbud pg. 132), there is quick and easy proof of Mal'cev's theorem. I could sketch it if necessary, but I am right now in the process of LaTeX-ing it, so I'll probably just come back and post a link.
Steve
EDIT - a sketch of the argument:
Mal'cev's theorem says a finitely generated linear group is residually finite. So let $X\subset GL(n,F)$ be a finite subset of the general linear group over some field $F$, and $G=\langle X \rangle$.  First, make $X$ symmetric, so that if $x\in X$ then also $x^{-1}\in X$.  Each $x\in X$ is an $n\times n$ matrix, so we can assemble all entries from all elements of $X$, getting a finite subset of $F$.  Let $R$ denote the subring of $F$ generated by this subset (along with $1$).  Then $R$ is a Jacobson ring, and since it's a subring of $F$, it's Jacobson radical is $0$.  Now $G$ is  a subgroup of $GL(n,R)$;  let $g\in G$ be a non-identity element, so that $g-I_n\neq 0$, where $I_n$ is the identity matrix.  Thus $g-I_n$ has a non-zero element, and thus there is some maximal ideal $m\subset R$ not containing this non-zero element.  The matrix ring homomorphism $M_n(R)\rightarrow M_n(R/m)$ (reducing everything mod $m$) induces a group homomorphism $G\rightarrow GL(n,R/m)$, where $g$ is not in the kernel. But $R/m$ is finite (by the Nullstellensatz), so $GL(n,R/m)$ is a finite group.
A: This paper shows that the answer to 2) is false in the category of finitely presented residually finite groups. As Greg points out, this is different from the category of finitely presented linear groups though.
Addendum: In a paper of Bridson and Miller (which I found from Igor's link to Miller's survey), they show that the isomorphism problem for subgroups of $\Gamma\times\Gamma\times F$ is undecidable, where $\Gamma$ is a particular hyperbolic group (which is free-by-finitely generated) and $F$ is free. As mentioned in the paper, Mosher constructed free-by-surface hyperbolic groups, which therefore could work as $\Gamma$. These groups embed in the mapping class group of the once-punctured surface, so if mapping class groups of once-punctured surfaces are linear, this would answer 2). However, the only mapping class groups known to be linear are the punctured sphere/braid groups and the genus 2 mapping class group.
A: Excuse me guys, but I think it is true that the permutation groups $S_m$ will not admit a faithful representation in dimension $n$ if $m>>n$? I can certainly see this for $m>2n$ atleast. So this will give countably many examples of finitely presented groups not admitting injective homomorphism to $GL(n,C)$ as Dmitri wanted in his question (1). My claim can be seen by either an elementary combinatorial calculation on the involution on the respective spaces or by classification of irreducible representation of $S_n$(that they are either the identity, sign or the standard ones). We don't have to invoke any high powered theorem to do this IMHO. Cheers! 
