Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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...

share|improve this question
    
An idea: Write your vectors as rows in a matrix and calculate the reduced row echelon form. Now take only rows that contain no irrational numbers. Make all entries of the remaining rows integer valued. –  Gregor Bruns Aug 23 '12 at 14:22
2  
If $\{b_1, b_2, \ldots, b_n \}$ is a basis for $V \subset \mathbb{R}^n$, then $V=\mathbb{R}^n$, and so $L=\mathbb{Z}^n$. –  Chris Eagle Aug 23 '12 at 14:49
    
I don't understand your question, maybe I miss something. Is $V$ supposed to be a real vector space? If so, how can it be $V\subset \mathbb Q^n$? If $b_1,\dots,b_k\in \mathbb Q^n$, the generated real vector space is not contained in $\mathbb Q^n$. –  Hans Aug 23 '12 at 15:25
    
$V$ is assumed to be a rational vector space. Hope that is clear from the question by now. –  newguy Aug 23 '12 at 15:36
    
OK, it is clear now. I was confused, because in light of Sean Eberhard's answer (as far as I understand), it seems reasonable to keep $V$ real vector space, and just assuming the $b_i$'s in $\mathbb Q^n$ instead of $\mathbb R^n$. –  Hans Aug 23 '12 at 15:53

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
Dear Sean: It's a little bit as if you told me that there are algorithms to decide if a positive integer is prime, and I told you: Let $n$ be equal to $2$ is the Riemann hypothesis is true, and to $4$ if it is false. Is $n$ prime? –  Pierre-Yves Gaillard Aug 23 '12 at 16:28
    
@Pierre-YvesGaillard Hmmm. I guess when I think of an algorithm being given real numbers as data, I think of real approximations, probably floating-point numbers. The point of my answer is that the the solution to this problem is too delicate for such an approach. In other words, you would need (at least) an "algorithm" for determining whether $x\in\mathbf{R}$ is rational. So it comes down to: What does it mean to "give somebody" a real number. –  Sean Eberhard Aug 23 '12 at 16:45
    
Dear Sean: The question seems to have been edited. The current version doesn't mention real numbers (except in a parenthesis referring - I guess - to a previous version). Anyway, the point is that it's a classical problem, and it might be worth looking first at the classical solution... –  Pierre-Yves Gaillard Aug 23 '12 at 16:55
    
Thanks for the elaborated answer, however I am little confused about something. If $a_1 e_1,\ldots, a_m e_m \in V$ then by virtue of $V$ being a $\mathbb{Q}$-vectorspace we have $e_1,\ldots,e_m\in V$. But since $e_1,\ldots, e_n \in \mathbb{Z}^n$ by assumption, this should imply that $e_1,\ldots,e_m$ is a basis for $V\cap \mathbb{Z}^n$. In other words I don't see what we need the $a_1,\ldots,a_m$ for. Perhaps I am just being tired, I suspect your answer is what i am looking for despite this little confusion. –  newguy Aug 24 '12 at 8:50
    
@newguy You are right. I think it's fixed now. –  Sean Eberhard Aug 24 '12 at 9:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.