basis of the lattice generated by the integer points inside a subspace of R^L

Question

Consider $K$ linearly independent vectors $\mathbf{a}_1, \mathbf{a}_2, ..., \mathbf{a}_K \in \mathbb{Z}^L$, where $1 \leq K<L $. Hence, the span of $\lbrace\mathbf{a}_1, \mathbf{a}_2, ..., \mathbf{a}_K\rbrace$ on real numbers is a subspace of $\mathbb{R}^L $ with dim $K$. Denote this subspace as $V=Span\lbrace\mathbf{a}_1, \mathbf{a}_2, ..., \mathbf{a}_K\rbrace$.

I think the integer points inside this span, i.e. $V \bigcap \mathbb{Z}^L$ , form a lattice of rank $K$ in $\mathbb{Z}^L$ (is it true?). What is the basis (generator matrix) of this lattice? How it can be computed explicitly from $\mathbf{a}_1, \mathbf{a}_2, ..., \mathbf{a}_K $?

In brief, given the linearly independent vectors $\mathbf{a}_1, \mathbf{a}_2, ..., \mathbf{a}_K \in \mathbb{Z}^L$, I want the basis for the lattice: $$ \Lambda =\lbrace \mathbf{b}\in {\mathbb{Z}^L} \vert \mathbf{b}=\sum\limits_{k = 1}^K {{\alpha _k}{{\mathbf{a}}_k}} ,\,{\alpha _1}, \cdots ,{\alpha _K} \in \mathbb{R} \rbrace$$ (what if $\mathbf{a}_1, \mathbf{a}_2, ..., \mathbf{a}_K \in \mathbb{R}^L$ ?)

Answer 1

Although the brute force solution of Alex is certainly possible, it is not very efficient. It would be easier in practice to use Hermite's normal form:

First, find a linear map $A \in \mathbb{Z}^{(L-K) \times L}$, such that $V = \ker(A)$ is the null space of $A$ (which can be found by computing the null space of the matrix with $V$ as its rowspace).

Next, compute the Hermite normal form of $A$ to obtain a decomposition $H = AU$, where $H \in \mathbb{Z}^{(L-K) \times L}$ is in column-style Hermite normal form, and $U \in \mathbb{Z}^{L\times L}$ is a unimodular matrix (that is, $U : \mathbb{Z}^L \to \mathbb{Z}^L$ is an isomorphism).

For $\Lambda_H = \ker(H) \cap \mathbb{Z}^n$, we have \begin{align*} \Lambda &= \ker(A) \cap \mathbb{Z}^n \\ &= \{\mathbf{x} \in \mathbb{Z}^n \mid A\mathbf{x} = \mathbf{0} \} \\ &= \{\mathbf{x} \in \mathbb{Z}^n \mid HU^{-1}\mathbf{x} = \mathbf{0} \} \\ &= \{U\mathbf{y} \mid \mathbf{y} \in \mathbb{Z}^n, H\mathbf{y} = \mathbf{0} \} \\ &= U\Lambda_H \end{align*} As $H$ is in column-style Hermite normal form, it is straightforward to find a basis for the lattice $\Lambda_H$ (it is a subset of the standard basis). Application of the isomorphism $U$ yields a basis for the lattice $\Lambda$.

Answer 2

Disregarding the last line of your question, yes, you do get a lattice of rank $K$, and this lattice can be computed explicitly. A quick and dirty algorithm would use

MR0525944 (80j:10031) Reviewed Nikulin, V. V. Integer symmetric bilinear forms and some of their geometric applications. (Russian) Izv. Akad. Nauk SSSR Ser. Mat. 43 (1979), no. 1, 111–177, 238.

The thing is that the lattice in question is a finite index extension of the original lattice, say, $S$. Restricting to $S$ the Euclidean inner product, we make it a true nondegenerate lattice, and then it has but finitely many finite index extensions: they are enumerated by the isotropic subgroups of the finite group $\operatorname{discr}S$. Each has an explicit basis (made by rational vectors in the basis of $S$), and one can try them all one by one to see if these vectors are actually integral.