<s>[INST] Span of Integer Linear Combinations 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.
 [/INST] 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.
</s>