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

适用范围：计算格与格密码中的欧氏几何基础。整理日期：2026-09-26。
前置笔记：[01 格与格基](/knowledge/lattices-and-bases/)。

设 $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]

## Gram–Schmidt 正交化

定义

$$
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$，再扣除前者。

![正交化的投影分解、格点变化与基本区域面积](/knowledge/attachments/bb4601ab031442c5.png)

图中左侧虚线箭头是 $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]

## 来源

1. Oded Regev，*Lattices in Computer Science*，Lecture 1: *Introduction*，Fall 2004。第 2 页定义 3、第 4 页定义 5、第 4—5 页第 2 节。[原文](https://cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/introduction.pdf)
2. Daniele Micciancio，*Point Lattices*，PDF 页首标注 Fall 2017，由 2019 年课程页链接。PDF 第 8—10 页第 3 节、第 10—13 页第 4 节。[原文](https://cseweb.ucsd.edu/classes/fa19/cse206A-a/lec1.pdf)

来源于 2026-09-26 核对。正文按已确认的草稿整理，并按要求补充正交化例子与配图。

## 引用此笔记

- [00 概览与阅读路线](/knowledge/lattices-overview/)
- [03 逐次极小值与 Minkowski 定理](/knowledge/successive-minima-and-minkowski/)
- [05 格基约化与 LLL 算法](/knowledge/lattice-reduction-and-lll/)
- [06 Babai 最近平面算法与近似 CVP](/knowledge/babai-nearest-plane/)
- [07 对偶格与对偶基](/knowledge/dual-lattices/)
- [09 高斯函数与离散高斯分布](/knowledge/gaussian-functions-and-discrete-gaussians/)
- [10 傅里叶变换与 Poisson 求和公式](/knowledge/fourier-transform-and-poisson-summation/)
- [12 q 元格与模线性方程](/knowledge/q-ary-lattices/)
- [15 高斯启发式与随机球面模型](/knowledge/gaussian-heuristic-and-random-spheres/)
- [16 投影格、BKZ 与局部 SVP](/knowledge/projected-lattices-bkz-and-local-svp/)