A question from stack exchange, given a vector \(\mathbf{v} \in \mathbb{Z}^2\), what is its orbit under the action of the general linear group \(\text{GL}(2,\mathbb{Z})\) of order 2 over the integers? Through answering this question, we relate the Euclidean algoirthm from number theory to the study of the general linear groups.

Claim:

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

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

Proof:

We would emulate the Euclidean algorithm.

WLOG suppose \(m > n\), then by division algorithm there exists non-negative integers \(q, r\) with \(n > r\) such that \(m = qn + r\). We can express this in matrix form

\[\begin{bmatrix} 0 & 1 \\ 1 & -q \end{bmatrix} \begin{bmatrix} m \\ n\end{bmatrix} = \begin{bmatrix} n \\ r\end{bmatrix}.\]

Notice that the square matrix above has determinant \(-1\) hence is invertible. Proceeding with the Euclidean algorithm we obtain some matrix \(T \in \text{GL}(2,\mathbb{Z})\) 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}\left(\begin{bmatrix} m \\ n\end{bmatrix}\right).\]

For the other direction, for all integers \(a, b\) we have \(\text{gcd}(m,n) \vert am + bn\), so

\[\text{Orb}\left(\begin{bmatrix} m \\ n\end{bmatrix}\right) \subset \text{gcd}(m,n) \mathbb{Z}^2.\] \[\qquad \qquad \qquad \qquad \qquad \qquad \qquad \square\]

Example: Consider the pair of integers \((7,5)\). Euclidean algorithm tells us that \(\text{gcd}(7,5) = 1\) as follows:

\[\begin{align*} 7 &= 1 \times 5 + 2, \\ 5 &= 2 \times 2 + 1, \\ 2 &= 2 \times 1 + 0. \end{align*}\]

In matrix form, we have

\[\begin{align*} &\begin{bmatrix} 0 & 1 \\ 1 & -2 \end{bmatrix}\begin{bmatrix} 0 & 1 \\ 1 & -2 \end{bmatrix}\begin{bmatrix} 0 & 1 \\ 1 & -1 \end{bmatrix} \begin{bmatrix} 7 \\ 5 \end{bmatrix} \\ &= \begin{bmatrix} -2 & 3 \\ 5 & -7 \end{bmatrix} \begin{bmatrix} 7 \\ 5 \end{bmatrix} \\ &= \begin{bmatrix} 1 \\ 0 \end{bmatrix}. \end{align*}\] \[\]

Remarks

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 \(\text{gcd}(0,0)\) as \(0\).

This also leads on to theory about \(\text{SL}(2,\mathbb{Z})\) which one could find here.