3
$\begingroup$

I have two related questions:

Version 1: Let $B=\{b_1,b_2,\dots,b_n\}$ be an orthogonal basis for $R^n$. What is the associated reduced basis obtained by applying LLL algorithm to $B$?

I know how to apply LLL algorithm and I can apply it for $R^3$ case. (Since for $n=3$ it takes reasonable time in the exam, this is an exam question by the way.)

But this case is general case for $n$, so I don't know what to do? is there a shortcut to find the reduced basis when the vectors are orthogonal ?

another version of this question is the following:

Version 2: Let $B=\{b_1,b_2,\dots,b_6\}$ be an orthogonal basis for $R^6$ .

Having $||b_1||=||b_3||=1$, $||b_2||^2=||b_6||^2=2$, $||b_4||^2=3,||b_5||^2=4$

What is the associated reduced basis obtained by applying LLL algorithm to this ordered basis $B$?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

LLL algorithm has two main parts:

  1. the reduction step: which recomputes the basis vectors aiming to reduce the values of the Gram-Schmidt coefficients to some value smaller than one half. This condition is usually written as $|\mu_{i, j}| < \frac{1}{2}$.
  2. the swap step: which swaps basis vectors aiming to achieve the Lovász condition, that is $ \delta \Vert \mathbf{b}^*_{i}\Vert^2 \leq \Vert \mathbf{b}^*_{i+1}\Vert^2+ \mu_{i+1,i}^2\Vert \mathbf{b}^*_{i}\Vert^2$.

Notice that the swap step just changes the order of the vectors, so, if somehow the reduction step is not executed, the output is just a reordering of the input basis...

Now, what is the Gram-Schmidt orthogonalization of a basis that is already orthogonal? Answering this will give you a trivial relation between $\mathbf{b}_i$ and the corresponding GS vector $\mathbf{b}_i^*$. And what are the values of $\mu_{i, j}$ given that $\mathbf{b}_i$ and $\mathbf{b}_j$ are orthogonal?

With these information, you can see that, for an orthogonal basis, the reduction step is ignored and the LLL algorithm just reorder the basis vectors according to whether $ \delta \Vert \mathbf{b}_{i}\Vert^2 \leq \Vert \mathbf{b}_{i+1}\Vert^2$ or not.

And to answer your second question, you just have to run this "simplified LLL" that you will have found in the first question and get the correct reordering.

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ I think I got what you say: values of $\mu_{i, j}$ must be zero when the vectors are orthogonal and I need to check the swap condition only. for the version 2 the values is given for the norms of the vectors so that i could compare and reorder the basis and get: {b1,b3,b2,b4,b6,b5} i.e. there are two swaps. Am I right with this? But for the question Version1 the norm values are not given. so how can i reorder? and moreover i cannot see why a reordered basis is different than the original? aren't they the same thing eventually? why order matters? $\endgroup$
    – esra
    Aug 23, 2018 at 21:23
  • 1
    $\begingroup$ @esra if we reorder the vectors of a basis, then we get a new basis that spans the same lattice. So, if we don't consider the order as an attribute of the basis, then they are the same basis. But we usually consider an ordered basis, so order matters. We do that because the reduced bases have properties that depend on the order. For instance, in a LLL-reduced basis, we know that $\Vert \mathbf{b}_1 \Vert \le 2^{(n-1)/2} \cdot \lambda_1$, where $\lambda_1$ is the length of the shortest non-zero vector of the lattice. If we don't consider the order, than $\mathbf{b}_1$ isn't well defined. $\endgroup$
    – Hilder Vitor Lima Pereira
    Aug 24, 2018 at 6:37
  • 1
    $\begingroup$ @esra and for the first question, it is not possible to say in advance how the vectors will be reordered because it depends on their norms. So, I don't see how you would be able to answer with more details than something like "the associated basis is a basis with the same vectors, but reordered with respect to the condition $ \delta \Vert \mathbf{b}_{i}\Vert^2 \leq \Vert \mathbf{b}_{i+1}\Vert^2$". $\endgroup$
    – Hilder Vitor Lima Pereira
    Aug 24, 2018 at 6:42
  • 1
    $\begingroup$ @esra You are welcome :) If the answer is OK, please, don't forget to accept it, so we can reduce the statistics of "unanswered questions" on this website. $\endgroup$
    – Hilder Vitor Lima Pereira
    Aug 24, 2018 at 6:47
  • 1
    $\begingroup$ Now i did it already! i am new to the site. So slowly learning how to accept, vote up exc. thanks again $\endgroup$
    – esra
    Aug 24, 2018 at 6:49

Your Answer

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

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