Unimodular transformation matrix of LLL algorithm

lattice

asked 4 years ago

Santanu
21 ●1 ●1 ●2

updated 4 years ago

slelievre
17789 ●22 ●163 ●352 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.

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 ( 4 years ago )

add a comment

1 Answer

Sort by » oldest newest most voted

answered 4 years ago

tmonteil
27483 ●32 ●205 ●519 http://wiki.sagemath.o...

updated 4 years ago

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

link

Comments

The following import should be enough:

from fpylll import (IntegerMatrix, LLL)

slelievre ( 4 years ago )

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: 4 years ago

Seen: 782 times

Last updated: Sep 27 '20

Unimodular transformation matrix of LLL algorithm savecancel

Comments

1 Answer

Comments