# How to show that $\mathrm{SL}(2,\mathbb Z) = \langle A, B\rangle$?

Show, that if $\mathbf{A}= \left( \begin{array}{cc} 1&1\\ 0&1 \end{array} \right)$, $\mathbf{B}= \left( \begin{array}{cc} 0&1\\ -1&0 \end{array} \right)$ and $\mathrm{SL}(2, \mathbb{Z}) := \{ \mathbf{C}\in\mathrm{M}(2\times 2;\mathbb{Z})\, |\, \det(\mathbf{C}) = 1\}$ then $\langle\mathbf{A}, \mathbf{B}\rangle = \mathrm{SL}(2, \mathbb{Z})$.

I found this exercise in a textbook for linear algebra in a chapter about the determinant, so it should be solved rather elementarily and without any deeper understanding of group theory ($\mathrm{SL}(2, \mathbb{Z})$ is defined only for the exercise). Showing $\langle\mathbf{A}, \mathbf{B}\rangle \subseteq \mathrm{SL}(2, \mathbb{Z})$ was easy but I got stuck with the opposite direction. Any help would be appreciated.

-
Are you sure this result is true? Something about it seems fishy to me. Too may degrees of freedom in SL(2,Z) for my liking. –  user22805 Jun 17 '12 at 11:27
I compared again with the book and it looks correct to me but if you can show that it is false, I am also happy. :) –  frank Jun 17 '12 at 11:38
Just checking, is $\langle A,B \rangle = \{ A^m B^n : m,n \in \mathbb{Z} \}$ ? –  Ragib Zaman Jun 17 '12 at 11:47
$\langle\mathbf{A},\mathbf{B}\rangle$ is surely "the group generated by A and B". –  Hurkyl Jun 17 '12 at 11:49
@David: If it helps, note the claimed statement is essentially "every invertible integer matrix is a product of integer elementary row operations", with a minor tweak to stay completely within determinant 1 rather than $\pm 1$. –  Hurkyl Jun 17 '12 at 11:53

The intuitive content is that the claimed statement roughly paraphrases into "every invertible integer matrix is a product of integer elementary row operations", with appropriate tweaks to the fact we want to stay within determinant 1 rather than $\pm 1$.

The proof of the claimed statement follows the same idea as the proof every invertible (real) matrix is a product of elementary matrices: show that elementary operations can row reduce any invertible matrix to the identity

The powers of $\mathbf{A}$ are precisely the elementary matrices that describe adding multiplies of the second row to the top row.

The powers of $\mathbf{BAB}^{3}$ are the elementary matrices that describe adding multiples of the top row to the second row.

Using these elementary row operations, any 2x2 integer matrix can be row reduced (think "Euclidean algorithm") to one of the following forms:

$$\left( \begin{matrix} x & y \\ 0 & z \end{matrix} \right) \qquad \left( \begin{matrix} x & y \\ 0 & 0 \end{matrix} \right) \qquad \left( \begin{matrix} 0 & x \\ 0 & 0 \end{matrix} \right) \qquad \left( \begin{matrix} 0 & 0 \\ 0 & 0 \end{matrix} \right)$$

with $0 \leq y < |z|$ in the first case, and $|x| > 0$ in all. If the original matrix was in $SL(2,\mathbf{Z})$, then only the first form is possible and we must have either $x=z=1$, and thus $y=0$.

-