4
$\begingroup$

This might be a stupid/very simple question, but since I can't quite seem to come up with a nice trick I will ask it anyway.

Assume that we have a vectorspace $V \subseteq \mathbb{Q}^n$ given in the form of a basis $b_1,\ldots, b_k \in \mathbb{Q}^n$ [EDIT: $V$ was originally assumed to be real, but since the question becomes unreasonably hard in this case, I am assuming $V \subseteq \mathbb{Q}^n$] . With this information I would like to find a basis for the lattice $L= V\cap \mathbb{Z}^n$ Does there exist an efficient algorithm for finding such a basis?

EDIT: In light of Sean Eberhard's answer below an algorithm which would solve the problem in the generality originally stated, i.e. for $V$ any real subspace, is clearly far too optimistic. Hence allow me to modify the question by adding the assumption that $b_1,\ldots, b_k \in \mathbb{Q}^n$, i.e. that in fact $V\subseteq \mathbb{Q}^n$.

EDIT 2: $V$ should be a proper subspace, since the answer is trivial otherwise, as pointed out below (my original labelling of the basis elements meant that Chris Eagles remark below answered my question as stated). Hope the problem has now been given in a way making it feasible without being trivial...

  • 0
    @BipolarMinds - We can assume that the $b_i$ are in $\mathbb Z^n$. Thus it is simpler to omit the introduction of $V$ and $\mathbb Q^n$, and to suppose just that we are given a $\mathbb Z$-submodule of $\mathbb Z^n$ of rank $k$. Then it is natural to replace $\mathbb Z$ with a general PID.2016-09-19

1 Answers 1

4

If you only assume $b_1,\ldots,b_m\in\mathbf{R}^n$, then you will have trouble, as the following example shows. Consider the $1$-dimensional subspace $V$ of $\mathbf{R}^2$ spanned by $(1,\gamma)$, where $\gamma$ is, say, the Euler-Mascheroni constant. If you could find a basis for $V\cap\mathbf{Z}^2$ you would become very famous: indeed, proving $V\cap\mathbf{Z}^2=0$ is equivalent to proving that $\gamma$ is irrational, which is unknown. The point is that finding $V\cap\mathbf{Z}^n$ would require infinite precision on $b_1,\ldots,b_m$, which is usually unavailable.

You will therefore have to assume $b_1,\ldots,b_m$ have more structure, say $b_1,\ldots,b_m\in\mathbf{Q}^n$. In this case, the problem is classical. Rescaling, without loss of generality $b_1,\ldots,b_m\in\mathbf{Z}^n$. Now put the matrix $[b_1,\ldots,b_m]$ into Smith normal form. This is the same as finding a new generating set $e_1,\ldots,e_n$ for $\mathbf{Z}^n$ and integers $a_1|a_2|\cdots|a_m$ such that the $\mathbf{Z}$-modules generated by $b_1,\ldots,b_m$ and by $a_1 e_1,\ldots,a_m e_m$ coincide. Finally, $e_1,\ldots,e_m$ is a generating set for $V\cap\mathbf{Z}^n$. (Note that the $\mathbf{Z}$-module generated by $b_1,\ldots,b_m$ is not necessarily all of $V\cap\mathbf{Z}^n$.) See the link above for more details on this algorithm.

  • 0
    Very nice and very clear. Thanks for the help.2012-08-24