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?
[Math] Lattice generated by vectors orthogonal to an integer vector
algorithmsinteger-latticeslinear algebravector-lattices
Related Solutions
It is, in fact, a difficult problem. But not in dimension 2.
From a given basis (a set of independant vectors) of an integer lattice, you are trying to find a shortest non-zero) vector of that lattice. This is the shortest vector problem (SVP), and for larger dimensions it is in fact hard (known results include NP-hardness for randomized reductions and infinity norm).
The problem is that you could potentially get a short vector from a weird integer combination of the basis vectors, as the way they interact with each other is really hard to predict (especially in larger dimensions).
In dimensions larger than two, there are in fact no better known ways to generate a short vector than to enumerate all possible vectors in a given sphere. There are ways to avoid generating too many vectors, but the complexity is still exponential. The LLL algorithm is a polynomial approach that exploits the basic idea of trying to create shorter vectors by working on only two vectors at a time (a generalisation of the 2-dimensional case), but it only gives you a relativly short vector (best proof gives you a factor of $2^{O(n)}$ on the size :().
In dimension two however, the LLL algorithm (Called Lagrange's algorithm, sometimes erroneously attributed to Gauss, a generalisation of the euclidean algorithm.) gives you a basis of the lattice made of the shortest and the second shortest (independant) vector of the lattice in polynomial time.
Short story in dimension 2 : from the largest vector of your basis, you add/remove the shortest one as to make it shorter. Rinse and repeat. (works the same way as the euclidean algorithm to find the pgcd of two integers)
Exemple : from $\displaystyle \binom{5}{5}$ and $\displaystyle \binom{14}{13}$.
you remove two times $\displaystyle \binom{5}{5}$ from $\displaystyle \binom{14}{13}$, forming $\displaystyle \binom{4}{3}$. as an integer combination, this new vector is inside your lattice.
your new vectors are $\displaystyle \binom{5}{5}$ and $\displaystyle \binom{4}{3}$. You remove the latter from the former, and you get $\displaystyle \binom{1}{2}$.
now you have $\displaystyle \binom{1}{2}$ and $\displaystyle \binom{4}{3}$. You remove the former twice from the latter, and get $\displaystyle \binom{2}{-1}$.
now you have $\displaystyle \binom{2}{-1}$ and $\displaystyle \binom{1}{2}$. You can't make any of them shorter by adding/removing the other. The LLL algorithm in dimension 2 (called the Lagrange or Gauss algorithm) tells you that those are the shortest vectors in the lattice (non dependant).
This is all usually done by using unitary transformation (multiplication by integer lattices of determinant $\pm 1$) on the lattice basis (a $n\times n$ matrix). Here we did :
$$ \left(\begin{array}{cc} 5&14 \\5 &13\end{array}\right) \left(\begin{array}{cc}1 & -2\\ 0&1\end{array}\right)\left(\begin{array}{cc}1 &0 \\-1 &1\end{array}\right)\left(\begin{array}{cc}1 & -2\\ 0&1\end{array}\right)=\left(\begin{array}{cc} 1&2 \\ 2&-1\end{array}\right) $$
the original basis is on the left, and each step is one of the multiplying matrices (from left to right). The end result is on the right. There usually are $\left(\begin{array}{cc}0 &1 \\ 1&0\end{array}\right)$ matrices in between for swapping the two vectors (that way the shortest one is on the left), but I removed those here for clarity.
For larger dimensions, it gets ugly. Couldn't find anything nice for the 2 dimensional case, so let's go :
Inner working :
You have two vectors $u$ and $v$, sorted by euclidean length. We define the coefficient $\mu=\dfrac{u\cdot v}{\|u\|^2}$. that coefficient $\mu$ represents the relative length of the projection of $v$ over $u$ (see picture below). Then making the vector $v$ as short as possible is done by removing $\lceil \mu \rfloor \times u$ from $v$. We get a new vector $v$ such that one of the following happens :
the new $\mu$ is in $\left[-\dfrac{1}{2};\dfrac{1}{2}\right]$, meaning that the $v$ vector is inside the two vertical bars. This is called size-reduced.
On the left side the vector $v$ is inside the circle of radius $\|u\|$, meaning that $v$ is now shorter than $u$. Therefore swapping position of $u$ and $v$ will yield $|\mu|>\dfrac{1}{2}$ (you can see it by projecting $u$ on $v$)
On the right side however, $v$ is outside the circle (the Lovasz condition is said to be verified) and therefore swapping the places of $u$ and $v$ wouldn't yield anything. The basis is said LLL-reduced, and $u$ is the shortest non-zero vector of the lattice.
Proof :
let's say it isn't. There are $x$ and $y$ integers ($x\neq 0$) such that $xu+yv$ is shorter than $u$.
$$ \begin{aligned} \|xu+yv\|^2 &= x^2\|u\|^2+2xy(u\cdot v)+y^2\|v\|^2\\ &= x^2\|u\|^2+2\mu xy \|u\|^2+y^2\|v\|^2\\ &\geq (x^2+2\mu xy +y^2)\|u\|^2\\ &\geq (x^2- |xy| +y^2)\|u\|^2 \end{aligned} $$
Either $x^2$ or $y^2$ is larger than $|xy|$. Therefore $(x^2- |xy| +y^2)$ is larger than $\min(x^2;y^2)$. If that minimum is $0$, $xu+yv$ is a non-zero integer combination of $u$ or $v$, and therefore larger than $u$ (contradiction). If it isn't, then $(x^2- |xy| +y^2)>0$ and we get a contradiction.
Therefore $u$ is the shortest vector.
For LLL in larger dimension, you do the same two vectors at a time, selecting the two vectors using a process that's similar to a bubble sort : once a pair of vectors is done you get to the next vector, and you move down each time you swap vectors. For the $\mu$ coefficient you use the Gram-Schmidt Orthogonalisation.
Unless I made a mistake (so much for reputable...), the answer is 93150. Here is how to compute it in GAP (you could call it from Sage...). First, start with the generators of the Leech lattice (as in Conway, Sloane; but Wikipedia has a version one can paste):
Leechgens:=[
[8,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[4,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[4,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[4,0,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[4,0,0,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[4,0,0,0,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[4,0,0,0,0,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[2,2,2,2,2,2,2,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[4,0,0,0,0,0,0,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[4,0,0,0,0,0,0,0,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[4,0,0,0,0,0,0,0,0,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0],
[2,2,2,2,0,0,0,0,2,2,2,2,0,0,0,0,0,0,0,0,0,0,0,0],
[4,0,0,0,0,0,0,0,0,0,0,0,4,0,0,0,0,0,0,0,0,0,0,0],
[2,2,0,0,2,2,0,0,2,2,0,0,2,2,0,0,0,0,0,0,0,0,0,0],
[2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,0,0,0,0,0,0,0,0],
[2,0,0,2,2,0,0,2,2,0,0,2,2,0,0,2,0,0,0,0,0,0,0,0],
[4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,4,0,0,0,0,0,0,0],
[2,0,2,0,2,0,0,2,2,2,0,0,0,0,0,0,2,2,0,0,0,0,0,0],
[2,0,0,2,2,2,0,0,2,0,2,0,0,0,0,0,2,0,2,0,0,0,0,0],
[2,2,0,0,2,0,2,0,2,0,0,2,0,0,0,0,2,0,0,2,0,0,0,0],
[0,2,2,2,2,0,0,0,2,0,0,0,2,0,0,0,2,0,0,0,2,0,0,0],
[0,0,0,0,0,0,0,0,2,2,0,0,2,2,0,0,2,2,0,0,2,2,0,0],
[0,0,0,0,0,0,0,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0],
[-3,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]]*1/ER(8);
Now calculate the Gram matrix, and -- using it -- the vectors of length at most 4:
gap> gram:=List(Leechgens,x->List(Leechgens,y->x*y));;
gap> s:=ShortestVectors(gram,4);;
These are now coefficient vectors, so expand. Also we need to add negatives:
gap> short:=List(s.vectors,x->x*Leechgens);;
gap> short:=List(short,Immutable);; # so sets can remember they are sorted
gap> short:=Union(short,-short);;
We can verify the patterns of nonzero entries (as on p. 133 in Conway/Sloane)
gap> Collected(List(short,x->Number(x,y->not IsZero(y))));
[ [ 2, 1104 ], [ 8, 97152 ], [ 24, 98304 ] ]
And now, for the piece de resistance:
gap> Number(short,x->IsZero(x*short[1]));
93150
Best Answer
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)$