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?


For integers \(m, n >0\),

\[\text{Orb}(\begin{bmatrix} m \\ n\end{bmatrix}) = \text{gcd}(m,n) \mathbb{Z}^2\]


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 post

All maths posts