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.