# Definition of Dual Lattice

1- Can someone explain why we have the definition of dual of a lattice like $$\Lambda^*=\{\vec{v}\in span(\textbf{B}): \langle \vec{v},\vec{x} \rangle \in \mathbb{Z}, \forall \vec{x} \in \Lambda\}$$.

2- There is an explanation in the lecture note of Daniele Micciancio, (CSE206A) Spring 2007, here, but I cannot follow some parts of it.

For the highlighted lines, we first note that for any invertible matrix $$M$$ for the field of definition of the inner product we trivially have $$\langle \mathbf x,\mathbf y\rangle = \langle \mathbf x,M\cdot M^{-1}\mathbf y\rangle.$$ Using this with the matrix $$M=\mathbf B^T\mathbf B$$ and $$\mathbf y=f(\mathbf x)$$ we see that $$\langle x,f(\mathbf B)\rangle=\langle \mathbf x,\mathbf B^T\mathbf B(\mathbf B^T\mathbf B)^{-1}f(\mathbf B)\rangle.$$

We now note another property of the inner product that $$\langle M\mathbf x,\mathbf y\rangle=(M\mathbf x)^T\mathbf y=\mathbf x^TM^T\mathbf y=\langle \mathbf x,M^T\mathbf y\rangle.$$ It follows then that $$\langle \mathbf x,\mathbf B^T\mathbf B(\mathbf B^T\mathbf B)^{-1}f(\mathbf B)\rangle=\langle \mathbf B\cdot\mathbf x,\mathbf B(\mathbf B^T\mathbf B)^{-1}f(\mathbf B)\rangle.$$

Thanks to @Daniel S, for noting a property of inner product: looking an inner product as product of a row vector and a column vector.

I just write it for clarity in the case someone is not familiar with basic mathematical concepts.

We look at vectors as column vectors (so $$\vec{v}^{T}$$ is a row vector). $$\mathbf{B}\in\mathbb{R}^{m\times n}$$, where $$m\geq n$$, is the basis of the lattice.

... since every linear function $$f:\mathcal{L}\rightarrow \mathbb{Z}$$ can be written as $$f_{\vec{v}}(\vec{y})=\langle\vec{v},\vec{y}\rangle$$

For $$\vec{y}_{m\times1}\in\mathcal{L(\mathbf{B}_{m\times n})}$$, we can write it based on the basis of the lattice: $$\exists\vec{x}\in\mathbb{Z}^{n}$$: $$\vec{y}=\mathbf{B}\vec{x}$$.

$$f(\vec{y})=f(\mathbf{B}\vec{x})=f(\sum_{i=1}^{n}x_{i}\vec{b}_{i})$$

Because when multiplying a column vector to basis matrix from right, it's equivalent to linear combinations of column vectors of the basis matrix. All the time, the first (second, ...) element of $$\vec{b}_{1}$$ ($$\vec{b}_{2},\ldots$$) multiplied by first (second, ...) element of $$\vec{x}$$.

$$=\sum_{i=1}^{n}x_{i}f(\vec{b}_{i})$$

because $$f$$ is linear.

$$=\langle\vec{x},[f(\vec{b}_{1},\ldots,f(\vec{b}_{n}))]^{T}\rangle$$

by looking at this serie as an inner product of two vectors. Note $$f:\mathcal{L}\rightarrow\mathbb{Z}$$, so $$f(\vec{b}_{i})\in\mathbb{Z}$$ and $$[f(\vec{b}_{1}),\ldots,f(\vec{b}_{n}))]\in\mathbb{Z}^{n}$$ is a vector.

$$=\vec{x}^{T}_{n\times1}\cdot\overrightarrow{f(\mathbf{B}_{m\times n})}_{n\times1}$$

by looking at inner product as product of a row vector and a column vector.

$$=\vec{x}^{T}_{n\times1}\mathbf{B}^{T}_{m\times n}\cdot(?)\overrightarrow{f(\mathbf{B})}_{n\times1}$$

trying to construct $$\mathbf{B}\vec{x}$$, the argument of $$f$$ at the first line.

