格密码笔记（三）

　　我们马上就要进入 lattice 相关的讨论了。鉴于我们很熟悉线性空间，我们可以先回顾线性空间的一些性质，来方便未来研究 lattice.

线性空间(vector spaces) 一个线性空间 $V$，是 ${\mathbb{R}}^m$ 的一个子集，满足$${\alpha }_1{\mathit{v}}_1+{\alpha }_2{\mathit{v}}_2\in V,\text{for all}{\mathit{v}}_1,{\mathit{v}}_2\in V,{\alpha }_1,{\alpha }_2\in \mathbb{R}$$
也就是说，一个线性空间，是对向量加法、标量乘法封闭的 ${\mathbb{R}}^m$ 的子集。

线性组合(linear combinations) ${\mathit{v}}_1,{\mathit{v}}_2,\dots ,{\mathit{v}}_k\in V$ 的一个线性组合是满足以下形式的向量： $$\mathit{w}={\alpha }_1{\mathit{v}}_1+{\alpha }_2{\mathit{v}}_2+\cdots +{\alpha }_k{\mathit{v}}_k,{\alpha }_1,\dots ,{\alpha }_k\in \mathbb{R}$$并将上述向量构成的集合$$\{{\alpha }_1{\mathit{v}}_1+\cdots +{\alpha }_1{\mathit{v}}_k:{\alpha }_1,\dots ,{\alpha }_k\in \mathbb{R}\}$$称为 $\{{\mathit{v}}_1,\dots ,{\mathit{v}}_k\}$ 的张成空间(span).

线性无关(linearly independence) 称一个向量集合 ${\mathit{v}}_1,\dots ,{\mathit{v}}_k\in V$ 线性无关，当且仅当方程 $${\alpha }_1{\mathit{v}}_1+{\alpha }_2{\mathit{v}}_2+\cdots +{\alpha }_k{\mathit{v}}_k=\mathbf{0}$$的唯一解是 ${\alpha }_1={\alpha }_2=\cdots =a_k=0$. 反之则称这个向量集合线性相关(linearly dependent).

基(bases) 向量空间 $V$ 的一个基，是可以张成 $V$ 的线性无关向量集合 ${\mathit{v}}_1,\dots ,{\mathit{v}}_n$. 也就是说，任何一个向量 $w\in V$ 都可以写成 ${\mathit{v}}_1,\dots ,{\mathit{v}}_n$ 的线性组合的形式，其线性组合的系数是唯一的。

　　接下来，我们讨论不同的基之间的关系，以及“维度”的概念。

1. 任何一个线性空间 $V$ 都有基。
2. 任何两个基，含有的向量个数是相同的。基的向量个数称为 $V$ 的维度(dimension).
3. 设 ${\mathit{v}}_1,\dots ,{\mathit{v}}_n$ 是 $V$ 的一个基，${\mathit{w}}_1,\dots ,{\mathit{w}}_n$ 是 $V$ 中的一个向量组。我们把 ${\mathit{w}}_j$ 写成 ${\mathit{v}}_i$ 的线性组合的形式：$$\begin{array}{rl}{\mathit{w}}_1& ={\alpha }_{11}{\mathit{v}}_1+{\alpha }_{12}{\mathit{v}}_2+\cdots +{\alpha }_{1n}{\mathit{v}}_n\\ {\mathit{w}}_2& ={\alpha }_{21}{\mathit{v}}_1+{\alpha }_{22}{\mathit{v}}_2+\cdots +{\alpha }_{2n}{\mathit{v}}_n\\ ⋮& ⋮\\ {\mathit{w}}_n& ={\alpha }_{n1}{\mathit{v}}_1+{\alpha }_{n2}{\mathit{v}}_2+\cdots +{\alpha }_{nn}{\mathit{v}}_n\end{array}$$那么 ${\mathit{w}}_1,\dots ,{\mathit{w}}_n$ 也是 $V$ 的一个基，当且仅当下面矩阵的行列式不为 0：$$\left(\begin{array}{cccc}{\alpha }_{11}& {\alpha }_{12}& \cdots & {\alpha }_{1n}\\ {\alpha }_{21}& {\alpha }_{22}& \cdots & {\alpha }_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ {\alpha }_{n1}& {\alpha }_{n2}& \cdots & {\alpha }_{nn}\end{array}\right)$$

