Ask Your Question
1

Unimodular transformation matrix of LLL algorithm

asked 2020-09-27 05:00:58 -0500

Santanu gravatar image

updated 2020-09-27 07:16:54 -0500

slelievre gravatar image

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

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

slelievre gravatar imageslelievre ( 2020-09-27 08:28:57 -0500 )edit

1 answer

Sort by ยป oldest newest most voted
1

answered 2020-09-27 13:52:35 -0500

tmonteil gravatar image

updated 2020-09-27 13:52:59 -0500

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 more

Comments

The following import should be enough:

from fpylll import (IntegerMatrix, LLL)
slelievre gravatar imageslelievre ( 2020-09-27 16:09:40 -0500 )edit

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 05:00:58 -0500

Seen: 68 times

Last updated: Sep 27