Span of Integer Linear Combinations

Question

This question relates to linear combinations of vectors; however, vectors can only be scaled by integer values. This means that if we have two vectors $\binom{a}{b}$ and $\binom{c}{d}$, we can only have $$x\binom{a}{b} + y\binom{c}{d},$$ where $a, b, c, d, x,y\in \mathbb{Z}.$

I was wondering how to determine when linear combinations of two vectors will span $\mathbb{Z^2}$. I know that if the second vector is a multiple of the first, this will not be true, but I'm not sure about the other cases.

Answer 1

Claim: $\begin{pmatrix}a\\b\end{pmatrix}$ and $\begin{pmatrix}c\\d\end{pmatrix}$ span the whole $\mathbb Z^2=M_{12}(\mathbb Z)$ if and only if $\det\left[\begin{matrix}a&c\\b&d\end{matrix}\right]=ad-bc=\pm 1$.

Proof sketch: basically, the span is the whole of $\mathbb Z^2$ if and only if $\begin{pmatrix}1\\0\end{pmatrix}$ and $\begin{pmatrix}0\\1\end{pmatrix}$ can be represented as linear combinations of $\begin{pmatrix}a\\b\end{pmatrix}$ and $\begin{pmatrix}c\\d\end{pmatrix}$. However:

$$\begin{pmatrix}1\\0\end{pmatrix}=x\begin{pmatrix}a\\b\end{pmatrix}+y\begin{pmatrix}c\\d\end{pmatrix}$$ $$\begin{pmatrix}0\\1\end{pmatrix}=z\begin{pmatrix}a\\b\end{pmatrix}+t\begin{pmatrix}c\\d\end{pmatrix}$$

is equivalent to:

$$\left[\begin{matrix}a&c\\b&d\end{matrix}\right]\cdot\left[\begin{matrix}x&z\\y&t\end{matrix}\right]=\left[\begin{matrix}1&0\\0&1\end{matrix}\right]=I$$

so existence of $\left[\begin{matrix}x&z\\y&t\end{matrix}\right]$ implies that $\det\left[\begin{matrix}a&c\\b&d\end{matrix}\right]=\pm 1$, and, conversely, if $\det\left[\begin{matrix}a&c\\b&d\end{matrix}\right]=\pm 1$, then the inverse $\left[\begin{matrix}a&c\\b&d\end{matrix}\right]^{-1}$ is easily shown to be an integral matrix.

Note: Notice that, using the same logic, one can conclude that $\begin{pmatrix}a\\b\end{pmatrix}$ and $\begin{pmatrix}c\\d\end{pmatrix}$ are linearly independent if and only if $\det\left[\begin{matrix}a&c\\b&d\end{matrix}\right]=ad-bc\ne 0$. Thus, in the $\mathbb Z$-module $\mathbb Z^2$ there are pairs of "vectors" which are linearly independent but don't span the whole module.

Answer 2

Possible solution:

Note that $$x\binom{a}{b} + y\binom{c}{d} =\binom{ax+cy}{bx+dy}.$$

By Bezout's lemma, as long as gcd(a, c) = 1 and gcd(b, d) = 1, the resulting vector can take on value in $\mathbb{Z^2}.$

Is this sufficient?