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 post

All maths posts