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$.
5
3 Answers
$\begingroup$
$\endgroup$
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 http://dl.dropbox.com/u/5390048/MatrixSemigroup.jpg
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.
answered Sep 10, 2010 at 17:06
$\begingroup$
$\endgroup$
4
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.
-
$\begingroup$ Please can you cite where or how you found this? $\endgroup$– UnknownCommented Jul 23, 2010 at 14:11
-
1$\begingroup$ 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). $\endgroup$– BS.Commented Jul 25, 2010 at 11:12
-
$\begingroup$ 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. $\endgroup$– BS.Commented Jul 25, 2010 at 11:16
-
$\begingroup$ @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. $\endgroup$– UnknownCommented Jul 16, 2011 at 16:30
$\begingroup$
$\endgroup$
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
hermite.cii.fc.ul.ptin a comment above seems to be broken, but a snapshot is saved on the Wayback Machine $\endgroup$