Relations in matrix semigroups 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$?
 A: 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
A: 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}$. 
