# Generators for the semigroup $\mathrm{SL}(n,\mathbb{N})$

For $$2\times 2$$ matrices we have the following result.

Any matrix in $$\mathrm{SL}(2,\mathbb{Z})$$ with nonnegative entries can be obtained from $$\mathrm{Id}_2$$ by repeatedly adding one column to another.

Proof: It is enough to prove that if $$\begin{pmatrix} a & b \\ c & d \end{pmatrix}\in\mathrm{SL}(2,\mathbb{Z})\setminus \{\mathrm{Id}_n\}$$ has nonnegative entries, then either $$\begin{pmatrix} a-b & b \\ c-d & d \end{pmatrix} \text{ or }\begin{pmatrix} a & b-a \\ c & d-a \end{pmatrix}$$ has nonnegative entries as well. After this you can finish by induction. Now to prove that, suppose $$a$$ is the biggest entry of the matrix, if $$a=1$$ then we obtain the matrices $$\begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} \tag{\star}$$ and we are done. Otherwise $$a>1$$, hence $$d-c\leq d-bc/a=(ad-bc)/a=1/a$$ from which $$d-c\leq 0$$ and we arrive in the first case. The cases in which the maximal entry is different from $$a$$ are done similarly $$\blacksquare$$

This can be restated as saying that the elementary matrices in ($$\star$$) generate the semigroup $$\mathrm{SL}(2,\mathbb{N})$$. Here $$\mathbb{N}$$ denotes the non-negative integers (including $$0$$).

My question is:

Is it true that $$\mathrm{SL}(n,\mathbb{N})$$ can be generated by elementary matrices, similarly as in the case $$n=2$$?

I would guess this has already been discussed in the literature so a good reference would be enough.

Edit: Probably the question above is stated better in terms of $$\mathrm{SL}^{\pm}(n,\mathbb{N})$$, the set of square $$n\times n$$ matrices with nonnegative integral entries and determinant $$1$$ or $$-1$$.

This set has the following properties:

1. $$\mathrm{Id}_n\in \mathrm{SL}^{\pm}(n,\mathbb{N})$$
2. If $$A\in \mathrm{SL}^{\pm}(n,\mathbb{N})$$ and we change a column of $$A$$ by the addition of it with other column, the result is still on $$\mathrm{SL}^{\pm}(n,\mathbb{N})$$.
3. If $$A\in \mathrm{SL}^{\pm}(n,\mathbb{N})$$ and we switch two columns of $$A$$, the result is still in $$A$$.

The problem is to show that the set $$\mathrm{SL}^{\pm}(n,\mathbb{N})$$ is the minimum set of matrices with this three properties.

Notice that property $$2$$ is equivalent to

1. If $$A\in \mathrm{SL}^{\pm}(n,\mathbb{N})$$ and $$L_{i,j}(1)$$ is the elementary matrix that acts by changing column $$i$$ by the addition of column $$i$$ and $$j$$ (see for example Wikipedia) then $$A\cdot L_{i,j}(1)\in \mathrm{SL}^{\pm}(n,\mathbb{N}).$$

and property 3 is equivalent to

1. If $$A\in \mathrm{SL}^{\pm}(n,\mathbb{N})$$ and $$T_{i,j}$$ is the elementary matrix that acts by switching column $$i$$ and $$j$$ then $$A\cdot T_{i,j}\in \mathrm{SL}^{\pm}(n,\mathbb{N}).$$

As $$L_{i,j}(1), T_{i,j}\in \mathrm{SL}^{\pm}(n,\mathbb{N})$$, the problem above is equivalent to

Every matrix in $$\mathrm{SL}^{\pm}(n,\mathbb{N})$$ can be written as a multiplication of matrices of the form $$L_{i,j}(1)$$ and $$T_{i,j}$$.

As operation 2 and 3 commute with each other. We can put all permutation matrices at the end, then by multiplying them we can use only one permutation matrix. If the final matrix has determinant 1 so will have this permutation matrix. In this way we see that this question is equivalent to the original one stated in terms of $$\mathrm{SL}(n,\mathbb{N})$$.

• What about $\begin{pmatrix} 0&1&0\\0&0&1\\ 1&0&0\end{pmatrix}$? – Mikael de la Salle May 7 '19 at 15:16
• The idea is that the generators will be all the elementary matrices that preserve $\mathrm{SL}(n,\mathbb{N})$. For $n=2$ we don't need permutation matrices because the only even permutation of $\{1,2\}$ is the identity but, as you notice, it appears we can't avoid them for $n\geq 3$. – Walter Simon May 7 '19 at 15:26
• I do not understand your comment. What do you mean by "elementary matrix that preserves $\mathrm{SL}(n,\mathbb{N})$"? – Mikael de la Salle May 7 '19 at 15:44
• Unless somebody points out that the counterexample given by de la Salle is flawed, isn't the answer to the OP's question that the conjecture is false? – Mark Fischler May 7 '19 at 15:53
• I edited the question. I hope it will be more clear now. – Walter Simon May 7 '19 at 16:29

A positive answer would mean that for any $$A\in\mathrm{SL}^\pm(n,\mathbb{N})$$, $$A\neq1$$ there exists $$i,j$$ and some other element $$B\in\mathrm{SL}^\pm(n,\mathbb{N})$$ such that $$A=L_{ij}(1)\cdot B$$ or $$A=B\cdot L_{ij}(1)$$, possibly after some permutation of rows and/or columns of $$A$$.
If, however, one can find an $$A$$ such that $$L_{ij}(-1)\cdot A', A'\cdot L_{ij}(-1) \notin \mathrm{SL}^\pm(n,\mathbb{N})$$ for any $$i,j$$ and any permutation $$A'$$ of columns/rows of $$A$$, then $$A$$ can not be decomposed into the product of $$L_{ij}(1)$$'s and $$T_{ij}$$'s.
A quick computer search reveals that $$A = \begin{pmatrix} 1 & 2 & 1 \\ 0 & 3 & 1 \\ 2 & 0 & 1 \end{pmatrix}$$ is one such matrix.