Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
add comment

2 Answers 2

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|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
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.