Sufficiency of $T_{i,j}^\lambda$ Matrices

As defined above, a basis B is S-reduced if and only if its associated quadratic form A satisfies:

$$S(A) \leq S(T^t \;A \;T), \quad\text{for } T \in SL_n({\Bbb Z}).$$ (2.4)

Thus, in order to Seysen-reduce a given lattice L which we know has basis B, we need to find a transformation matrix $T \in SL_n({\Bbb Z})$ such that for all other $T' \in SL_n({\Bbb Z})$ we have $S(T^t \;A \;T) \leq S((T')^t \;A \;T')$. As $SL_n({\Bbb Z})$ is the set of all $n \times n$ matrices of unit determinant, we suspect that it is computationally difficult to find the desired matrix T directly. However, there are ways to avoid having to compute matrix T directly. Specifically, we can restrict our attention to a set of generating matrices for $SL_n({\Bbb Z})$, as we show below. Initially, let us assume that n = 2 and that A is the quadratic form associated with a lattice basis we wish to reduce. $SL_2({\Bbb Z})$ thus contains all $2 \times 2$ matrices $\left[ \begin{smallmatrix}a & b \\ c & d\\ \end{smallmatrix} \right]$ with ad - bc = 1. Now, it is known [2,37] that the set G₂ is a set of generating matrices for $SL_2({\Bbb Z})$, where:

$$G_2 = \left\{ \begin{bmatrix}1 & \lambda \\ 0 & 1 \end{bmatri... ...ambda & 1 \end{bmatrix} \colon \lambda \in {\Bbb Z}\right\}$$

That is, if $T \in G_2$, then there exists a sequence of matrices $T_1,T_2,\ldots{},T_k$ such that

$$T = T_1 \;T_2 \;\cdots T_k, \; T_i \in G_2 \quad\text{for } 1 \leq i \leq k.$$

(Actually, the set $\left\{ \left[ \begin{smallmatrix}1 & \lambda \\ 0 & 1 \end{smallmatrix} \righ... ...\\ \lambda & 1 \end{smallmatrix}\right] \colon \lambda \in \{-1,0,1\} \right\}$ is sufficient, since
$$\begin{align*}\begin{bmatrix}1 & \pm 1 \\ 0 & 1 \end{bmatrix}^\lambda & = \begi... ...lambda & = \begin{bmatrix}1 & 0 \\ \pm \lambda & 1 \end{bmatrix}. \end{align*}$$
Section 2.2.2 below discusses the performance of Seysen's algorithm when we restrict $\lambda = \pm 1$.) Notice that the matrices $\left[ \begin{smallmatrix}1 & \lambda \\ 0 & 1\\ \end{smallmatrix} \right]$ and $\left[ \begin{smallmatrix}1 & 0 \\ \lambda & 1\\ \end{smallmatrix} \right]$ describe all possible row moves which can be performed on a $2 \times 2$ matrix. As an example, note that the matrix $S_0 = \left[ \begin{smallmatrix}0 & 1 \\ -1 & 0\\ \end{smallmatrix} \right]$ is generated by:

$$S_0 = \begin{bmatrix}1 & 0 \\ -1 & 1 \end{bmatrix} \;\begin{b... ...end{bmatrix} \;\begin{bmatrix}1 & 0 \\ -1 & 1 \end{bmatrix}.$$

(S₀ corresponds to swapping the two rows in a matrix.) Thus, the set of matrices $T_{i,j}^\lambda$ for $n = 2, i \neq j$ is exactly a set of generating matrices for $SL_2({\Bbb Z})$. Therefore, it is sufficient for n = 2 for Seysen's algorithm to consider only products of matrices of the form $T_{i,j}^\lambda$. The difficulty is in choosing the right matrices and the right order of operations. Our analysis above assumed n = 2, but similar results are known where n is an arbitrary integer [30]. For fixed n > 0,

$$G_n = I_n \bigcup \left\{ \bigcup\begin{Sb}1 \leq i,j \leq n ... ... j\end{Sb} \left\{ T_{i,j}^1, T_{i,j}^{-1} \right\} \right\}$$

is a set of generating matrices for $SL_n({\Bbb Z})$. Thus, it would be sufficient for Seysen's algorithm to consider only T_i,j¹ and T_i,j^-1 transformation matrices if it could pick the proper triples $(i,j,\pm 1)$ at every step. In practice, Seysen's algorithm chooses triples $(i,j,\lambda)$ where $\lambda \in {\Bbb Z}$, but the basic problem is still choosing the right triples in the right order. Choosing the correct (i,j) pairs to reduce and the value of $\lambda$ for that pair are discussed below.