Skip to content

定義

Lattice

Given n linearly independent vectors \mathbf{b_1}, \mathbf{b_2}, \cdots, \mathbf{b_n} \in \mathbb{R^m}, the lattice generated by them is defined as

L(\mathbf{b_1}, \cdots, \mathbf{b_n}) \overset{\text{def}}{=} \Big{\{}\sum_{i=1}^{n}x_i\mathbf{b_i} \ | \ x_i \in \mathbb{Z}\Big{\}}

We can write \mathbf{b_1}, \cdots, \mathbf{b_n} as a matrix \mathbf{B} for convenience

\mathbf{B} = \begin{pmatrix} | & & | \\ \mathbf{b_1} & \cdots & \mathbf{b_n} \\ | & & | \end{pmatrix}
L(\mathbf{B}) \overset{\text{def}}{=} \{\mathbf{Bx} \ | \ \mathbf{x} \in \mathbb{Z}^n \}

We call \{\mathbf{b_1}, \cdots, \mathbf{b_n}\} a basis of lattice
We call n the rank of lattice
We call m the dimension of lattice
When n = m, we call the lattice a full-rank lattice

Lattice 跟 Vector Space 很像,但 Lattice 是 vectors 整數倍的 linear combination

Unimodular Matrix

A matrix \mathbf{U} \in \mathbb{Z}^{n \times n} is unimodular if |\text{det}(\mathbf{U})| = 1

性質 ( property )

  1. \mathbf{U} is unimodular \Leftrightarrow \mathbf{U}^{-1} is unimodular

Fundamental Parallelepiped

Given n linearly independent vectors \mathbf{b_1}, \mathbf{b_2}, \cdots, \mathbf{b_n} \in \mathbb{R^m}, their fundamental parallelepiped is defined as

P(\mathbf{b_1}, \cdots, \mathbf{b_n}) \overset{\text{def}}{=} \Big{\{}\sum_{i=1}^{n}x_i\mathbf{b_i} \ | \ x_i \in \mathbb{R}, 0 \le x_i < 1\Big{\}}

Determinant of Lattice

Let \mathbf{B} be the basis matrix of L

\text{det}(L) = \text{det}(\mathbf{B}) = \text{vol}(P(\mathbf{B}))

\text{det}(L) 是個定值,所有的 bases 都有一樣的 determinant

Minimum Distance of Lattice

\lambda_1(L) = \underset{v \ \in \ L \setminus 0}{min} \|v\|