Lattice generated by vectors orthogonal to an integer vector
Given a non-zero vector $\boldsymbol{v}$ composed of integers, imagine the set of all non-zero integer vectors $\boldsymbol{u}$, such that $\boldsymbol{u} \cdot \boldsymbol{v} = 0$, i.e., the integer vectors orthogonal the original vector. The set $S = \{\boldsymbol{u} : \boldsymbol{u} \cdot \boldsymbol{v} = 0\}$ seems to form a $dim(\boldsymbol{v})-1$ dimensional lattice. Specifically, it's clear that for any two elements of $S$, their linear combination is also in $S$. However, because S is a subset of the lattice of all integer vectors, it's also a lattice. It there a name for this lattice? Additionally, how can it's basis vectors be computed?
$\endgroup$ 12 Answers
$\begingroup$I don't know if this lattice has a name, however it is easy to compute a basis given $\mathbf{v}$ by recurrence:
Suppose the gcd of all coordinates of $\mathbf{v}$ is 1 or else divide by it.
Let $\mathbf{v}=(v_1,...,v_n)$.
If $n=2$, then your basis is just $(v_2,-v_1)$
If $n > 2$:
Set the first vector of your basis to be $\mathbf{b}_1=(-v_n*a_1,-v_n*a_2,...,-v_n*a_{n-1},gcd(v_1,...v_{n-1}))$, where the $a_i$ come from Bézout's Identity and can be easily calculated using the extended Euclidean algorithm.
Then complete your basis using the same algorithm with $\mathbf{v}=(v_1,...v_{n-1})$.
This yields a basis of the lattice orthogonal to $\mathbf{v}$ and not a sublattice.
Indeed, all integer vector $\mathbf{u}$ orthogonal to $\mathbf{v}$ have last coordinate which is a multiple of $gcd(v_1,...,v_{n-1})$.
$\sum_{i=1..n} u_i v_i = 0$ implies $u_n v_n = -\sum_{i=1..n-1}u_i v_i$so $gcd(v_1,...v_{n-1})$ divides $u_n v_n$ and is coprime with $v_n$.
Example
Suppose we want the lattice orthogonal to $v = (125, -75, 45, -27)$.
We first look at the orthogonal of $(125,-75)$, which is the same as the lattice orthogonal to $(5,-3)$ if we simplify by $gcd(125,-75)=25$.
So our first vector is going to be $(-3,-5,0,0)$.
Now we look at the orthogonal of $(125,-75,45)$, which is the same as the orthogonal of $(25,-15,9)$, if we simplify by $gcd(125,-75,45)=5$.
Bézout's Identity gives us $2*25+3*(-15)=5$, so our new vector is $(-9*2,-9*3,5,0)=(-18,-27,5,0)$.
Finally, we arrive to our last step, Bézout's Identity gives us $1*125+1*(-75)+(-1)*45=5$, so our last vector is $(27*1,27*1,27*(-1),5)=(27,27,-27,5)$.
So our basis is formed by the three vectors :$\big((-3,-5,0,0),(-18,-27,5,0),(27,27,-27,5)\big)$
I know that is an old question and already have a beautiful answer given by Florian Bourse, but I am adding the following just for future references.
That lattice has a name: it is called orthogonal lattice. In general, we define it regarding a set of vectors $a_1, ..., a_d \in \mathbb{Z}^n$ as follows:
$$L^\bot := \left\{ u\in \mathbb{Z}^n : \langle a_i, u \rangle = 0 \text{ for } 1 \le i \le d \right\}.$$
Or equivalently we define the lattice $L$ generated by the integer linear combinations of $a_i$'s and $L^\bot$ is then the lattice whose vectors are orthogonal to all the vectors of $L$.
Your case is just a particular one where $d=1$. And you are right about the dimension, it is $n - d$.
There are a lot of other known properties of these lattices (for instance, $\det(L^\bot) \le \det(L)$ and $(L^\bot)^\bot = span(L)\cap\mathbb{Z}^n$).
Section 2 of Merkle-Hellman Revisited: A Cryptanalysis of the Qu-Vanstone by Phong Nguyen and Jacques Stern present some discussion about this type of lattice and a polynomial-time algorithm to compute a LLL-reduced basis to them, which I've implemented in SAGE and published in this Github repository.
$\endgroup$ 1
