Dual Lattice Explained: Definition, Basis, and Worked Example

The dual lattice of a full-rank lattice $\Lambda$ contains every vector whose inner product with every point of $\Lambda$ is an integer. It is a useful way to turn questions about spacing in the original lattice into questions about directions in another one. If you already know what a basis is, the construction is just one matrix operation: take its inverse transpose.

\Lambda^* = \{y \in \mathbb{R}^n : \langle y,x\rangle \in \mathbb{Z} \text{ for every } x \in \Lambda\}

Why is the dual basis the inverse transpose?

Write the basis vectors as the columns of an invertible matrix $B$ . Every original lattice point has the form $x=Bz$ for an integer vector $z$ . A candidate dual vector $y$ must satisfy $y^\top Bz \in \mathbb{Z}$ for every integer $z$ . This happens exactly when each coordinate of $B^\top y$ is an integer. Solving for $y$ gives the dual basis:

\Lambda(B)^* = \Lambda(B^{-\top}), \qquad B^{-\top}=(B^{-1})^\top

The columns of $B^{-\top}$ pair with the columns of $B$ like coordinate rulers: their inner product is 1 for the matching pair and 0 for the others. This is why a dual basis is more precise than simply drawing a second grid rotated by ninety degrees.

Worked example: a rectangular lattice

Take $B=\operatorname{diag}(2,3)$ . The original lattice consists of the points $(2a,3b)$ with integer $a,b$ . Its dual basis is $B^{-\top}=\operatorname{diag}(1/2,1/3)$ , so the dual points are $(c/2,d/3)$ . Check the definition directly:

\langle (c/2,d/3),(2a,3b)\rangle = ac+bd \in \mathbb{Z}

The original fundamental rectangle has area 6. The dual rectangle has area $1/6$ . In general, $\det(\Lambda^*)=1/\det(\Lambda)$ . Here “det” means the positive covolume of the lattice, not the signed determinant of one chosen basis. The example also shows why the dual of a coarsely spaced lattice is finely spaced in the corresponding directions.

Does the choice of basis change the dual lattice?

No. Two bases of the same lattice differ by an integer matrix $U$ with determinant $\pm1$ : $B\prime=BU$ . Their dual bases also differ by an integer change of basis, so they generate the same set of dual points. The definition through inner products makes this independence clear even before doing the matrix algebra. The dual is a property of the lattice, while a basis is one way to describe it.

Where does duality appear in cryptography?

Dual vectors expose modular relationships that are useful in attacks and proofs. For a public matrix $A$ , the two associated q-ary lattices are dual up to a factor of $1/q$ . A short vector in one can describe a linear test on noisy samples from the other. This is the geometric starting point of a dual attack on Learning With Errors. It does not mean that taking a dual basis alone breaks LWE; finding the needed short vector remains the hard part.

The dual also appears in the smoothing parameter: it measures Gaussian mass on nonzero dual points. That relationship is one reason Gaussian distributions occur throughout lattice cryptography. For a concrete distribution and a numerical example, continue with discrete Gaussian sampling.

Common mistakes

Using $B^{-1}$ instead of $B^{-\top}$ . Basis vectors are columns, so the transpose matters for a skewed basis.
Assuming dual means perpendicular. The defining condition is an integer inner product, which can be nonzero.
Ignoring rank. The simple inverse-transpose formula requires a square, full-rank basis. Lower-rank lattices need a definition relative to their linear span.

6.1 Dual lattice explained