General n-vector Row Operations

Section 2.3.1 above discussed the possibility of extending Seysen's algorithm to consider row operations involving three and four vectors at once. It is possible to extend these operations to encompass arbitrary k-moves where integer multiples of k-1 basis vectors are added to another basis vector. For fixed k, let $\bold{b_j}$ be the target basis vector (the vector to be modified) and let $\bold{b_{i_1}},\ldots{},\bold{b_{i_{k-1}}}$ be the basis vectors to be added to $\bold{b_i}$ in multiples of $\lambda_1,\ldots{},\lambda_{k-1}$ respectively. Then, after the row move, we will have:
$$\begin{align*}\bold{b_j} & \leftarrow \bold{b_j} + \sum_{m=1}^{k-1} \lambda_m \... ...^*} - \lambda_m \bold{b_j^*}, \quad\text{for } 1 \leq m \leq k-1. \end{align*}$$
Now, we may solve for the new values of the quadratic forms A and A^* after the row move has occurred. In A, the only value that changes is a_j,j. Its new value is:

$$a_{j,j} \leftarrow a_{j,j} + \left( \sum_{m=1}^{k-1} a_{i_m,i... ...\ m \neq p \end{Sb}^{k-1} 2 \lambda_m \lambda_p a_{i_m,i_p}.$$ (2.14)

In the dual lattice quadratic form A^*, the values a_im,im^* change for $1 \leq m \leq k-1$. Their new values are:

$$a_{i_m,i_m}^* \leftarrow a_{i_m,i_m}^* - 2 \lambda_m a_{i_m,j... ...+ \lambda_m^2 a_{j,j}^*, \quad\text{for } 1 \leq m \leq k-1.$$ (2.15)

If we compute $\Delta$, the change in S(A) resulting from this row move, we find that:
$$\begin{align}\begin{split} \Delta & = a_{j,j}^* \left( \left( \sum_{m=1}^{k-1} ... ...{Sb}^{k-1} \lambda_m \lambda_p a_{i_m,i_p} a_{j,j}^*. \end{split} \end{align}$$
Thus, for all $1 \leq m \leq k-1$ we have:

$$\frac{\partial}{\partial \lambda_m} \Delta = 4 \lambda_m a_{i... ... \\ p \neq m\end{Sb}^{k-1} \lambda_p a_{i_m,i_p} a_{i,i}^*.$$ (2.16)

We may thus compute formulae for all $\lambda_m$ for $1 \leq m \leq k-1$ if we solve the simultaneous system of equations obtained by setting the k-1 derivatives defined in Equation 2.21 equal to zero. Of course, we still must solve the problem of finding optimal integer values for the $\lambda_m$. For the 2-move case we showed that $\lceil \lambda_r \rfloor$ was the best integer choice for $\lambda$. It is not clear that rounding will work in the k-move case. The real values derived for the $\lambda_m$ may only indicate some range of integer values which need to be searched.