Smith decomposition

Theorem 2   Smith Decomposition. If $A$ is an $n \times n$ non-singular integer matrix, there exist unimodular matrices $U$ and $V$ such that:

$$\begin{array}{rl} i. & UAV = \Delta\\ ii. & \Delta\ is\ a\ ... ...a_{1}\ \vert\ \delta_{2}\ \ldots\ \vert\ \delta_{n} \end{array}$$

$\Delta$ is unique and is called the Smith normal form of $A$.

For example, consider the matrix:

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

Its Smith normal decomposition is: $UMV=\Delta$ where:

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

In [NRi00], and affine smith normal form has been defined for affine matrices. The corresponding function in Polylib is:

void AffineSmith (Lattice *A, Lattice **U, Lattice **V, Lattice **Diag)

: compute the Smith normal form of a matrix