Theoretical background

Lattice are manipulated in Polylib because they are used in constructing ${{\cal Z}}$-polyhedra. A subset $L$ in ${{Q}}^n$ is a lattice if is generated by integral combination of finitely many vectors: $a_{1},\cdots,a_{n}$ ($a_i \in {Q}^n$).

$$L=L(a_{1},\cdots,a_{n})=\{\lambda_{1}a_{1}+\cdots + \lambda_{n}a_{n}\vert\lambda_{1},\cdots,\lambda_{n}\in setZ\}$$

If the $a_i$ vectors have integral coordinates, $L$ is an integer lattice. If the $a_i$ vectors are linearly independent, they constitute a basis of the lattice. If the vectors $(a_{1},\cdots,a_{n})$ constitute a basis of ${Q}^n$, the lattice is said to be full dimensional.

The affine object corresponding to a lattice is called an affine lattice. It is constructed by adding the same constant vectors to all the points of a lattice. For instance, the set $L_1 = \{2i+1, 3j+5\ \vert\ i,j \in {\cal Z}\}$ can be interpreted as an affine lattice: it is the lattice defined by any integral linear combinations of the vectors $(2,0)$ and $(0, 3)$, plus the vector $(1,5)$

$$L_1 = \left\{i\left(\begin{array}{c} 2 \\ 0 \end{array}\right... ... 1 \\ 5 \end{array}\right) \ \vert\ i,j\in {\cal Z} \right\}.$$

In Polylib, only full-dimensionnal affine integral lattices are considered. It can easily be proven that an element of this subset of affine lattices can always be represented by a non singular integral matrix and an integral vector. For instance, lattice $L_1$ above, will be mathematically represented by:

$$L_1 = \left( \left (\begin{array}{cc} 2 & 0 \\ 0 & 3 \end{ar... ...ht), \left( \begin{array}{c} 1 \\ 5 \end{array}\right) \right)$$

The data structure used to represent an affine lattice in Polylib is an affine matrix. For example, lattice $L_1$ will be represented in Polylib by the following matrix:

$$L_1 = \left (\begin{array}{ccc} 2 & 0 & 1\\ 0 & 3 & 5 \\ 0 & 0 & 1 \end{array}\right)$$

Lattice manipulation naturally leads to an intensive use of the Hermite normal form (HNF).

Definition 3 (Hermite normal form)   A matrix $A$ of full row rank is said to be in Hermite normal form (HNF) if it has the form $[B \ 0]$ where $B$ is a non singular, lower triangular, non negative matrix, in which each row has a unique maximum entry located on the main diagonal of $B$.

Theorem 1   For any rational matrix $A$ of full row rank, there exists a unique matrix $B$ in Hermite normal form and a unimodular matrix $U$ such that $A=BU$.

Consider the following matrices $A$, $B$ and $U$. Then $BU$ is the Hermite decomposition of $A$.

$$A = \left( \begin{array}{ccc} 1 & 2 & 3 \\ -3 & 2 & 0 \\ 1... ... 1 & 2 & 3 \\ -3 & 2 & 0 \\ 2 & -3 & -2 \end {array} \right)$$

Proposition 3   (uniqueness of the Hermite normal form) Let $A$ and $A'$ be rational matrices of full row rank, with Hermite normal forms $[B \ 0]$ and $[B' \ 0]$ , respectively. Then the columns of $A$ generate the same lattice as those of $A'$, if and only if $B=B'$.

In other words, two lattices are equal if and only if their respective matrices have the same Hermite normal form.

Proposition 4   (lattice canonical form) Given a full-dimensional linear lattice $L$, there exists a unique representation $(H,0)$ of $L$ (i.e. $L= \{ x~\vert~x=Hy,\ y \in Z^n \}$), such that $H$ is in Hermite normal form.

Proposition 5   (affine lattice canonical form) Given a full dimensional affine lattice $L$, there exists a unique representation $(H,h)$ of $L$ (i.e. $L= \{ x~\vert~x=Hy+h,\ y \in {\cal Z}^n \}$), such that $H$ is in Hermite normal form and $0\leq h_i <H_{ii}, \ 1\leq i \leq n$.

For instance, consider the following lattice $L$:

$$L = \left(\left ( \begin{array}{cc} 0 & 1 \\ 4 & 0 \end{arra... ... \right) \right) =\{j+5, 4i+7\ \vert\ i,j \in {\cal Z}\} \quad,$$

its unique canonical form is

$$L = \left (\left ( \begin{array}{ccc} 1 & 0 \\ 0 & 4 \end{ar... ...eft( \begin{array}{c} 0 \\ 3 \end{array} \right) \right)\quad.$$

Polylib can also handle unions of (affine integral full dimensionnal) lattices. This provides a set of objects which is closed under union, intersection, image by invertible integral functions (see [NRi00]).

For instance, consider the following lattice $L$:

$$L = \left(\left ( \begin{array}{cc} 0 & 1 \\ 4 & 0 \end{arra... ... \right) \right) =\{j+5, 4i+7\ \vert\ i,j \in {\cal Z}\} \quad,$$

its unique normal form is

$$L = \left (\left ( \begin{array}{ccc} 1 & 0 \\ 0 & 4 \end{ar... ...eft( \begin{array}{c} 0 \\ 3 \end{array} \right) \right)\quad.$$