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

  • $\begingroup$ What about $\begin{pmatrix} 0&1&0\\0&0&1\\ 1&0&0\end{pmatrix}$? $\endgroup$ May 7, 2019 at 15:16
  • $\begingroup$ 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$. $\endgroup$ May 7, 2019 at 15:26
  • $\begingroup$ I do not understand your comment. What do you mean by "elementary matrix that preserves $\mathrm{SL}(n,\mathbb{N})$"? $\endgroup$ May 7, 2019 at 15:44
  • 1
    $\begingroup$ 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? $\endgroup$ May 7, 2019 at 15:53
  • $\begingroup$ I edited the question. I hope it will be more clear now. $\endgroup$ May 7, 2019 at 16:29

1 Answer 1


I believe that the answer is negative.

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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .