1
$\begingroup$

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$ ?)

$\endgroup$
2
  • 1
    $\begingroup$ You don't generally get a lattice of dim K. (A line of irrational slope in R^2 won't hit any nontrivial integer points.) $\endgroup$ Jan 3, 2015 at 7:50
  • $\begingroup$ You right for the case that vectors a_1,...,a_K are in R^n (last line of my question!). but for the case that a_1,...,a_K are in Z^L, at least these integer points and their integer combinations are in the span V and may form a lattice. $\endgroup$
    – mohsenh01
    Jan 3, 2015 at 9:25

2 Answers 2

2
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ Isn't it always a subset of the standard basis? Just checking I'm not missing something. $\endgroup$ Jan 11, 2021 at 15:54
  • $\begingroup$ You are right. I updated my answer. $\endgroup$ Jan 13, 2021 at 10:36
1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Do you mean a lattice of rank $K$? As an example, consider the case $L=3$, $K=2$: $\mathbf{a}_1=[2,0,0], \mathbf{a}_2=[0,2,0]$, then a basis for the lattice $\Lambda$ is: $\mathbf{e}_1=[1,0,0], \mathbf{e}_2=[0,1,0]$ and the lattice rank is 2. $\endgroup$
    – mohsenh01
    Jan 5, 2015 at 5:01
  • $\begingroup$ And also the reference you introduced is too complex for me to understand! Any simpler solution? thanks. $\endgroup$
    – mohsenh01
    Jan 5, 2015 at 5:07
  • $\begingroup$ Yes, it's $K$ of course. $\endgroup$ Jan 5, 2015 at 8:30
  • $\begingroup$ I don't see why it's complicated. In any case, if time doesn't matter, it suffices to try linear combinations of $\mathbf{a}_i$ with denominators $n$ such that $n^2$ divides the determinant of the Gram matrix. There are finitely many such vectors (modulo the original lattice). $\endgroup$ Jan 5, 2015 at 11:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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