Gram-Schmidt 直交化

Last updated Nov 11, 2022 Edit Source

Gram-Schmidt 直交化 (GSO; Gram-Schmidt Orthonormalization) とは実 $m$ 次元ベクトル空間 $\mathbb{R}^m$ の任意の $\mathbb{R}$ ベクトル空間としての基底を直交基底に変換する方法です. $\mathbf{b} _ n$ の直交化は $\mathbf{b} _ {1},\ldots, \mathbf{b} _ {n-1}$ すべてと直交するように元の高さのまま移動させます. GSOのWikipedia のgifがわかりやすいです.

Definition 1 (GSOベクトル) $n$ 次元格子 $L\subseteq \mathbb{R}^m$ の順序付き基底 ${\mathbf{b} _ {1},\ldots, \mathbf{b} _ {n}}$ に対するGSOベクトル $\mathbf{b} _ {1}^* ,\ldots, \mathbf{b} _ {n}^ *\in\mathbb{R}^m$ を次のように定義する. また $\mu _ {i,j}$ をGSO係数と呼ぶ.

$$ \begin{aligned} &\begin{dcases} \mathbf{b} _ 1^* := \mathbf{b} _ 1 \\ \mathbf{b} _ i^ * := \mathbf{b} _ i - \sum _ {j=1}^{i-1} \mu _ {i, j} \mathbf{b} _ j^ * & (2\leq i\leq n) \\ \end{dcases} \\ &\quad\mu _ {i, j} := \frac{\langle \mathbf{b} _ i, \mathbf{b}_j^ * \rangle}{| \mathbf{b} _ j^ * |^2} \qquad (1\leq j<i\leq n) \end{aligned} $$

行列を用いて表現すると次のように(要詳細) $B, B^* , U$ を定義したとき $B = UB^ *$ が成り立つと書ける.

$$ \begin{aligned} B &= \begin{pmatrix} \mathbf{b} _ 1 \\ \vdots \\ \mathbf{b} _ n \\ \end{pmatrix} & B^* &= \begin{pmatrix} \mathbf{b} _ 1^ * \\ \vdots \\ \mathbf{b} _ n^ * \\ \end{pmatrix} & U &= \begin{pmatrix} 1 & 0 & 0 & \cdots & 0 \\ \mu _ {2,1} & 1 & 0 & \cdots & 0 \\ \mu _ {3,1} & \mu_{3,2} & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ \mu _ {n,1} & \mu _ {n,2} & \mu _ {n,3} & \cdots & 1 \\ \end{pmatrix} \end{aligned} $$

Theorem 2 (GSOベクトルの基本性質)

1. 任意の $1\leq i<j\leq n$ に対して $\langle\mathbf{b}_ i^* , \mathbf{b} _j^ *\rangle = 0$ が成り立つ.
2. 任意の $1\leq i\leq n$ に対して $|\mathbf{b}_ i^ * |\leq|\mathbf{b} _i|$ が成り立つ.
3. 任意の $1\leq i\leq n$ に対して $\langle\mathbf{b} _ 1^* ,\ldots,\mathbf{b} _ i^ *\rangle_{\mathbb{R}} = \langle\mathbf{b} _ 1,\ldots,\mathbf{b} _ i\rangle _ {\mathbb{R}}$ が成り立つ.
4. $\mathrm{vol}(L) = \prod _ {i=1}^n|\mathbf{b} _ i^*|$ が成り立つ.

Proof.

1. $j$ に関する数学的帰納法により示す. $j=1$ のときは証明すべきことはない. $1,\ldots,j$ について成立していると仮定する. $j+1$ のとき任意の $1\leq i<j+1$ に対して $$ \begin{aligned} \langle\mathbf{b} _ i^ * , \mathbf{b} _ {j+1}^ * \rangle &= \left\langle\mathbf{b} _ i^ * , \mathbf{b} _ {j+1} - \sum _ {k=1}^j\mu _ {j+1, k}\mathbf{b} _ {k}^ * \right\rangle \\ &= \langle\mathbf{b} _ i^ * , \mathbf{b} _ {j+1}\rangle - \mu _ {j+1,i}\langle\mathbf{b} _ i^ * , \mathbf{b} _ {i}^ * \rangle \\ &= \langle\mathbf{b} _ i^ * , \mathbf{b} _ {j+1}\rangle - \frac{\langle \mathbf{b} _ {j+1}, \mathbf{b} _ i^ * \rangle}{| \mathbf{b} _ i^ * |^2}|\mathbf{b} _ i^ * |^2 \\ &= 0 \end{aligned} $$ が成り立つ. よって, 数学的帰納法より任意の $1\leq i<j\leq n$ に対して $\langle\mathbf{b} _ i^ * , \mathbf{b} _ j^ * \rangle = 0$ が成り立つ.

