6.49.9  Short basis of a lattice: lll

The lll command finds a short basis for the ℤ-modules generated by the rows of a matrix.

• lll takes one argument:
  M, an invertible matrix with integer coefficients.
• lll(M) returns the sequence (S,A,L,O) where:
  • the rows of S is a short basis of the ℤ-module generated by the rows of M,
  • A is the change-of-basis matrix from the short basis to the basis defined by the rows of M (AM=S),
  • L is a lower triangular matrix, the modulus of its non diagonal coefficients are less than 1/2,
  • O is a matrix with orthogonal rows such that L*O=S.

Examples.

• Input:
  (S,A,L,O):=lll(M:=[[2,1],[1,2]])
  Output:

  ⎡ ⎢ ⎣

  −1 1 2 1

  ⎤ ⎥ ⎦

  ,

  ⎡ ⎢ ⎣

  −1 1 1 0

  ⎤ ⎥ ⎦

  ,

  ⎡ ⎢ ⎢ ⎢ ⎢ ⎣

  1 0 − 1 2 1

  ⎤ ⎥ ⎥ ⎥ ⎥ ⎦

  ,

  ⎡ ⎢ ⎢ ⎢ ⎢ ⎣

  −1 1 3 2 3 2

  ⎤ ⎥ ⎥ ⎥ ⎥ ⎦

  [[-1,1],[2,1]], [[-1,1],[1,0]], [[1,0],[1/-2,1]], [[-1,1],[3/2,3/2]]
  Hence:

  S =  ⎡ ⎢ ⎣ −1 1 2 1 ⎤ ⎥ ⎦                   A =  ⎡ ⎢ ⎣ −1 1 1 0 ⎤ ⎥ ⎦                   L =  ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ 1 0 − 1 2 1 ⎤ ⎥ ⎥ ⎥ ⎥ ⎦                   O =  ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ −1 1 3 2 3 2 ⎤ ⎥ ⎥ ⎥ ⎥ ⎦

  So the original basis is v₁=[2,1], v₂=[1,2] and the short basis is w₁=[−1,1], w₂=[2,1]. Since w₁=−v₁+v₂ and w₂=v₁ then AM=S LO=S.
• Input:

  M := [[3,2,1],[1,2,3],[2,3,1]]:;

  (S,A,L,O):=lll(M)

  Output:

  ⎡ ⎢ ⎢ ⎣

  −1 1 0 −1 −1 2 3 2 1

  ⎤ ⎥ ⎥ ⎦

  ,

  ⎡ ⎢ ⎢ ⎣

  −1 0 1 0 1 −1 1 0 0

  ⎤ ⎥ ⎥ ⎦

  ,

  ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣

  1 0 0 0 1 0 − 1 2 − 1 2 1

  ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦

  ,

  ⎡ ⎢ ⎢ ⎣

  −1 1 0 −1 −1 2 2 2 2

  ⎤ ⎥ ⎥ ⎦

  so

  S =  ⎡ ⎢ ⎢ ⎣ −1 1 0 −1 −1 2 3 2 1 ⎤ ⎥ ⎥ ⎦                   A =  ⎡ ⎢ ⎢ ⎣ −1 0 1 0 1 −1 1 0 0 ⎤ ⎥ ⎥ ⎦                   L =  ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ 1 0 0 0 1 0 − 1 2 − 1 2 1 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦                   O =  ⎡ ⎢ ⎢ ⎣ −1 1 0 −1 −1 2 2 2 2 ⎤ ⎥ ⎥ ⎦

  Properties:
  AM=S and LO=S.