$$=\vec{x}^{T}_{n\times1}\mathbf{B}^{T}\mathbf{B}_{m\times n}\cdot(\mathbf{B}^{T}\mathbf{B})^{-1}\overrightarrow{f(\mathbf{B})}_{n\times1}$$

$$\mathbf{B}\in\mathbb{R}^{m\times n}$$, where $$m\geq n$$ is a rectangular matrix; it doesn't have inverse. $$\mathbf{B}$$'s columns are basis vectors of the lattice, so are linearly independent. $$\Rightarrow$$ $$(\mathbf{B}^{T}\mathbf{B})_{n\times n}$$ has inverse (Note: $$(\mathbf{B}\mathbf{B}^{T})_{m\times m}$$ is not invertible).

$$=(\mathbf{B}\vec{x})^{T}_{m\times1}\cdot\underbrace{\left(\mathbf{B}_{m\times n}(\mathbf{B}^{T}\mathbf{B})^{-1}_{n\times n}\cdot\overrightarrow{f(\mathbf{B})}_{n\times 1}\right)}_{\vec{v}}$$

$$\vec{v}=\left(\mathbf{B}_{m\times n}(\mathbf{B}^{T}\mathbf{B})^{-1}_{n\times n}\cdot\overrightarrow{f(\mathbf{B})}_{n\times 1}\right)$$ is in the linear span of the lattice. Because $$f:\mathcal{L}\rightarrow\mathbb{Z}$$ and $$\mathbf{B}\in\mathbb{R}^{m\times n}$$, so $$\overrightarrow{f(\mathbf{B}_{m\times n})}\in\mathbb{Z}^{n}$$ $$\Rightarrow\vec{v}'=(\mathbf{B}^{T}\mathbf{B})^{-1}_{n\times n}\cdot\overrightarrow{f(\mathbf{B}_{m\times n})}_{n\times1}\in\mathbb{R}^{n}$$ $$\Rightarrow\vec{v}=\mathbf{B}_{m\times n}\cdot(\mathbf{B}^{T}\mathbf{B})^{-1}f(\mathbf{B})=\mathbf{B}_{m\times n}\cdot\vec{v}'_{n\times1}\in span_{\mathbb{R}}(\mathbf{B}_{m\times n})=\{\mathbf{B}_{m\times n}\vec{w}:\vec{w}\in\mathbb{R}^{n}\}$$.

$$=\langle\vec{y},\vec{v}\rangle$$

again by looking inner product as product of a row vector and a column vecror.

Finally, we've reached to the equality $$f(\vec{y})=\langle\vec{y},\vec{v}\rangle$$ for all $$\forall\vec{y}\in\mathcal{L}(\mathbf{B})$$ and some vector $$\vec{v}\in span_{\mathbb{R}}(\mathcal{L}(\mathbf{B}))=span_{\mathbb{R}}(\mathbf{B})$$ (because $$\mathbf{B}$$ is the basis of the lattice $$\mathcal{L}(\mathbf{B})$$, so $$span_{\mathbb{R}}(\mathcal{L}(\mathbf{B}))=span_{\mathbb{R}}(\mathbf{B})$$).

In other words, we can write a linear function $$f:\mathcal{L}\rightarrow\mathbb{Z}$$ as $$f(\vec{y})=f_{\vec{v}}(\vec{y})=\langle\vec{v},\vec{y}\rangle$$ for some $$\vec{v}\in span_{\mathbb{R}}(\mathbf{B})$$, i.e., represent it with a vector.

Now we substitute this representation in the natural definition of duality for lattices:

$$\left(\mathcal{L}(\mathbf{B})\right)^{*}=\{f:\mathcal{L}(\mathbf{B})\rightarrow\mathbb{Z} \ | \ f \ \text{is linear}\}=\{\vec{v}\in span_{\mathbb{R}}(\mathbf{B}): \langle\vec{v},\vec{y}\rangle\in\mathbb{Z},\forall\vec{y}\in\mathcal{L}(\mathbf{B})\}$$

As it was noted in Wikipedia, It should be emphasized that a lattice and its dual are fundamentally different kinds of objects; one consists of vectors in Euclidean space, and the other consists of a set of linear functionals on that space.