　　我们接下来介绍如何度量向量的长度，以及向量的夹角。

点积(dot product) 设 $\mathit{v},\mathit{w}\in V\subset {\mathbb{R}}^m$. 记 $\mathit{v},\mathit{w}$ 的坐标如下：$$\mathit{v}=(x_1,x_2,\dots ,x_m),\mathit{w}=(y_1,y_2,\dots ,y_m)$$则记 $\mathit{v}$ 与 $\mathit{w}$ 的点积为$$\mathit{v}\cdot \mathit{w}=x_1{y}_1+x_2{y}_2+\cdots +x_m{y}_m$$若 $\mathit{v}\cdot \mathit{w}=0$，我们称 $\mathit{v}$ 与 $\mathit{w}$ 正交(orthogonal).

欧几里得范数(Euclidean norm) 向量 $\mathit{v}$ 的长度，或称欧几里得范数，为$$\Vert \mathit{v}\Vert =\sqrt{x_1^2+x_2^2+\cdots +x_m^2}$$显然有 $\mathit{v}\cdot \mathit{v}=\Vert \mathit{v}{\Vert }^2$.

　　有了点积这个工具，接下来就可以研究角度。设 $\mathit{v},\mathit{w}\in V\subset {\mathbb{R}}^m$. 我们有：

1. 记 $\theta$ 为向量 $\mathit{v},\mathit{w}$ 之间的角（这里我们把 $\mathit{v},\mathit{w}$ 的起始点都放在原点 $\mathbf{0}$）。则 $$\mathit{v}\cdot \mathit{w}=\Vert \mathit{v}\Vert \Vert \mathit{w}\Vert \cos \theta$$
2. (Cauchy-Schwarz 不等式) 两向量的点积的绝对值，不大于向量长度的积。$$|\mathit{v}\cdot \mathit{w}|\le \Vert \mathit{v}\Vert \Vert \mathit{w}\Vert$$

　　显然，两向量正交，则它们夹角是 90°. 来考虑向量相互正交的基：

正交基(orthogonal basis) 线性空间 $V$ 的一个正交基，是满足以下条件的基 ${\mathit{v}}_1,\dots ,{\mathit{v}}_n$：$${\mathit{v}}_i\cdot {\mathit{v}}_j=0\text{for all}i\ne j$$
额外地，若这个基还满足 $\Vert {\mathit{v}}_i\Vert =1$，则我们称这个基规范正交(orthonormal).

　　若一个基是正交的，则很多式子都可以化简。举个例子：若 ${\mathit{v}}_1,\dots ,{\mathit{v}}_n$ 是正交基，一个向量 $\mathit{v}=a_1{\mathit{v}}_1+\cdots +a_n{\mathit{v}}_n$ 是这个基的线性组合，则有 $$\begin{array}{rl}\Vert \mathit{v}{\Vert }^2& =\Vert a_1{\mathit{v}}_1+\cdots +a_n{\mathit{v}}_n{\Vert }^2\\ & =(a_1{\mathit{v}}_1+\cdots +a_n{\mathit{v}}_n)\cdot (a_1{\mathit{v}}_1+\cdots +a_n{\mathit{v}}_n)\\ & =\sum _{i=1}^n\sum _{j=1}^n{a}_i{a}_j({\mathit{v}}_i\cdot v_j)\\ & =\sum _{i=1}^n{a}_i^2\Vert {\mathit{v}}_i{\Vert }^2\end{array}$$最后一步的化简，正确性源于这个基里面的向量相互正交。若这还是一个规范正交基，式子可以进一步化简为 $\Vert \mathit{v}{\Vert }^2=\sum a_i^2$.

　　有生成规范正交基的算法 (Gram-Schmidt)，可以从任何一个向量组生成规范正交基，其张成空间不变。细节不再赘述，主要思路是将后面的向量除去所有前面向量方向上的分量。详情请阅维基百科。