Welcome to MathOverflow

Question

18

7

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$.

flag	asked May 10 2010 at 18:48 Hej 881●3●12

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 2010 at 21:07

1

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 2010 at 23:00

Willie, check this out: hermite.cii.fc.ul.pt/elc/meetings/im_1997/… See the Theorem by Gow and Tamburini on page 6 of that document. – Hej May 11 2010 at 2:23

3

As Victor mentioned, the answer is no. A proof can be found here: journals.cambridge.org/action/… – Hej May 11 2010 at 2:24

Bill Thurston · Accepted Answer · 2010-09-10 17:06:44Z UTC

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: alt text

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.

BS · Answer 2 · 2010-06-01 10:23:17Z UTC

7

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.

edited Jun 1 2010 at 10:23

answered Jun 1 2010 at 10:18

BS
5,313●1●12●25

Please can you cite where or how you found this? – To be cont'd Jul 23 2010 at 14:11

1

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 2010 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 2010 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/…. 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. – To be cont'd Jul 16 2011 at 16:30

Denis Serre · Answer 3 · 2010-09-10 15:38:08Z UTC

4

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$).

answered Sep 10 2010 at 15:38

Denis Serre
18.7k●1●31●93

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

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

3 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.