# Is the semigroup of nonnegative integer matrices with determinant 1 finitely generated?

The group of $n\times n$ matrices with integer entries and determinant equal to 1, $SL(n,Z)$, is a finitely generated group (in fact, it is generated by 2 matrices). I am interested to know if the semigroup of the matrices in $SL(n,Z)$ where all the entries are nonnegative is also finitely generated. This is true at least in dimension $n=2$.

-
The answer is "no" for $n\geq 3$. I've heard Thurston give an elementary proof based on its action on $Z^n_+$ which eludes me at the moment. – Victor Protsak May 10 '10 at 21:07
how do you generate SL(n,Z) with only two matrices? It is the case for n = 2, but do you have a reference for higher dimensions? – Willie Wong May 10 '10 at 23:00
Willie, check this out: hermite.cii.fc.ul.pt/elc/meetings/im_1997/lectures.pdf See the Theorem by Gow and Tamburini on page 6 of that document. – Hej May 11 '10 at 2:23
As Victor mentioned, the answer is no. A proof can be found here: journals.cambridge.org/action/… – Hej May 11 '10 at 2:24

The question has been amply answered, but perhaps it's worth explaining the geometry of the situation. The positive monoid acts by projective transformations on the $n-1$-simplex (the view of the positve orthant as seen from the origin, and the partially order on the monoid is the order by inclusion of the image under this action. In $R^n$, the image of the simplex spanned by the origin together with the basis vectors cannot contain any interior lattice points. This implies that in the projective action, no proper image can contain its barycenter. This, with its ramifications, gives a strong limitation on images of the entire simplex under the positive monoid.

On the other hand, it's not hard to prove that for $n \ge 3$, the set of images of any face are dense. In fact, using elementary and well-known theory, there is a positive density of $(n-1)$-tuples of lattice points that extend to a basis for $Z^n$, and any such $n$-tuple of positive elements can be extended to a positive basis.

This implies that there is no finite set of generators, because a single image of the $n-1$-simplex can contain at most simplices near the barycenter over a small range of angles. Here's a picture for the 2-dimensional case:

The line segment is the projection of the pair of lattice points $L_1=(285, 684, 112)$ and $L_2 = (764, 318, 949)$ found, by pseudorandom selection from lattice cubes that projected near the targeted segment, subject to the condition that they extend to a free basis.

A third element of a basis can be transformed to be project arbitrarily close to any desired point on the line through the image of $L_1$ and $L_2$ by adding $N*L1 + M*L2$, for suitable $N$ and $M$.

Moreover, this characterize the closure (with respect to the Hausdorff topology) of the set of images of the triangle under the positive monoid: it consists of all triangles spanned by positive free bases, together with set of all line segments contained in the triangle.

-

In fact, there are infinitely many "primes" in this monoid $M$, i.e. elements $a$ such that any decomposition $a=bc$ has b or c invertible in $M$ (hence a permutation matrix). Any such prime is necessarily in any generating set (up to permuting lines and columns).

Exercise : if $n=3$, $\begin{pmatrix} 1 & m & m \\\ m & 1+m^2 & 0 \\\ m & 0 & 1+m^2+m^4 \end{pmatrix}$ with $m\geq1$ is an infinite family of (inequivalent) primes.

-
Please can you cite where or how you found this? – Unknown Jul 23 '10 at 14:11
I found these example in trying to see if elementary matrices and permutations generate all of $M$. Any element of the submonoid they generate has two comparable columns (and lines), and the above matrices were the first counterexamples I found, of the simple form $C=\begin{pmatrix} 1 & x & x \\ x & a & 0 \\ x & 0 & b \end{pmatrix}$. The irreducibility follows also, since if $C=AB$, either line $2$ of $A$ contains two $0$, or column $3$ of $B$ does. But this would imply that $C$ is upper block-triangular, hence product of elementaries and permutations (by red. to the $2\times 2$ case). – BS. Jul 25 '10 at 11:12
correction : This would imply that $A$ or $B$ is upper block-triangular up to permutations, hence a product of elementaries and permutations, and then that $C$ has two comparable lines or columns, which it hasn't. – BS. Jul 25 '10 at 11:16
@BS, thank you for clarification. I saw your answer just today.(if only you used the "@myname" trick, the comment would have reached me at the right time) I am interested in these matrices and once asked about them here mathoverflow.net/questions/26117/prime-undecomposable-matrices. My interest in prime matrices has never dwindled and I would like to know more. Is there a place where one can find more discussion? Thank you. – Unknown Jul 16 '11 at 16:30

See Exercise 28 on my web-site http://www.umpa.ens-lyon.fr/~serre/DPF/exobis.pdf of exercises on matrices. And thanks to BS for having pointed a typo (I wrote $1+m+m^2$ instead of $1+m^2+m^4$).

-