LLL(..., ChangeMatrix => ...) -- also find change of basis matrix

Synopsis

Usage:
(B,U) = LLL(A,ChangeMatrix=>true)
Inputs:
- A, a matrix, over the integers, of size d by n
Outputs:
- B, a matrix, the LLL matrix (also having d rows)
- U, a matrix, the n by n invertible transform matrix
Consequences:
- The routine returns a pair of matrices, rather than just one

Description

Constructs the change of basis matrix U from the basis A to the basis B. This is an invertible matrix U such thatAU = B.

i1 : A = matrix randomMutableMatrix(10,10,.5,100000)

o1 = | -52677 -12289 -26460 0      -41690 -45251 0      0      0      0     
     | 43398  0      0      0      0      0      0      0      -54152 0     
     | 0      0      -13350 -21081 0      -90302 0      61080  0      42747 
     | -50452 -2300  0      0      91938  0      0      0      0      -72545
     | 72214  78806  0      50789  -68012 -17056 0      0      75513  0     
     | 0      -35332 38252  60505  -73468 0      -48548 76954  -32787 0     
     | -59989 0      48589  0      0      29803  48240  -67957 0      -85205
     | 0      62509  -15295 0      0      -83096 -25232 0      88745  0     
     | 25183  80160  57240  0      0      0      0      0      86665  0     
     | 0      21001  22834  -40866 -36816 -33066 0      0      86636  0     
     ------------------------------------------------------------------------
     |
     |
     |
     |
     |
     |
     |
     |
     |
     |

              10        10
o1 : Matrix ZZ   <--- ZZ

i2 : (B,U) = LLL(A, ChangeMatrix=>true)

o2 = (| 0      -26460 0      21597  0      12289  -50998 -19918 -50998 28099 
      | 0      0      0      -43398 0      -54152 -10754 -10754 -10754 10754 
      | 0      -13350 -21081 -15872 -61080 -21081 -5209  32329  16457  0     
      | 0      0      0      48152  0      2300   46086  -24159 -26459 45852 
      | 0      0      50789  -10464 0      47496  -10052 -21013 40737  9885  
      | -48548 38252  11957  3370   -28406 14502  -13788 43347  -1831  10671 
      | 48240  48589  48240  -26754 19717  48240  26754  28292  -10211 11749 
      | -25232 -15295 -25232 -5292  25232  1004   31528  36820  6296   61505 
      | 0      57240  0      -2263  0      6505   8768   -14152 8768   48472 
      | 0      22834  -40866 -34899 0      24769  22852  16885  -18014 -44634
     ------------------------------------------------------------------------
     |, | 0 0 0 -1 0  0  1  1  1  -1 |)
     |  | 0 0 0 1  0  -1 -2 -3 -2 2  |
     |  | 0 1 0 -1 0  0  1  2  1  0  |
     |  | 0 0 1 0  0  1  1  2  2  0  |
     |  | 0 0 0 0  0  0  1  1  1  0  |
     |  | 0 0 0 1  0  0  -1 -2 -1 0  |
     |  | 1 0 1 0  -1 1  0  0  1  -1 |
     |  | 0 0 0 1  -1 0  -1 -2 -1 0  |
     |  | 0 0 0 0  0  1  1  1  1  -1 |
     |  | 0 0 0 0  0  0  0  1  1  0  |

o2 : Sequence

i3 : B == A*U

o3 = true

Further information

Default value: false
Function: LLL -- compute an LLL basis
Option name: ChangeMatrix -- name for an optional argument

LLL(..., ChangeMatrix => ...) -- also find change of basis matrix

Synopsis

Description

Further information

See also