0
$\begingroup$
l1 = {{-6327, 0, -2109}, {131, 0, -131}, {-6840, 0, 24929}};
LatticeReduce[l1]]

returns

{{1,0,0},{0,0,1}}.

How do I find the (probably not unique) $2\times 3$ integer matrix n such that

n.l1 == {{1,0,0},{0,0,1}}

Discussions in the literature of LLL reduction all seem to be for the linearly independent basis case. What does LatticeReduce do with a linearly dependent basis and is there any good discussion of this case in the published literature?

Thanks for the illuminating reply Daniel. Just to make sure I understand correctly here is how I would answer my original question using just the regular functions LatticeReduce & HermiteDecomposition.

Given a rank 2 basis in 3 dimensions

l1 = {{21, 22, -43}, {11, -13, 17}, {182, 19, -96}}

b1 = LatticeReduce[l1] = {{11, -13, 17}, {-32, -9, 26}}

If I want to find n2 that satisfies

b1 = n2.l1

I let

l2 = HermiteDecomposition[l1] = {{{-1, 2, 0}, {11, -21, 0}, {-5, -7, 1}}, {{1, -48, 77}, {0, 515, -830}, {0, 0, 0}}}

and then solve n1.l2[[2, 1;;2]] = b1, or

n1 = Transpose[LinearSolve[b1.Transpose[l2[[2, 1;;2]]], b1.Transpose[b1]]] = {{11, 1}, {-32, -3}}

or

{u,w,v} = SingularValueDecomposition[l2[[2, 1 ;; 2]]]//N

n1 = b1.v.{{1/w[[1, 1]], 0}, {0, 1/w[[2, 2]]}, {0, 0}}.Transpose[u] = 
{{11., 1.}, {-32., -3.}}

and then

n2 = n1.l2[[1, 1;;2]] = {{0, 1, 0}, {-1, -1, 0}}.

$\endgroup$
  • $\begingroup$ (1) LatticeReduce checks for independence and, if there are dependencies, preprocesses with HermiteDecomposition. $\endgroup$ – Daniel Lichtblau Dec 19 '15 at 21:11
  • $\begingroup$ (2) There is an undocumented LinearAlgebra`ExtendedLatticeReduce which returns the multiplier matrix and reduced lattice. Unfortunately, due to a bug in the code (just noticed with this example), it only gives the multiplier matrix needed for handling the Hermite form vectors, not the full one that would arise from also using the HermiteDecomposition multiplier matrix. I need to fix that. $\endgroup$ – Daniel Lichtblau Dec 19 '15 at 21:14
  • $\begingroup$ The method above looks good. I think I prefer LinearSolve to SVD though. The latter is either prone to bogging down (in exact arithmetic) or requiring a some trial and error on precision (approximate arithmetic) to recover correctly all integers. $\endgroup$ – Daniel Lichtblau Dec 22 '15 at 15:21
  • $\begingroup$ Another method that is used is to give the lattice a "large" multiplier, then augment on the right or left with an identity matrix. It will have full rank and the reduced form will be a good approximation to the reduction of the original. One recovers the multipliers from the augmented part (the idea is identical to what is often taught for matrix inversion). Also remember to divide out the original multiplier from the original part to get the actual reduced form. $\endgroup$ – Daniel Lichtblau Dec 22 '15 at 15:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.