# Basis of the module $$\Z^n$$

A student who is taking linear algebra asked me the following problem.

If we consider the field $$\R$$ restricted to $$\Z$$, and create a "vector space" on $$\Z$$. How do we know if $$v,u\in \Z^2$$ "spans" $$\Z^2$$?

Formally, what can we say about $$v$$ and $$u$$ if for every $$w\in \Z^2$$, there exist $$n,m\in \Z$$, such that $$nv + mu = w$$.

We can generalize it and put it in terms of modules, as $$\Z$$ is only a ring but not a field.

Theorem1

$$v_1,\ldots,v_n$$ is a basis for the module $$\Z^n$$ iff the matrix $$M$$ formed by the vectors is a unimodular matrix.

Proof

$$\Rightarrow$$ If $$\det(M)=0$$, then $$v_1,\ldots,v_n$$ are not linearly independent. If $$|\det(M)|\geq 2$$, then the parallelepiped formed by $$v_1,\ldots,v_n$$ has volume $$\geq 2$$. If there is any integer point not on the corners of the parallelepiped, then that point can't be written as linear combination of $$v_1,\ldots,v_n$$. Notice that it must contain some lattice points not on the corners of the parallelepiped. One can see why by consider a large box that contain volume of $$m$$ such parallelepiped, but contain at least $$2m$$ lattice points.

This shows if $$M$$ is not unimodular, then $$v_1,\ldots,v_n$$ can't be a basis.

Alternative proof: $$M$$ is not unimodular then $$M^{-1}$$ contain a non-integer entry. This shows there exist a $$b$$, such that the solution $$x$$ to $$Mx=b$$ contain a non-integer entry. (proposed by Thao Do)

$$\Leftarrow$$ $$|\det(M)|=1$$ implies it has a inverse over $$\Z$$, thus $$Mx = b$$ for any $$b\in \Z^n$$ always has a solution.

Posted by Chao Xu on 2012-08-30.
Tags: math.