MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 4 down vote accepted

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.

share|cite|improve this answer
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). – HenrikRüping Nov 17 '10 at 15:29
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). – Mark Sapir 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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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