LLL - 格簡化基算法問題？
我有兩個相關的問題：
**版本 1：**讓 $ B={b_1,b_2,\dots,b_n} $ 是正交基 $ R^n $ . 應用 LLL 算法得到的關聯約簡基是什麼 $ B $ ?
我知道如何應用 LLL 算法，我可以將它應用於 $ R^3 $ 案子。（因此 $ n=3 $ 考試需要合理的時間，順便說一句，這是一道考試題。）
但這種情況是一般情況 $ n $ ，所以我不知道該怎麼辦？當向量正交時，是否有找到約簡基的捷徑？
這個問題的另一個版本如下：
**版本 2：**讓 $ B={b_1,b_2,\dots,b_6} $ 是正交基 $ R^6 $ .
有 $ ||b_1||=||b_3||=1 $ , $ ||b_2||^2=||b_6||^2=2 $ , $ ||b_4||^2=3,||b_5||^2=4 $
通過將 LLL 算法應用於此有序基獲得的相關簡化基是什麼 $ B $ ?
LLL算法有兩個主要部分：
- 減少步驟：重新計算基向量，旨在將 Gram-Schmidt 係數的值減少到小於一半的某個值。這個條件通常寫成 $ |\mu_{i, j}| < \frac{1}{2} $ .
- 交換步驟：交換基向量以達到 Lovász 條件，即 $ \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 $ .
請注意，交換步驟只是改變了向量的順序，所以，如果不執行歸約步驟，輸出只是輸入基礎的重新排序……
現在，什麼是已經正交的基的 Gram-Schmidt**正交化？回答這個問題會給你一個微不足道的關係 $ \mathbf{b}_i $ 和對應的GS向量 $ \mathbf{b}i^* $ . 什麼是價值觀 $ \mu{i, j} $ 鑑於 $ \mathbf{b}_i $ 和 $ \mathbf{b}_j $ 是正交的嗎？
有了這些資訊，您可以看到，對於正交基，簡化步驟被忽略，LLL 算法只是根據是否重新排序基向量 $ \delta \Vert \mathbf{b}{i}\Vert^2 \leq \Vert \mathbf{b}{i+1}\Vert^2 $ 或不。
要回答您的第二個問題，您只需執行您將在第一個問題中找到的“簡化 LLL”並獲得正確的重新排序。