Euclidean algorithm and GL(2, Z)
Given a vector \(\mathbf{v} \in \mathbb{Z}^2\), what is its orbit under the action of the general linear group \(GL(2,\mathbb{Z})\) of order 2 over the integers?
Claim:
For integers \(m, n >0\),
\[\text{Orb}(\begin{bmatrix} m \\ n\end{bmatrix}) = \text{gcd}(m,n) \mathbb{Z}^2\]Proof:
We would emulate the Euclidean algorithm.
WLOG if \(m > n\), then by division algorithm there exists non-negative integers \(q, r\) with \(r < n\) such that \(m = qn + r\). I.e. \(\begin{bmatrix} 1 & -q \\ 0 & 1 \end{bmatrix} \begin{bmatrix} m \\ n\end{bmatrix} = \begin{bmatrix} r \\ n\end{bmatrix}\) and \(\begin{bmatrix} 0 & 1 \\ 1 & -q \end{bmatrix} \begin{bmatrix} m \\ n\end{bmatrix} = \begin{bmatrix} n \\ r\end{bmatrix}\)
Notice that both of square matrices above have determinant \(\pm 1\). Proceeding with the Euclidean algorithm we obtain some element \(T \in GL(2,\mathbb{Z})\) by composition such that \(T\begin{bmatrix} m \\ n\end{bmatrix} = \begin{bmatrix} gcd(m,n) \\ 0 \end{bmatrix}\). Hence \(\text{gcd}(m,n) \mathbb{Z}^2 \subset \text{Orb}(\begin{bmatrix} m \\ n\end{bmatrix})\).
For the other direction, for all integers \(a, b\) we have \(gcd(m,n) \vert am + bn\), so \(\text{Orb}(\begin{bmatrix} m \\ n\end{bmatrix}) \subset \text{gcd}(m,n) \mathbb{Z}^2\) \(\square\)
All the matrices used in the algorithm are shear matrices, and I wonder if there’s anything interesting going on geometrically.
The claim also supports defining \(gcd(0,0)\) as \(0\).
Next maths post Previous maths postAll maths posts