Suppose that $A_1, \dots, A_k \in M_n(\mathbb{Q})$ and $S$ is the semigroup generated by them. Two questions: are there always a finite set of relations $\{R_i\}$ among the $A_j$ such that $S$ is isomorphic to semigroup $\langle a_1, \dots, a_k  R_i\rangle$? By a relation I mean something of the form $w = w'$ where $w,w'$ are two words. If this is true, is it true that there is a bound on the length of the relations? That is, is there an $l$ which is a function of $n$, and perhaps the maximum absolute values of the entries of the $A_i$ so that we may always find a set of relations $R_i$ of length $\le l$?

$\begingroup$ Looks like it might be undecidable because of the word problem. $\endgroup$ – Steve Huntsman Feb 3 '10 at 22:27

$\begingroup$ But he word problem in matrix rings is trivially decidable. What I really wanted was that if you start listing words in the matrix generators in order of length and looking for coincidences, is there a point when you know that you've found a set of relations which generates them all. $\endgroup$ – Victor Miller Feb 4 '10 at 2:45

$\begingroup$ Thanks for the answer. Yes, I really meant the putative bound to be a function of the height. My original problem (which I didn't state) really involved $M_n(\mathbb{Z})$ so that absolute value would be the same as height. $\endgroup$ – Victor Miller Feb 4 '10 at 14:17

$\begingroup$ There are only finitely many such matrices, so conditional on the first part, there is a function of the height and n, but that doesn't say the function is computable. $\endgroup$ – Douglas Zare Feb 4 '10 at 15:51

$\begingroup$ Ok, to be more specific, the kind of bound that I envision would be something like $H^{kn}$, where $H$ is the maximum height of a generator, $k$ is the number of generators, and $n$ is the dimension of the matrices. If one looks at a commutative case of Siegel's lemma en.wikipedia.org/wiki/Siegel%27s_lemma one gets a bound something like this, so one would expect $k$ and $n$ to enter into the exponent. One the other hand, I suspect that this may be the worse case. If the semigroup is far from being commutative then I might hope that one could do better. $\endgroup$ – Victor Miller Feb 4 '10 at 16:12
Free semigroups on 2 generators have a faithful 2x2 representation over Z by sending the generators to
1 1
0 1
and its transpose. There are finitely generated subsemigroups of this free semigroup that are not finitely presented. I don't know who first proved this, but an example is in http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.98.795&rep=rep1&type=pdf

$\begingroup$ @Benjamin: Thanks. That shows that I was making too general a request. The real question that I'm interested in (should this be a separate MO question?) is: Let $A,B$ be noncommuting $n \times n$ matrices with coefficients in $\mathbb{Z}$ which generate a finite semigroup. Let $G$ denote the semigroup generated by $A+B,AB$. Does $G$ have a finite presentation (with the given generators) with the kind of bound I asked for? $\endgroup$ – Victor Miller Jul 11 '11 at 13:34
You are asking whether there is a faithful matrix representation of a finitely generated semigroup with no finite presentation. I don't know the answer to that. Note that only finitely many relations are needed to specify the representation variety $V_n$, so if the answer is yes, you would get a sequence of finitely presented semigroups with the same representation variety $V_n$, and thus a family of finitely presented semigroups with no faithful representation in dimension $n$. That's not a surprise, but it may be a way to look for an example.
Edit: Let me correct an example I had here before.
There is no bound on the length of relations possible for matrices with entries whose entries are at most 1, since you can represent the additive semigroup generated by 1 and $0\le p/q \le 1$, which is determined by commutativity and $p*1 = q * (p/q)$ in additive notation.
$$1\to \left( \begin{array}{cc} 1 & 1 \\\ 0 & 1\end{array}\right), ~~~~\frac pq \to \left( \begin{array}{cc} 1 & \frac pq \\\ 0 & 1\end{array}\right) $$.
Perhaps a bound would be possible not in terms of the magnitudes of the entries, but some other height function.
This type of example can be embedded in a slightly more complicated fashion when n=1, since you can have relations between 2, 3, and $2^p/3^q$ in the multiplicative semigroup of rationals. If that seems contrived because one of the generators is redundant, take 4, 9, and $2^{2p+1}/3^{2q+1}$.

$\begingroup$ Wait a moment. To represent Z/n over M_m(Q) requires m>= phi(n), I think. So you could imagine a bound which involved the number of generators and the size of the matrices. $\endgroup$ – David E Speyer Feb 4 '10 at 12:32

$\begingroup$ Thanks. I didn't notice the Q instead of C. I replaced that example with a couple of others. $\endgroup$ – Douglas Zare Feb 4 '10 at 13:37