MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Here are two questions about finitely generated and finitely presented groups (FP):

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

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

2) For which $n$ given two subgroups of $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 $GL(n,C)$.

share|cite|improve this question
up vote 23 down vote accepted

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.

share|cite|improve this answer
Greg, thank you for the answer and for the comment to the second part of my question! I guess, I should modify it. I was having in mind the following: It is said that 3-dimensional manifolds are algorithmically recognisible, while 4-manfiolds not, beacause for FPFG groups there is no algorithm to recognise them. So maybe I should reformulate the question like this: Is there an algorithm that recognise linear FPRG groups (i.e. decides for any two such groups if they are isomorphic)? Will this question make more sense? If yes, I will reformulated it like this. – Dmitri Dec 23 '09 at 20:11
Provided you are given the faithful linear representations, not just a promise that they exist, the question could be okay. I.e., "Given two subgroups of GL(n,Q) generated by explicit lists of matrices, together with lists of relations and the promise that they are sufficient, is there an algorithm to determine if they are isomorphic as groups?" Note that for closed hyperbolic 3-manifolds, Mostow rigidity is available, which gives much more information than just linearity. – Greg Kuperberg Dec 23 '09 at 20:19
Greg, may I ask you one more thing? Is there any good exposition, that decribes the result "$G$ is residually linear if and only if it is residually finite". I like a lot the idea of the proof that you have descirbed, but also want to see it written in more detailes. – Dmitri Dec 23 '09 at 23:00
A proof of Malcev's theorem is in a book by Merzlyakov "Рациональные группы" (in Russian, the title translates as "Rational groups"). I do not think there is English translation, so probably Malcev's original paper is the most accessible reference. – Igor Belegradek Dec 24 '09 at 4:43
This Malcev's theorem is explained (nicely, in context of subsequent developments) at least in two places: B.A.F. Wehrfritz, Infinite Linear Groups, Springer, 1973 and A.E. Zalesskii, Linear groups, Russ. Math. Surv. 36 (1981), N5, 63-128. – Pasha Zusmanovich Dec 28 '09 at 12:59

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.

share|cite|improve this answer
David, thanks a lot! – Dmitri Dec 23 '09 at 18:33

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.

share|cite|improve this answer

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!


  • 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.
share|cite|improve this answer
Henry, great answer, huge thanks! – Dmitri Dec 27 '09 at 9:56

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.

share|cite|improve this answer
I can't say that I made a conscious distinction. In any case your reference is good. – Greg Kuperberg Dec 24 '09 at 2:53
Very interesting! This summer in CRIM I heard from somebody (maybe Benson Farb) that while it is unknown that mapping class group is linear, all the possible corrolaries that hold for linear groups also holds for this group. So your answer shows that proving that mapping class group is linear will have some applications :)! – Dmitri Dec 24 '09 at 12:39
There are some highly non-trivial consequences of linearity that are "only just" known for mapping class groups. I'm thinking of the "equationally Noetherian" property, which says that every variety over a group G can be defined using only finitely many equations. This is an immediate consequence of Hilbert's Basis Theorem for linear groups; for mapping class groups, it's a consequence of highly non-trivial forthcoming work of Daniel Groves. – HJRW Dec 26 '09 at 23:45
Mosher constructed hyperbolic surface-by-free groups, and I think the existence of a hyperbolic free-by-surface group is open. (This could be a matter of the two of us having differing terminology.) – Richard Kent Sep 28 '10 at 1:19

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.

share|cite|improve this answer
Igor, thanks a lot for the reference!! – Dmitri Dec 24 '09 at 11:42

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.


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.

share|cite|improve this answer
Steve thanks for the answer. Sure I will be very curious to see the proof, so once you have it, please do leave a link! – Dmitri Feb 5 '10 at 9:30

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!

share|cite|improve this answer
Maharana, thanks for your answer! Well, when I formulated the question I was meaning, "FGFP groups that don't admit a injective homomorphism fo $GL(n,C)$ for ANY n". In this case to consturct an example you surelly need infinite groups. I will modify now the question, so that there is no ambiguity. – Dmitri Dec 25 '09 at 12:28

Your Answer


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.