Lattice Reduction in Mathematica

Question

I have some trouble understanding the concept of lattice reduction. As I understand, an integer lattice $$\{ A k : k \in \mathbb{Z}^n \} \subset \mathbb{Z}^n $$ is defined by a regular matrix $A \in \mathbb{Z}^{n \times n}$.

Two matrices $A$ and $B$ generate the same lattice if there exist $R \in \mathbb{Z}^{n \times n}$ such that $$A = B R.$$

Now I try the following in Mathematica with the function

A = {{1, 0, 1345}, {1, 0, 35}, {0, 1, 154}}

B = LatticeReduce[A]

yields $$ B= \left( \begin{array}{ccc} 9 & -2 & 7 \\ -2 & -8 & 8 \\ -2 & 9 & 6 \\ \end{array} \right) $$

Now, I expect $B^{-1} A \in \mathbb{Z}^{3 \times 3}$. However, R = Inverse[B].A yields $$ R=\left( \begin{array}{ccc} \frac{9}{262} & -\frac{4}{131} & \frac{233}{2} \\ -\frac{32}{655} & \frac{43}{655} & \frac{62}{5} \\ \frac{111}{1310} & \frac{38}{655} & \frac{459}{10} \\ \end{array} \right) $$

What did I do wrong? Thanks!

Answer 1

EXTRA: Alright, Mathematica works with the rows as generating vectors. A vector in their lattice will be $k A,$ where $k$ is a row vector of integers. Try $k = (1,0,0)$ and see what happens. This means that reduction follows the recipe $A = LB,$ so that $L = A B^{-1}.$

? opa = a
%16 = 
[1 0 1345]

[1 0 35]

[0 1 154]

? opb = [ 9,-2,7; -2,-8,8; -2,9,6]
%17 = 
[9 -2 7]

[-2 -8 8]

[-2 9 6]

? matdet(opb)
%18 = -1310

? opbinv = - matadjoint(opb) / 1310
%19 = 
[12/131 -15/262 -4/131]

[2/655 -34/655 43/655]

[17/655 77/1310 38/655]


? L =  opa * opbinv
%21 = 
[35 79 78]

[1 2 2]

[4 9 9]

ORIGINAL: You have not been clear about rows and columns. We usually talk about the lattice generated by the columns of $A,$ that is what your definition says. Here is a satisfactory calculation from gp-pari that results in the transpose (well, permuted with $\pm$ signs) of your $B.$ I have no way of knowing how that compares with Mathematica. Note that there is a problem if we just take transposes, as $(AT)^t = T^t A^t,$ so the order becomes incorrect.

qflll(x,{flag = 0})

LLL algorithm applied to the columns of the matrix x. The columns of x may be linearly dependent. The result is a unimodular transformation matrix T such that x .T is an LLL-reduced basis of the lattice generated by the column vectors of x.

aa = [1,1,0; 0,0,1; 1345,35,154]
%1 = 
[1 1 0]

[0 0 1]

[1345 35 154]

? matdet(aa)
%2 = 1310


? aat = qflll(aa)
%13 = 
[1 0 -1]

[-3 9 -1]

[-8 -2 9]

? aared = aa * aat
%14 = 
[-2 9 -2]

[-8 -2 9]

[8 7 6]

? 
? 
? matdet(aat)
%15 = 1
?