Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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