2. $i=1$ のとき $\mathbf{b} _ 1^* = \mathbf{b} _ 1$ より明らか. $i\geq 2$ のとき $$ |\mathbf{b}_ i|^2 = |\mathbf{b} _ i^ * |^2 + \sum_{j=1}^{i-1}\mu _ {i,j}^2|\mathbf{b}_j^ * |^2\geq|\mathbf{b} _ i^ * |^2 $$ より成り立つ.

3. 任意の $1\leq k\leq i$ に対し, $\mathbf{b} _ k = \mathbf{b} _ k^* + \sum _ {j=1}^{k-1} \mu _ {k, j}\mathbf{b} _ j^ *$ より, $\mathbf{b} _ k\in\langle\mathbf{b} _ 1^ * ,\ldots,\mathbf{b} _ i^ * \rangle _ {\mathbb{R}}$ がわかる. よって $\langle\mathbf{b} _ 1,\ldots,\mathbf{b} _ i\rangle _ {\mathbb{R}}\subseteq\langle\mathbf{b} _ 1^ * ,\ldots,\mathbf{b} _ i^ * \rangle _ {\mathbb{R}}$ が成り立つ. 逆向きの包含関係は $i$ に関する数学的帰納法で示す. $i = 1$ のとき $\mathbf{b} _ 1^ * = \mathbf{b} _ 1$ より明らか. $i=k-1$ のとき成り立つと仮定すると $i=k$ のとき $\mathbf{b} _ k^ * = \mathbf{b} _ k - \sum _ {j=1}^{k-1} \mu _ {k, j}\mathbf{b} _ j^ *$ より $\mathbf{b} _ k^ * \in\langle\mathbf{b} _ 1,\ldots,\mathbf{b} _ i\rangle _ {\mathbb{R}}$ , よって任意の $i$ について示された. よって $\langle\mathbf{b} _ 1^ * ,\ldots,\mathbf{b} _ i^ * \rangle _ {\mathbb{R}}=\langle\mathbf{b} _ 1,\ldots,\mathbf{b} _ i\rangle _ {\mathbb{R}}$ である.

4. $B=UB^*$ と $\det(U) = 1$, GSOベクトルの直交性より $$ \begin{aligned} \mathrm{vol}(L)^2 &= \det(BB^\top) \\ &= \det(UB^ * (B^ * )^\top U^\top) \\ &= \det(B^ * (B^ * )^\top) \\ &= \prod _ {i=1}^n|\mathbf{b} _ i^ * |^2 \end{aligned} $$

Theorem 3 (Hadamardの不等式) GSOベクトルの基本性質 2, 4 より次のことが分かる.

$$ \mathrm{vol}(L)\leq\prod _ {i=1}^n|\mathbf{b} _ i| $$

つまり, ${\mathbf{b} _ {1},\ldots, \mathbf{b} _ {n}}$ が直交基底$\iff\mathrm{vol}(L)=\prod _ {i=1}^n|\mathbf{b} _ i|$ である.

Definition 4 (射影格子) $n$ 次元格子 $L\subseteq\mathbb{R}^m$ の基底 ${\mathbf{b} _ {1},\ldots, \mathbf{b} _ {n}}$ に対し, 各 $1\leq l\leq n$ に対して $\langle\mathbf{b} _ {1},\ldots, \mathbf{b} _ {l-1}\rangle _ \mathbb{R}$ の直交補空間への直交射影を $\pi _ l:\mathbb{R}^m\to\langle\mathbf{b} _ {1},\ldots, \mathbf{b} _ {l-1}\rangle _ \mathbb{R}^\bot$ とする. 定理 2 の 1,3 より

$$ \begin{aligned} \langle\mathbf{b} _ {1},\ldots, \mathbf{b} _ {l-1}\rangle _ \mathbb{R}^\bot &= \langle\mathbf{b} _ {1}^ * ,\ldots, \mathbf{b} _ {l-1}^ * \rangle _ \mathbb{R}^\bot = \langle\mathbf{b} _ {l}^ * ,\ldots, \mathbf{b} _ {n}^ * \rangle _ \mathbb{R} \\ \pi _ l(\mathbf{b}_i) &= \sum _ {j=l}^i\mu _ {i,j}\mathbf{b} _ j^ * \\ \end{aligned} $$

となる. すると集合 $\pi _ l(L)$ は ${\pi _ l(\mathbf{b} _ {l}),\ldots,\pi _ l(\mathbf{b} _ {n})}$ を基底に持つ $n-l+1$ 次元の格子であり, $\pi _ l(L)$ を射影格子 (projected lattice) と呼ぶ.

$O(N^3)$

1

def gram_schmidt():

• 格子暗号解読のための数学的基礎 ー格子基底簡約アルゴリズム入門ー