Unimodular transformation matrix of LLL algorithm

lattice

asked 2020-09-27 12:00:58 +0200

Santanu
21 ●1 ●1 ●2

updated 2020-09-27 14:16:54 +0200

slelievre
17654 ●22 ●160 ●348 http://carva.org/samue...

I also asked this question on sage-support.

I have a matrix M1 with integer entries with 90 rows and 6 columns. After applying the LLL algorithm to M1, I get M2 = M1.LLL(). I want to get the corresponding unimodular transformation matrix T such that T * M1 = M2.

We can find T by T = M2 * M1.pseudoinverse() or T = M1.solve_left(M2), but determinant of T becomes 0 i.e., T.det() equals 0. I want T.det() to equal 1.

edit retag flag offensive close merge delete

Comments

Providing this is the object of

Sage Trac ticket 25191: Add flag for returning LLL transformation matrix

In the meantime, explore fpylll to figure out how to do it.

slelievre ( 2020-09-27 15:28:57 +0200 )edit

add a comment

1 Answer

Sort by » oldest newest most voted

answered 2020-09-27 20:52:35 +0200

tmonteil
27323 ●31 ●202 ●514 http://wiki.sagemath.o...

updated 2020-09-27 20:52:59 +0200

Here is a workaround suggested by Martin Albrecht, the current developer of fpylll:

sage: from fpylll import *
sage: A = random_matrix(ZZ, 6, 90)
sage: U = IntegerMatrix.identity(6)
sage: B = LLL.reduction(IntegerMatrix.from_matrix(A), U).to_matrix(matrix(ZZ, 6, 90))
sage: U = U.to_matrix(matrix(ZZ, 6,6))
sage: B == U*A
True
sage: abs(U.det())
1

See this sage-devel thread

edit flag offensive delete link

Comments

The following import should be enough:

from fpylll import (IntegerMatrix, LLL)

slelievre ( 2020-09-27 23:09:40 +0200 )edit

add a comment

Your Answer

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

Add Answer

Question Tools

1 follower

Stats

Asked: 2020-09-27 12:00:58 +0200

Seen: 584 times

Last updated: Sep 27 '20

Unimodular transformation matrix of LLL algorithm edit

Comments

1 Answer

Comments