Question

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.

Answer 1

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.

Answer 2

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.