# Basis for a lattice in a subspace of $\Bbb R^n$

Let $$S$$ be a linear subspace of $$\Bbb R^n$$ having dimension $$k and assume $$S$$ is described by $$n-k$$ linear equations with integer coefficients. Look at now the intersection $$\Lambda=S\cap \Bbb Z^n$$ - such an intersection is a lattice in $$S$$. Theoretically speaking, I already know the existence of a basis $$\{v_1,\dots,v_k\} \in S$$ such that $$\Lambda=\big\{\lambda_1v_1+\cdots+\lambda_kv_k\,|\, \lambda_i\in \Bbb Z \text{ for all } i\big\}$$. Of course, any $$v_i$$ has integer coefficients.

I am wondering if the basis $$\big\{v_1,\dots,v_k\big\}$$ can be completed to a basis $$\big\{v_1,\dots,v_k,v_{k+1},\dots,v_{n}\big\}$$ of $$\Bbb R^n$$ by adding other $$n-k$$ vectors (with integer coefficients) such that there is a matrix $$g\in \text{SL}(n,\Bbb Z)$$ such that $$g(e_i)=v_i$$ for any $$i=1,\dots,n$$, where $$\{e_1,\dots,e_n\}$$ denotes the standard basis.

In other words, I am wondering if $$\{v_1,\dots,v_k\}$$ can be completed to a primitive set of vectors generating the standard lattice $$\Bbb Z^n$$. By setting $$V$$ the $$k\times n$$ matrix having the vectors $$v_i$$ as columns, if I am not mistaken, this condition is equivalent to say that the gcd of the $$k^{th}$$ order minors is one. In this case, the matrix $$V$$ can be completed to a square matrix with determinant one - hence a matrix in $$\text{SL}(n,\Bbb Z)$$.

When $$n=2$$, this is always true. Indeed, let $$qx-py=0$$ a one-dimensional space in $$\Bbb R^2$$ - $$p,q$$ are taken coprime. Clearly $$(p,q)$$ satisfies the equation above. Taking any solution $$(x_o,y_o)$$ of the associated diophantine equation $$qx-py=1$$ (the solution exists because $$p,q$$ are coprime) we have two vectors $$(p,q), \, (x_o,y_o)$$ and they form a basis for the standard lattice. In other words, the basis $$(p,q)$$ is completed to a basis of $$\Bbb Z^2$$.

When $$n=3$$, the problem seems more subtle and I don't have an answer. I began with this example. I considered the plane $$S$$ given by the equation $$x+y-2z$$ in $$\Bbb R^3$$. The vectors $$(2,0,1),\, (0,2,1)$$ form a basis for $$S$$ and they belong $$\Bbb Z^3$$, clearly. However, they don't form a basis for the lattice $$\Lambda=S\cap \Bbb Z^3$$. Indeed, the vector $$(1,1,1)$$ doesn't belong to $$\Bbb Z$$-span of them. By chance, I noticed that $$\big\{(2,0,1),\,(1,1,1)\big\}$$ is a basis for the lattice $$\Lambda$$. Not only, by adding the vector $$(0,-1,0)$$, for instance, I can complete the latter basis to a basis of $$\Bbb R^3$$ and there is $$g\in\text{SL}(3,\Bbb Z)$$ such that $$g(e_1)=(2,0,1),\, g(e_2)=(1,1,1),\, g(e_3)=(0,-1,0)$$. I have made some other examples and they work similarly.

For a generic $$n\ge3$$, I don't know if there is an algorithmic method to find a basis for $$\Lambda=S\cap \Bbb Z^n$$ and if such a basis can be always complete to a basis for $$\Bbb Z^n$$, like in the $$n=2$$ case.

• If I recall correctly, a basis of sublattice can be completed to a basis of the full lattice if and only if the sublattice is of the form $\mathbb{Z}^n\cap W$, where $W$ is a linear subspace.
– efs
Jan 7, 2020 at 17:03
• There is a (classic?) book on lattices that treats all this type of questions in detail, but I can't remember which one.
– efs
Jan 7, 2020 at 17:05
• @EFinat-S, Thanks for your answer. I think you are right but I am not able to find a proof. I have checked two books: Integral Matrices by Newmann and Lectures on the Geometry of numbers by Siegel. Is the book you have mentioned one of them? I didn't find a similar result but I may miss it. Jan 7, 2020 at 19:53
• It was the book of Cassels on Geometry of numbers.
– efs
Jan 7, 2020 at 21:22
• See Cassels "An Introduction to the Geometry of Numbers", Corollary 3 in page 14. Also, you may want to look at Theorem 1.28 here: books.google.com/… (I hope the link works for you)
– efs
Jan 7, 2020 at 21:31