Let $\Lambda$ be an $n$-dimensional lattice in $\mathbb R^n$ and let $\cal B$ be the set of all bases that generate $\Lambda$. For a basis $\mathbf{B}=[\mathbf{b}_1, ... ,\mathbf{b}_n]\in {\cal B}$, define $\mathbf{B}^\dagger = [\mathbf{b}^\dagger_1, ... ,\mathbf{b}^\dagger_n]$ to be the Gram-Schmidt orthogonalization of $\mathbf B$ (i.e., $\mathbf{B} = \mathbf{B}^\dagger\mathbf{U}$, for some upper-triangular matrix $\mathbf{U}$ with unit diagonal).

I'm interested in the existence of a lattice basis $\mathbf{B}\in{\cal B}$ that has the following property: $$||\mathbf{b}^\dagger_i||\leq||\mathbf{b}^\dagger_j||,\; \mbox{for all }\; 1\leq i < j \leq n.$$

Does such a basis exist for any $\Lambda$? Is this related to any problems already studied in the literature? Any pointers/insight will be very much appreciated. Thanks!


1 Answer 1


$\def\b{{\bf b}}$ No, not any lattice has such a basis.

Notice that $||\b_n^\dagger||$ is the distance from $\b_n$ to the hyperplane $H_{n-1}=\langle \b_1,\dots,\b_{n-1}\rangle $; thus it is not greater than the minimal length of a lattice vector outside $H_{n-1}$. Moreover, they can be equal only in the case when this shortest vector is orthogonal to $H_{n-1}$.

Now, take a lattice spanned by the equilateral triangle with unit side length in the plane. Then $||{\bf b}_1||\geq 1$, and $||{\bf b}_2^\dagger||\leq 1$; the equality in the second case is achieved only if $H_1$ is orthogonal to some unit lattice vector; but then $||{\bf b}_1||=\sqrt3$. So in any case $||{\bf b}_1^\dagger||>||{\bf b}_2^\dagger||$.

More generally, we see that a lattice $\Lambda$ admits such a basis if it has some "layered" structure: the distance between two neighboring lattice hyperplanes parallel to $H_{n-1}$ is at least the smallest length of a lattice vector in $H_{n-1}$, and the same condition inductively holds for $\Lambda\cap H_{n-1}$. But even this condition seems to be quite weak.


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.