Using Hadamard Matrices to Permute Lattice Bases

Our third and last suggestion for moving lattice bases out of local minima was suggested by Matthijs Coster (personal communication). Instead of randomly permuting the lattice basis as random quenching does, Coster suggests using a Hadamard matrix H to transform a Seysen-reduced lattice basis B into lattice basis $B' = B \;H$. Recall that matrix H is a Hadamard matrix if it satisfies the following two properties:

1.

Each entry h_i,j of H is either +1 or -1.

2.

If $\bold{h_1},\ldots{},\bold{h_n}$ are the rows of H, then for all i,j with $i \neq j$, $(\bold{h_i},\bold{h_j}) = 0$.

It is not difficult to show that if H is an $n \times n$ Hadamard matrix, then n = 2 or $n \equiv 0 \bmod 4$ ([1], 2.21 Exercise 10). Now, consider the lattice basis B' obtained by multiplying B by a Hadamard matrix H. (If $n \not\equiv 0 \bmod 4$ we may consider B and the corresponding lattice L to be sublattices of an n'-dimension space with $n' > n, n' \equiv 0 \bmod 4$.) Each basis vector in B' is a linear combination of all the basis vectors in B, but no two B' vectors have similar constructions, since $\bold{h_i}$ and $\bold{h_j}$ differ in $\tfrac{1}{2}n$ coordinates if $i \neq j$. The basis vectors in B' will have lengths $\approx \sqrt{n}$ times the lengths of the basis vectors in B, so while we obtain a good randomization of the lattice, the lengths of the basis vectors are still manageable. We should point out that the matrix H is not a linear transformation matrix; $\det(H) \neq 1$. This means that the lattice generated by B is not the same lattice generated by B'. However, all n-dimensional Hadamard matrices H_n satisfy:

$$H_n \;H_n^t = n \;I_n.$$

Thus,

$$B \;H_n \;H_n^t = n \;B$$

and the net result of the operation is to scale B (and the associated lattice L) by a factor of n. Thus we can divide out the factor of n and we are left with the lattice L we started with. So, our plan of attack should be as follows. When Seysen's algorithm stops and reports that lattice basis B is a local minimum of S(A), create $B' = B \;H$ where H is a Hadamard matrix. Now, Seysen-reduce lattice basis B' until a local minimum is reached. Then compute $B'' = \tfrac{1}{n} B' H_n^t$. Finally, Seysen-reduce basis B'', producing basis B'''. Bases B and B''' describe the same lattice L. Note that there is no guarantee that S(A''') < S(A), where A,A''' and the quadratic forms associated with B,B''' respectively. Further study is required before we may conclude whether Hadamard permutations provide a reasonable method for ``kicking'' lattice basis B.