The Gaussian algorithm tells us, that for any field $k$ a $n\times n$-matrix over $k$ can written as a product of at most $C$ elementary matrices ($C\sim n^2$). I am wondering, whether such a constants also exists for other rings - like $\mathbb{Z}$. Given a matrix $A\in SL_2(\mathbb{Z})$, one can basically use the Euclidean algorithm to find such a decomposition. However if we take a the following matrix involving the Fibonacci numbers, the algorithm takes about $n$-steps and hence we get a decomposition in $\sim n$ factors. But there might still be a better decomposition.

So is there for every $n$ a matrix $A \in SL_2(\mathbb{Z})$, that cannot be written as a product of elementary matrices ?

I guess the construction with the Fibonacci numbers might be a candidate, I don't know how to prove, that it is impossible to decompose it in a better way.


Yes. The group $SL_2(\mathbb Z)$ is virtually free and is not boundedly generated by any finite generating set because of that. You can look at the (very nice) slides of Dave Witte-Morris' talks on bounded generation here.

  • $\begingroup$ The slides also say, that $SL_3(\mathbb{Z})$ (and higher, I guess) is boundedly generated by elementary matrices. ($2$ was just a arbitrary number I picked). $\endgroup$ – HenrikRüping Nov 17 '10 at 15:29
  • $\begingroup$ Yes, that is a remarkable result, and very useful also (one of the proofs of property (T) for $SL_n(\mathbb Z)$, $n\ge 3$, uses it, for example). $\endgroup$ – user6976 Nov 17 '10 at 16:00

Put $a=\left[\begin{array}{cc} 0&-1\\\\1&0\end{array}\right]$ and $b=\left[\begin{array}{cc} 0&-1\\\\1&-1\end{array}\right]$. I think it is known that the group $PSL_2(\mathbb{Z})=SL_2(\mathbb{Z})/\{I,-I\}$ is freely generated by $a$ and $b$ subject only to $a^2=b^3=1$. Probably most very long words in $a$ and $b$ will also need a long list of elementary matrices to represent them.


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.