### 15.3.11 Short basis of a lattice

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

- lll takes 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 LO=S.

#### Examples

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

⎡
⎢
⎣

−1 | 1
2 | 1

⎤
⎥
⎦

,

⎡
⎢
⎣

−1 | 1
1 | 0

⎤
⎥
⎦

,

⎡
⎢
⎢
⎢
⎢
⎣

1 | 0

−

1
2

1

⎤
⎥
⎥
⎥
⎥
⎦

,

⎡
⎢
⎢
⎢
⎢
⎣

−1 | 1

3
2

3
2

⎤
⎥
⎥
⎥
⎥
⎦

So the original basis is v1=[2,1], v2=[1,2] and the short basis is w1=[−1,1], w2=[2,1]. Since w1=−v1+v2 and w2=v1 then AM=S and LO=S.

As another example, input:

M:=[[3,2,1],[1,2,3],[2,3,1]]:; S,A,L,O:=lll(M)

⎡
⎢
⎢
⎣

−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

⎤
⎥
⎥
⎦

Properties: AM=S and LO=S.