Description
This function is provided by the package
LLLBases. If the optional argument
ChangeMatrix=>true is given, then the output is a pair of matrices: the first is the LLL matrix as above, and the second is the change of basis matrix from the original basis to the new basis.
In this example, we compute the LLL basis of the nullspace of a matrix. This is an example of Havas et al.
i1 : m1 = map(ZZ^10, ZZ^10, (j,i) -> (i+1)^3 * (j+1)^2 + i + j + 2)
o1 = | 3 11 31 69 131 223 351 521 739 1011 |
| 7 36 113 262 507 872 1381 2058 2927 4012 |
| 13 77 249 583 1133 1953 3097 4619 6573 9013 |
| 21 134 439 1032 2009 3466 5499 8204 11677 16014 |
| 31 207 683 1609 3135 5411 8587 12813 18239 25015 |
| 43 296 981 2314 4511 7788 12361 18446 26259 36016 |
| 57 401 1333 3147 6137 10597 16821 25103 35737 49017 |
| 73 522 1739 4108 8013 13838 21967 32784 46673 64018 |
| 91 659 2199 5197 10139 17511 27799 41489 59067 81019 |
| 111 812 2713 6414 12515 21616 34317 51218 72919 100020 |
10 10
o1 : Matrix ZZ <-- ZZ
|
i2 : m = syz m1
o2 = | -3 -1632481 -2819632 -4476373 -6680969 -9511685 -13046786 |
| 8 4353284 7519023 11937004 17815934 25364520 34791469 |
| -7 -3809126 -6579152 -10444892 -15588965 -22193990 -30442586 |
| 2 1088324 1879762 2984262 4454001 6341156 8697904 |
| 0 -1 0 0 0 0 0 |
| 0 0 -1 0 0 0 0 |
| 0 0 0 -1 0 0 0 |
| 0 0 0 0 -1 0 0 |
| 0 0 0 0 0 -1 0 |
| 0 0 0 0 0 0 -1 |
10 7
o2 : Matrix ZZ <-- ZZ
|
i3 : LLL m
o3 = | 1 0 1 0 1 1 1 |
| -1 1 0 1 0 -1 -2 |
| -1 -1 -1 -2 -2 0 1 |
| 0 -1 -1 0 1 -1 1 |
| 2 1 -1 1 -1 1 -2 |
| -1 -1 2 1 1 0 0 |
| 0 2 0 0 -1 0 2 |
| 0 -1 1 -2 1 -1 -1 |
| 0 0 -1 1 1 2 0 |
| 0 0 0 0 -1 -1 0 |
10 7
o3 : Matrix ZZ <-- ZZ
|
It is also possible to get the change of basis matrix from the original basis to the LLL basis. For example,
i4 : (n,c) = LLL(m, Strategy => NTL, ChangeMatrix=>true)
o4 = (| 1 0 1 0 1 1 1 |, | 148443 361542 392022 200620 -47785 309365
| -1 1 0 1 0 -1 -2 | | -2 -1 1 -1 1 -1
| -1 -1 -1 -2 -2 0 1 | | 1 1 -2 -1 -1 0
| 0 -1 -1 0 1 -1 1 | | 0 -2 0 0 1 0
| 2 1 -1 1 -1 1 -2 | | 0 1 -1 2 -1 1
| -1 -1 2 1 1 0 0 | | 0 0 1 -1 -1 -2
| 0 2 0 0 -1 0 2 | | 0 0 0 0 1 1
| 0 -1 1 -2 1 -1 -1 |
| 0 0 -1 1 1 2 0 |
| 0 0 0 0 -1 -1 0 |
------------------------------------------------------------------------
-331062 |)
2 |
0 |
-2 |
1 |
0 |
0 |
o4 : Sequence
|
i5 : m * c == n
o5 = true
|