02 基本区域、格行列式与正交化

适用范围：计算格与格密码中的欧氏几何基础。整理日期：2026-09-26。前置笔记：01 格与格基。

设 \(B=[b_1,\ldots,b_n]\in\mathbb R^{m\times n}\) 列满秩，\(\Lambda=\mathcal L(B)\)。以下使用欧氏内积与范数，体积均指 \(\operatorname{span}(B)\) 中的 \(n\) 维体积。

基本区域
#

基 \(B\) 对应的基本平行多面体为

\mathcal P(B)=\{Bx:x\in[0,1)^n\}.

它沿所有格向量平移后，构成整个线性空间的不交划分：

\operatorname{span}(B) =\bigsqcup_{v\in\Lambda}\bigl(v+\mathcal P(B)\bigr).

半开区间保证边界点只属于一个区域。这可以直接从坐标分解 \(x=\lfloor x\rfloor+(x-\lfloor x\rfloor)\) 理解。

基本区域并不唯一；\(\mathcal P(B)\) 是其中一种，其形状依赖所选的基。[1，第 2 页，定义 3；2，第 10—11 页，定义 14 及其后说明]

格行列式是基本区域的体积，也是格自身的不变量：

\det\Lambda :=\operatorname{vol}_n\bigl(\mathcal P(B)\bigr) =\sqrt{\det(B^TB)}.

当 \(m=n\) 时，\(\det\Lambda=|\det B|\)。

换成等价格基 \(B'=BU\)，其中 \(U\) 为幺模矩阵，有

\det(B'^TB') =(\det U)^2\det(B^TB) =\det(B^TB).

因此，基本区域的形状可以改变，体积保持不变。

\(\det\Lambda\) 的倒数刻画单位体积内的渐近格点数密度；比较疏密时，应在相同维数和尺度下理解。[1，第 4 页，定义 5；2，第 12—13 页，定义 15、引理 17、定理 18]

定义

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\) 在前面基向量所张空间的正交补上的分量，满足：

\(b_1^*,\ldots,b_n^*\) 两两正交，但不要求长度为 \(1\)。
每个前缀张成的空间保持不变： \(\operatorname{span}(b_1,\ldots,b_i)=\operatorname{span}(b_1^*,\ldots,b_i^*)\)。
结果依赖基及其排列顺序。
\(b_i^*\) 通常不属于原格，故正交化通常不是保持原格不变的换基。

最后一条与第一篇的幺模换基条件相呼应：Gram–Schmidt 使用的投影系数一般不是整数。[1，第 4—5 页，第 2 节、定义 6；2，第 8—10 页，第 3 节]

取

b_1=\begin{pmatrix}2\\0\end{pmatrix}, \qquad b_2=\begin{pmatrix}1\\2\end{pmatrix}.

第一步 \(b_1^*=b_1\)。第二步计算

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

即把 \(b_2\) 分解为沿 \(b_1\) 的投影 \((1,0)^T\) 与垂直分量 \((0,2)^T\)，再扣除前者。

图中左侧虚线箭头是 \(b_2^*\) 的平移。中、右两图使用相同刻度；阴影表示基本区域，边界开闭未在图中区分。

正交不等于等价格基。 \(b_2^*=-\tfrac12b_1+b_2\)。由于原基下坐标唯一且包含非整数系数，\(b_2^*\notin\mathcal L(B)\)，因此 \(\mathcal L(B^*)\ne\mathcal L(B)\)。
体积相同不等于格相同。 原平行四边形的面积为 \(|\det B|=4\)；正交化后矩形的面积为 \(\|b_1^*\|\|b_2^*\|=2\cdot2=4\)。

向量例子取自 Micciancio 讲义 PDF 第 9 页、图 4 附近；投影计算、格点对照与配图为本次整理。[2]

\det\Lambda =\operatorname{vol}_n\bigl(\mathcal P(B)\bigr) =\sqrt{\det(B^TB)} =\prod_{i=1}^{n}\|b_i^*\|.

简短推导：写成 \(B=B^*T\)，其中 \(T\) 为对角元全为 \(1\) 的上三角矩阵，则

\det(B^TB) =\det\bigl((B^*)^TB^*\bigr) =\prod_{i=1}^{n}\|b_i^*\|^2.

各个 \(\|b_i^*\|\) 随基变化，但它们的乘积保持不变。由 \(\|b_i^*\|\leq\|b_i\|\)，还得到 Hadamard 不等式：

\det\Lambda\leq\prod_{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 核对。正文按已确认的草稿整理，并按要求补充正交化例子与配图。