# Why does the set of integer vectors in the nullspace of $\mathbf{A}$ constitute a lattice?

I can almost see that this is true for the following reason:

Let $\{\mathbf{x}_i\}$ be the set of all integer vectors in the nullspace of $\mathbf{A}$. Then any finite linear combination with integer coefficients of these vectors is again an integer vector in the nullspace of $\mathbf{A}$. This is almost a lattice, except I'm using too many "basis vectors". And I don't see how I can trim the number of $\mathbf{x}_i$ to just the dimension of the nullspace of $\mathbf{A}$.

• Why do you say it is 'almost' a lattice? You just showed it is a lattice. I am confused about your comments on dimension/basis. – Fimpellizieri Jun 1 '18 at 22:15
• To me a lattice is a set of the form $\{\mathbf{Kx}:\mathbf{x}\in\mathbb{Z}^k\}$ for some matrix $\mathbf{K}$. But I don't see how to reduce the set of all integer vectors in the nullspace of $\mathbf{A}$ to a single matrix. – Sebastian Oberhoff Jun 2 '18 at 7:52
• A lattice is an additive group that is isomorphic to some $\mathbb Z^n$. – Fimpellizieri Jun 2 '18 at 8:03
• I was thinking of them like this: cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/… – Sebastian Oberhoff Jun 2 '18 at 8:14
• Besides, I have at best shown that the integer vectors in the nullspace of $\mathbf{A}$ constitute an additive group. I haven't demonstrated that it is isomorphic to $\mathbb{Z}^n$ for some $n$. – Sebastian Oberhoff Jun 2 '18 at 12:04

Following the comments, a highly general result is as follows:

Theorem. Let $n\gt 0$ be a positive integer, and let $H$ be a subgroup of $\mathbb{Z}^n$. Then there exists a basis $a_1,\ldots,a_n$ of $\mathbb{Z}^n$, an integer $d$ with $0\leqslant d\leqslant n$, and positive integers $m_1,\ldots,m_d$ such that $m_1|m_2$, $m_2|m_3,\ldots,m_{d-1}|m_d$ and such that $m_1a_1,\ldots,m_da_d$ is a basis for $H$. In particular, $H$ is free and finitely generated.

In particular, $H$ is isomorphic to $\mathbb Z^d$.
You can see a proof this in this previous answer, with an explanation of an unclear part in this other answer.

While the idea that $H\sim \mathbb Z^d$ for some $d$ sounds fairly intuitive, that one can produce a basis with the divisibility property is not so obvious. You might have heard of the Smith normal form for matrices, which provides an algorithm for finding exemplars of the theorem given generators for $H$.

• I've been mulling on this some more. Doesn't the following also work? Consider the set of all lattices generated by integer vectors in the nullspace of $\mathbf{A}$. These lattices can be partially ordered using the subset relation. This partial order has infima (intersection) and suprema (direct sum) and therefore constitutes a lattice in the order sense. If you may, we have a lattice of lattices. Now this lattice has an obvious upper bound, namely $\mathbb{Z}^n$. Hence it has a maximal element which is the desired lattice. – Sebastian Oberhoff Jun 4 '18 at 19:50
• Is such a maximal element, in principle, unique? Does the choice, in principle, not matter? – Fimpellizieri Jun 4 '18 at 20:51
• If there were two maximal elements then their direct sum would again be a lattice in the nullspace containing both maximal elements, contradicting the assumption that they were maximal. – Sebastian Oberhoff Jun 4 '18 at 20:57
• Sounds good -- that's a maximum! – Fimpellizieri Jun 4 '18 at 21:01
• On second thought, I don't know if the assertion that the direct sum of two lattices again constitutes a lattice is as straightforward as it sounds or whether this requires an argument that is again as complex as the one you linked to. – Sebastian Oberhoff Jun 4 '18 at 21:48