Use Euclid's gcd algorithm to prove a statement about matrices with determinant $\pm1$

Question

Define:

$$GL_2:=\{ A \in M_2(\Bbb Z)\mid\det(A) \in \{1,-1\}\},$$

$$a:=\begin{bmatrix}0 & 1\\1 & 0\end{bmatrix},\ b:=\begin{bmatrix}1 & 1\\0 & 1\end{bmatrix}.$$

Use Euclid's gcd algorithm to show that: $\forall g \in GL_2$ $\exists r_1, \dots, r_k, s_1, \dots, s_k \in \Bbb Z$ s.t. $g=a^{r_1}b^{r_1} \cdots a^{r_k}b^{r_k}$, where $a^{-1}, b^{-1}$ are the inverse matrices.

Any clues?

Answer 1

There are two main steps:

• Write every elementary matrix in terms of $a$ and $b$
• Figure out how to reduce a matrix to the diagonal using elementary operations

Unlike the case of a field, when over the integers, both row and column operations are needed to reduce a matrix to a diagonal one. The basic algorithm is

• Let $g$ be the (nonnegative) $\gcd$ of all the entries of the matrix
• Do elementary row and column operations to put $g$ in the top-left corner of the matrix
• Eliminate the remaining entries of the first row and column
• You're now done with the first row and column -- repeat the above on the rest of the matrix.