The Art Gallery Guardian

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.