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.

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

⎡
⎢
⎣

−1	1
2	1

⎤
⎥
⎦

⎡
⎢
⎣

−1	1
1	0

⎤
⎥
⎦

⎡
⎢
⎢
⎢
⎢
⎣

−

⎤
⎥
⎥
⎥
⎥
⎦

⎡
⎢
⎢
⎢
⎢
⎣

−1

⎤
⎥
⎥
⎥
⎥
⎦

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

As another example, input:

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

⎡
⎢
⎢
⎣

⎤
⎥
⎥
⎦

⎡
⎢
⎢
⎣

⎤
⎥
⎥
⎦

⎡
⎢
⎢
⎢
⎢
⎢
⎣

−

⎤
⎥
⎥
⎥
⎥
⎥
⎦

⎡
⎢
⎢
⎣

⎤
⎥
⎥
⎦

Properties: AM=S and LO=S.