length of decompositions into elementary matrices

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.
• 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.