17
$\begingroup$

I hope that the following problem isn't actually elementary (at least, for the sake of the fact that I'm posting it here), and I apologize if it is. I did try hard to solve it first.

Let $V$ be a $\mathbb{Q}$-vector subspace of $\mathbb{Q}^n$, and let $G = V \cap \mathbb{Z}^n$. Does there exist a linearly independent generating set for $G$ (i.e. a subset of $G$ such that every element of $G$ can be expressed uniquely as as $\mathbb{Z}$-linear combination of elements of this subset)? Is there an algorithm to find it (given a basis for $V$)?

Improve this question
$\endgroup$
18
  • 6
    $\begingroup$ Fernando: it is too elementary if you were taught these things. So is the fact that every left invertible element of the group von Neumann algebra of a discrete group is invertible (because every projection in a vN algebra with faithful finite trace is of finite type, I'm sure Aaron can explain this better than me) $\endgroup$
    – Yemon Choi
    Commented Feb 16, 2013 at 17:40
  • 5
    $\begingroup$ Fernando: well, your university 1st year went further than mine, I guess. $\endgroup$
    – Yemon Choi
    Commented Feb 16, 2013 at 17:57
  • 10
    $\begingroup$ I hope my question didn't offend you Fernando. I was tentative about asking it, because I wasn't sure if it was research-level. Perhaps, sometimes you need to see the answer before you realize how easy a question is. Thank you for pointing out Smith Normal Form, since I didn't learn about it in my undergrad or graduate career $\endgroup$
    – Aaron Tikuisis
    Commented Feb 16, 2013 at 18:09
  • 7
    $\begingroup$ It seems this thread has a meta page now. tea.mathoverflow.net/discussion/1537/… $\endgroup$
    – Ryan Budney
    Commented Feb 16, 2013 at 23:08
  • 4
    $\begingroup$ @Aaron Tikuisis no offence, I simply think it doesn't fit this forum. $\endgroup$
    – Fernando Muro
    Commented Feb 17, 2013 at 0:37

1 Answer 1

Reset to default
14
$\begingroup$

EDIT: I typed this up before everyone piled on to say that this is too elementary. Moving to CW rather than deleting, as I distinctly remember not seeing this during my education on groups and rings (but then maybe I missed class that day). And don't even go down the line of "grad school courses"...

Feel free to downvote if you feel like it, of course.

Interesting question! The following is not a full answer, but seemed worth a bit more than a comment.

If I understand correctly, the first part asks if G is free abelian, in which case the answer is apparently yes, see this MO question from someone reputable. (I confess this is not something I knew, although I did have my suspicions.)

My guess is that some modification of Gauss-Jordan elimination should provide an algorithm for extracting a "Z-basis" from a Z-generating set, but it's not clear to me right now how one would get a Z-generating set from a given Q-basis of your original V.

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ Your "guess" is what is known as the Smith normal form. $\endgroup$
    – Felipe Voloch
    Commented Feb 16, 2013 at 21:57
  • 2
    $\begingroup$ @Felipe, of course you know, but for the record: the Smith normal form algorithm combines Gauss-Jordan ideas with Euclides's algorithm for the gcd. I like to see it as a generalization of the later, rather than the former. $\endgroup$
    – Fernando Muro
    Commented Feb 17, 2013 at 1:04
  • $\begingroup$ Yemon, the question you have linked to specifically asks about not necessarily finitely generated free abelian groups. The OP does not need to read the Wikipedia proof for his question, this is much more elementary. $\endgroup$
    – Alex B.
    Commented Feb 18, 2013 at 11:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .