Ask Your Question
0

Matrix transformation of a LLL reduced basis

asked 2019-10-03 11:39:10 +0200

A.Cio gravatar image

Dear Sage Community,

I am trying the way to obtain the matrix transformation of a LLL reduced basis, that is a matrix that gives the expression of the new lattice basis in terms of the old.

In particular, I have a matrix X and the LLL reduced base Y (obtain by the LLL function of Sage: Y=X.LLL()) and I want a matrix T such that TX=Y.

I try to solve the problem using solve.left() but the result is different from Magma. With a matrix X=[5 2] [1 4] [2 3],

the T matrix in Sage is [ 0 0 0] [ 2/9 -1/9 0] [ 1/18 -5/18 0] while in Magma is [ -3 -6 10] [ -3 -7 11] [ -5 -11 18]

Please could anyone help me to understand a way to have in SAGE the same result of Magma?

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
0

answered 2019-10-03 17:13:20 +0200

tmonteil gravatar image

updated 2019-10-03 17:13:52 +0200

Because you matrices are not square (hence not invertible), there may be many solutions, and given each propositions, you can actually check that the wanted equality holds. I am not sure about you actual problems, but you can have a look at the pseudoinverse method:

sage: X = matrix(ZZ, [[5,2],[1,4],[2,3]]) ; X
[5 2]
[1 4]
[2 3]
sage: Y = X.LLL() ; Y
[ 0  0]
[ 1  0]
[ 0 -1]
sage: T = Y*X.pseudoinverse() ; T
[      0       0       0]
[  21/94 -51/470  -1/235]
[   4/47  -10/47   -5/47]

You can check:

sage: T*X == Y
True
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2019-10-03 11:39:10 +0200

Seen: 993 times

Last updated: Oct 03 '19