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 264648963742163 -5720194896614938149 196290847034331948723461
| 8 -705730569979100 15253853057639806247 -523442258758217541061987
| -7 617514248731710 -13347121425434776433 458011976413438494260267
| 2 -176432642494772 3813463264409886720 -130860564689552160194102
| 0 -1 21616 -741761955
| 0 0 -1 34317
| 0 0 0 -1
| 0 0 0 0
| 0 0 0 0
| 0 0 0 0
------------------------------------------------------------------------
-10053331640015906467212478543 733064576943136582501759958326999
26808884373375699932906739118 -1954838871848360526997313580179474
-23457773826703642477234348613 1710484012867308536573627860523869
6702221093343811022840899589 -488709717962081822034202577795737
37990456734120 -2770172027631443820
-1757596888 128159705187668
51218 -3734692423
-1 72919
0 -1
0 0
------------------------------------------------------------------------
-73320113471254325003809576801404806297 |
195520302590011163973959639684930937765 |
-171080264766259075893319671817970920665 |
48880075647501959867181120921053624538 |
277068806472403333000800 |
-12818357921462101920 |
373538813424120 |
-7293258360 |
100020 |
-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 |, | -24064763942356 -58611163497565
| -1 1 0 1 0 -1 -2 | | 21614 4199
| -1 -1 -1 -2 -2 0 1 | | 1 -17415
| 0 -1 -1 0 1 -1 1 | | 0 51216
| 2 1 -1 1 -1 1 -2 | | 0 1
| -1 -1 2 1 1 0 0 | | 0 0
| 0 2 0 0 -1 0 2 | | 0 0
| 0 -1 1 -2 1 -1 -1 |
| 0 0 -1 1 1 2 0 |
| 0 0 0 0 -1 -1 0 |
------------------------------------------------------------------------
-63552405302952 -32523380442305 7746682944537 -50152546997616
-21530 7900 -11415 5399
21699 29516 10199 5400
21701 29517 -24116 5400
72918 -72917 27100 -45817
1 -1 100019 100018
0 0 1 1
------------------------------------------------------------------------
53669921692178 |)
-17414 |
-17416 |
51216 |
1 |
0 |
0 |
o4 : Sequence
|
i5 : m * c == n
o5 = true
|