I've been studying an introductory book on algebra. I've hit upon the following exercise:
Let $\mathbb{Z}^m=\mathbb{Z}\oplus\mathbb{Z}\,\oplus\,...\oplus\,\mathbb{Z}$. Show that $\mathbb{Z}^m$ is free (has a basis) and describe all bases.
Obviously, $(1,0,...,0),(0,1,...,0),...,(0,0,...,1)$ form a basis. However, the second part is giving me difficulties. I have figured out some things:
So suppose we have a basis $B$. First I showed that $|B|=m$. Indeed, the basis elements $b_i$ can be interpreted as lying in $\mathbb{Q}^m$ and so if $|B|>n$, some finite rational linear combination of the $b_i$ is $0$. But then multiplying this linear combination by the product of the denominators of the coefficients gives a finite integer linear combination of the $b_i$ that is $0$ so $B$ is not a basis. Similarly, if $|B|<n$ then some $v\in\mathbb{Q}^m$ is not in the span of the $b_i$. But any integer multiple of $v$ is not in their span either, giving us an element of $\mathbb{Z}^m$ not expressible in terms of the $b_i$.
If for any $b_i$ the components $(b_i)_j$ are not coprime, that is, if $d_i=\mathrm{gcd}_j((b_i)_j)>1$, the vector $\hat{b}_i=d_i^{-1}\cdot b_i$ is in $\mathbb{Z}^m$. Therefore, if $\hat{b}_i$ were expressible in terms of the $b_i$ in $\mathbb{Z}^m$ only, there would be two distinct ways of representing $\hat{b}_i$ in $\mathbb{Q}^m$, so the $b_i$ would not be a basis.
The elements $e_i=(0,...,1_i,...,0)$ must be expressible in terms of the basis. This means that there are some $k_j\in\mathbb{Z}$ such that $\sum_{j=1}^mk_j(b_j)_i=1$. This is well-known to imply $\mathrm{gcd}_j((b_j)_i)=1$.
Here's my takeaway: if we arrange the $b_i$ into the columns of a matrix $M$ then the $\mathrm{gcd}$ of every row and column must be $1$. That's a necessary condition. On the other hand, if $\det(M)=\pm 1$, by Cramer's rule $M^{-1}$ has only integer entries, so the $b_i$ form a basis. That's a sufficient condition. For $m=2$, it also happens to be necessary (otherwise the $M_{ij}$ would not be coprime by Cramer's rule). And this is as far as I've gotten. Indeed, even for $m=2$ the solutions seem quite complex: $(2,3),(3,5)$ is one; anything of the form $(a,1),(ab\pm1,b);a,b\in\mathbb{Z}$ works too. I just don't see a way to classify all the different possibilities for larger $m$.
A set $\{\alpha_1,...,\alpha_m\}\subseteq\mathbb{Z^m}$ is a basis if and only if the determinant of the matrix $B$ whose columns are $\alpha_1,...,\alpha_m$ is either $1$ or $-1$. In the proof I assume you know that a matrix in $M_m(\mathbb{Z})$ has an inverse in $M_m(\mathbb{Z})$ if and only if its determinant is $1$ or $-1$.
Alright, so now suppose the columns of $B$ form a basis of $\mathbb{Z^m}$. If we look at $B$ at a matrix in $M_m(\mathbb{Q})$ then its columns form a basis of the vector space $\mathbb{Q^m}$ over $\mathbb{Q}$. This means the matrix $B$ is invertible in $M_m(\mathbb{Q})$ and by definition $B^{-1}$ is a change of base matrix-from the basis $\{\alpha_1,...,\alpha_m\}$ to the standard basis. But then the elements of the $k$th column of $B^{-1}$ are the coefficients of $e_k$ as a linear combination in the basis $\{\alpha_1,...,\alpha_m\}$ over $\mathbb{Q}$. But since $e_k\in\mathbb{Z^m}$ and $\{\alpha_1,...,\alpha_m\}$ form a basis of $\mathbb{Z^m}$ we get that these coefficients must be integers. (because $e_k$ can be written as a "linear combination" in $\{\alpha_1,...\alpha_m\}$ over $\mathbb{Z}$, and this must be its unique representation as a linear combination over $\mathbb{Q}$). Hence $B^{-1}\in M_m(\mathbb{Z})$, so $\det(B)\in\{1,-1\}$.
Now the other direction. Suppose $\det(B)\in\{1,-1\}$. Then $B^{-1}\in M_m(\mathbb{Z})$. Since the determinant is not zero the columns $\{\alpha_1,...,\alpha_m\}$ form a basis of $\mathbb{Q^m}$ over $\mathbb{Q}$, and again $B^{-1}$ is a change of base matrix-from the basis $\{\alpha_1,...,\alpha_m\}$ to the standard basis, and the $k$th column contains the coefficients of $e_k$ in its linear combination in $\{\alpha_1,...,\alpha_m\}$. But since the entries of $B^{-1}$ are integers we get that all these coefficients are in $\mathbb{Z}$. Since $\{e_1,...,e_m\}$ form a basis of $\mathbb{Z^m}$ we get that each element in $\mathbb{Z^m}$ can be written as a "linear combination" over $\mathbb{Z}$ in $\{\alpha_1,...,\alpha_m\}$. So to show $\{\alpha_1,...,\alpha_m\}$ is a basis of $\mathbb{Z^m}$ we just have to show that this combination is unique for any element of $\mathbb{Z^m}$. But this is obvious, as the linear combination of any element is unique even over $\mathbb{Q}$.