The Art Gallery Guardian

Basis of the module Zn\Z^n


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

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

Formally, what can we say about vv and uu if for every wZ2w\in \Z^2, there exist n,mZn,m\in \Z, such that nv+mu=wnv + mu = w.

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

Theorem1

v1,,vnv_1,\ldots,v_n is a basis for the module Zn\Z^n iff the matrix MM formed by the vectors is a unimodular matrix.

Proof

\Rightarrow If det(M)=0\det(M)=0, then v1,,vnv_1,\ldots,v_n are not linearly independent. If det(M)2|\det(M)|\geq 2, then the parallelepiped formed by v1,,vnv_1,\ldots,v_n has volume 2\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 v1,,vnv_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 mm such parallelepiped, but contain at least 2m2m lattice points.

This shows if MM is not unimodular, then v1,,vnv_1,\ldots,v_n can't be a basis.

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

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

Posted by Chao Xu on .
Tags: math.