suivant: Quadratic forms monter: Matrix factorizations précédent: Singular value decomposition :   Table des matières   Index

## Short basis of a lattice : lll

lll takes as argument an invertible matrix M with integer coefficients.
lll returns (S, A, L, O) such that:
• 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 (A*M = S),
• L is a lower triangular matrix, the modulus of it's non diagonal coefficients are less than 1/2,
• O is a matrix with orthogonal rows such that L*O = S.
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]]
Hence :
S=[[-1,1],[2,1]]
A=[[-1,1],[1,0]]
L=[[1,0],[1/-2,1]]
O=[[-1,1],[3/2,3/2]]
Hence 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 :
A:=[[-1,1],[1,0]], A*M==S and L*O==S.
Input :
(S,A,L,O):=lll([[3,2,1],[1,2,3],[2,3,1]])
Output :
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]]
Input :
M:=[[3,2,1],[1,2,3],[2,3,1]]
Properties :
A*M==S and L*O==S

suivant: Quadratic forms monter: Matrix factorizations précédent: Singular value decomposition :   Table des matières   Index
giac documentation written by Renée De Graeve and Bernard Parisse