2
$\begingroup$

Let $S$ be a linear subspace of $\Bbb R^n$ having dimension $k<n$ 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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – EFinat-S Jan 7 at 17:03
  • $\begingroup$ There is a (classic?) book on lattices that treats all this type of questions in detail, but I can't remember which one. $\endgroup$ – EFinat-S Jan 7 at 17:05
  • $\begingroup$ @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. $\endgroup$ – InsideOut Jan 7 at 19:53
  • $\begingroup$ It was the book of Cassels on Geometry of numbers. $\endgroup$ – EFinat-S Jan 7 at 21:22
  • 2
    $\begingroup$ 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) $\endgroup$ – EFinat-S Jan 7 at 21:31
3
$\begingroup$

The answer to your question, with a full proof, appears in "An Introduction to the Geometry of Numbers" by J.W.S. Cassels, Corollary 3 in page 14. It is also stated as Theorem 1.28 here but without a proof.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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