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$ – Mikael de la Salle May 7 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$ – Walter Simon May 7 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$ – Mikael de la Salle May 7 at 15:44
  • $\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$ – Mark Fischler May 7 at 15:53
  • $\begingroup$ I edited the question. I hope it will be more clear now. $\endgroup$ – Walter Simon May 7 at 16:29

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.