02 基本区域、格行列式与正交化 适用范围：计算格与格密码中的欧氏几何基础。整理日期：2026-09-26。
前置笔记：01 格与格基 。
设 B = [ b 1 , … , b n ] ∈ R m × n B=[b_1,\ldots,b_n]\in\mathbb R^{m\times n} B = [ b 1 , … , b n ] ∈ R m × n Λ = L ( B ) \Lambda=\mathcal L(B) Λ = L ( B ) span ( B ) \operatorname{span}(B) span ( B ) n n n
基本区域
基 B B B
P ( B ) = { B x : x ∈ [ 0 , 1 ) n } . \mathcal P(B)=\{Bx:x\in[0,1)^n\}. P ( B ) = { B x : x ∈ [ 0 , 1 ) n } . 它沿所有格向量平移后，构成整个线性空间的不交划分：
span ( B ) = ⨆ v ∈ Λ ( v + P ( B ) ) . \operatorname{span}(B)
=\bigsqcup_{v\in\Lambda}\bigl(v+\mathcal P(B)\bigr). span ( B ) = v ∈ Λ ⨆ ( v + P ( B ) ) . 半开区间保证边界点只属于一个区域。这可以直接从坐标分解 x = ⌊ x ⌋ + ( x − ⌊ x ⌋ ) x=\lfloor x\rfloor+(x-\lfloor x\rfloor) x = ⌊ x ⌋ + ( x − ⌊ x ⌋)
基本区域并不唯一；P ( B ) \mathcal P(B) P ( B )
格行列式
格行列式是基本区域的体积，也是格自身的不变量：
det Λ : = vol n ( P ( B ) ) = det ( B T B ) . \det\Lambda
:=\operatorname{vol}_n\bigl(\mathcal P(B)\bigr)
=\sqrt{\det(B^TB)}. det Λ := vol n ( P ( B ) ) = det ( B T B ) . 当 m = n m=n m = n det Λ = ∣ det B ∣ \det\Lambda=|\det B| det Λ = ∣ det B ∣
换成等价格基 B ′ = B U B'=BU B ′ = B U U U U
det ( B ′ T B ′ ) = ( det U ) 2 det ( B T B ) = det ( B T B ) . \det(B'^TB')
=(\det U)^2\det(B^TB)
=\det(B^TB). det ( B ′ T B ′ ) = ( det U ) 2 det ( B T B ) = det ( B T B ) . 因此，基本区域的形状可以改变，体积保持不变。
det Λ \det\Lambda det Λ
Gram–Schmidt 正交化
定义
b i ∗ = b i − ∑ j < i μ i , j b j ∗ , μ i , j = ⟨ b i , b j ∗ ⟩ ∥ b j ∗ ∥ 2 . b_i^*
=b_i-\sum_{j<i}\mu_{i,j}b_j^*,
\qquad
\mu_{i,j}
=\frac{\langle b_i,b_j^*\rangle}{\|b_j^*\|^2}. b i ∗ = b i − j < i ∑ μ i , j b j ∗ , μ i , j = ∥ b j ∗ ∥ 2 ⟨ b i , b j ∗ ⟩ . b i ∗ b_i^* b i ∗ b i b_i b i
b 1 ∗ , … , b n ∗ b_1^*,\ldots,b_n^* b 1 ∗ , … , b n ∗ 1 1 1 每个前缀张成的空间保持不变：
span ( b 1 , … , b i ) = span ( b 1 ∗ , … , b i ∗ ) \operatorname{span}(b_1,\ldots,b_i)=\operatorname{span}(b_1^*,\ldots,b_i^*) span ( b 1 , … , b i ) = span ( b 1 ∗ , … , b i ∗ )
结果依赖基及其排列顺序。
b i ∗ b_i^* b i ∗
最后一条与第一篇的幺模换基条件相呼应：Gram–Schmidt 使用的投影系数一般不是整数。[1，第 4—5 页，第 2 节、定义 6；2，第 8—10 页，第 3 节]
二维例子：扣除投影，保留垂直分量
取
b 1 = ( 2 0 ) , b 2 = ( 1 2 ) . b_1=\begin{pmatrix}2\\0\end{pmatrix},
\qquad
b_2=\begin{pmatrix}1\\2\end{pmatrix}. b 1 = ( 2 0 ) , b 2 = ( 1 2 ) . 第一步 b 1 ∗ = b 1 b_1^*=b_1 b 1 ∗ = b 1
μ 2 , 1 = ⟨ b 2 , b 1 ∗ ⟩ ∥ b 1 ∗ ∥ 2 = 2 4 = 1 2 , b 2 ∗ = b 2 − 1 2 b 1 ∗ = ( 0 2 ) . \mu_{2,1}
=\frac{\langle b_2,b_1^*\rangle}{\|b_1^*\|^2}
=\frac{2}{4}
=\frac12,
\qquad
b_2^*
=b_2-\frac12b_1^*
=\begin{pmatrix}0\\2\end{pmatrix}. μ 2 , 1 = ∥ b 1 ∗ ∥ 2 ⟨ b 2 , b 1 ∗ ⟩ = 4 2 = 2 1 , b 2 ∗ = b 2 − 2 1 b 1 ∗ = ( 0 2 ) . 即把 b 2 b_2 b 2 b 1 b_1 b 1 ( 1 , 0 ) T (1,0)^T ( 1 , 0 ) T ( 0 , 2 ) T (0,2)^T ( 0 , 2 ) T
图中左侧虚线箭头是 b 2 ∗ b_2^* b 2 ∗
正交不等于等价格基。 b 2 ∗ = − 1 2 b 1 + b 2 b_2^*=-\tfrac12b_1+b_2 b 2 ∗ = − 2 1 b 1 + b 2 b 2 ∗ ∉ L ( B ) b_2^*\notin\mathcal L(B) b 2 ∗ ∈ / L ( B ) L ( B ∗ ) ≠ L ( B ) \mathcal L(B^*)\ne\mathcal L(B) L ( B ∗ ) = L ( B ) 体积相同不等于格相同。 原平行四边形的面积为 ∣ det B ∣ = 4 |\det B|=4 ∣ det B ∣ = 4 ∥ b 1 ∗ ∥ ∥ b 2 ∗ ∥ = 2 ⋅ 2 = 4 \|b_1^*\|\|b_2^*\|=2\cdot2=4 ∥ b 1 ∗ ∥∥ b 2 ∗ ∥ = 2 ⋅ 2 = 4
向量例子取自 Micciancio 讲义 PDF 第 9 页、图 4 附近；投影计算、格点对照与配图为本次整理。[2]
正交化与格行列式的联系
det Λ = vol n ( P ( B ) ) = det ( B T B ) = ∏ i = 1 n ∥ b i ∗ ∥ . \det\Lambda
=\operatorname{vol}_n\bigl(\mathcal P(B)\bigr)
=\sqrt{\det(B^TB)}
=\prod_{i=1}^{n}\|b_i^*\|. det Λ = vol n ( P ( B ) ) = det ( B T B ) = i = 1 ∏ n ∥ b i ∗ ∥. 简短推导：写成 B = B ∗ T B=B^*T B = B ∗ T T T T 1 1 1
det ( B T B ) = det ( ( B ∗ ) T B ∗ ) = ∏ i = 1 n ∥ b i ∗ ∥ 2 . \det(B^TB)
=\det\bigl((B^*)^TB^*\bigr)
=\prod_{i=1}^{n}\|b_i^*\|^2. det ( B T B ) = det ( ( B ∗ ) T B ∗ ) = i = 1 ∏ n ∥ b i ∗ ∥ 2 . 各个 ∥ b i ∗ ∥ \|b_i^*\| ∥ b i ∗ ∥ ∥ b i ∗ ∥ ≤ ∥ b i ∥ \|b_i^*\|\leq\|b_i\| ∥ b i ∗ ∥ ≤ ∥ b i ∥
det Λ ≤ ∏ i = 1 n ∥ b i ∥ , \det\Lambda\leq\prod_{i=1}^{n}\|b_i\|, det Λ ≤ i = 1 ∏ n ∥ b i ∥ , 等号当且仅当原基向量两两正交。[1，第 5 页，第 2 节末；2，第 10 页引理 13、第 12—13 页定义 15、定理 16、引理 17]
来源
Oded Regev，Lattices in Computer Science ，Lecture 1: Introduction ，Fall 2004。第 2 页定义 3、第 4 页定义 5、第 4—5 页第 2 节。原文
Daniele Micciancio，Point Lattices ，PDF 页首标注 Fall 2017，由 2019 年课程页链接。PDF 第 8—10 页第 3 节、第 10—13 页第 4 节。原文
来源于 2026-09-26 核对。正文按已确认的草稿整理，并按要求补充正交化例子与配图。
引用此笔记
