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 that$AU = B$.

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

o1 = | -8031  0      0      0      88379  -94929 0      0      0      0     
     | 55574  20182  70070  0      0      -13982 -94602 0      -40555 -9613 
     | -74322 -33228 0      -40828 -68991 0      0      -67902 65046  74210 
     | 89120  -17794 59911  0      0      0      -28590 -89433 0      4549  
     | 55425  -90574 0      0      0      -54423 -61026 30061  25364  0     
     | 0      0      0      0      0      -27571 -55134 0      31782  74516 
     | 0      0      0      0      0      83366  95253  0      -38577 0     
     | -59640 -23833 0      0      0      -82072 70952  0      0      0     
     | 0      0      0      0      0      -34637 -36361 0      0      -14763
     | 0      80627  -71921 0      0      0      0      -68183 80908  0     
     ------------------------------------------------------------------------
     |
     |
     |
     |
     |
     |
     |
     |
     |
     |

              10       10
o1 : Matrix ZZ   <-- ZZ

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

o2 = (| 0      -9512  88379 -9512  0      1481   1481   8031   1481   1481  
      | 0      11582  0     50710  -9613  28602  -24651 -9242  -21095 -913  
      | -40828 -8307  12665 -17471 -7446  17529  587    -58    12785  20385 
      | 0      -12939 0     42423  4549   -3369  -13214 20857  43947  26153 
      | 0      18370  0     43734  0      -3695  -13673 -40039 31454  -59120
      | 0      15171  0     -27563 74516  -6741  -4219  34304  -38523 -38523
      | 0      50464  0     11887  0      -32365 26690  20478  6212   6212  
      | 0      9911   0     9911   0      -22432 -69551 12521  1401   -22432
      | 0      -16487 0     -1724  -14763 -19874 1724   21598  -19874 -19874
      | 0      3457   0     12444  0      -41222 -21431 -43143 -62653 17974 
     ------------------------------------------------------------------------
     |, | 0 2  0  2  0 -1 -1 -1 -1 -1 |)
     |  | 0 1  0  1  0 0  -1 -1 -1 0  |
     |  | 0 -1 0  0  0 3  -1 -2 2  2  |
     |  | 1 -4 -2 -4 2 1  1  3  2  1  |
     |  | 0 -1 1  -1 0 1  1  0  1  1  |
     |  | 0 -1 0  -1 0 1  1  0  1  1  |
     |  | 0 1  0  1  0 0  -1 -1 0  0  |
     |  | 0 1  0  1  0 1  -1 -2 0  0  |
     |  | 0 -1 0  0  0 3  -1 -3 2  2  |
     |  | 0 1  0  0  1 -1 0  1  -1 -1 |

o2 : Sequence

i3 : B == A*U

o3 = true

Further information

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

Functions with optional argument named ChangeMatrix :

forceGB(...,ChangeMatrix=>...) -- inform Macaulay2 about the change of basis matrix from GB to generators
gb(...,ChangeMatrix=>...) -- see gb -- compute a Gröbner basis
hermite(...,ChangeMatrix=>...) (missing documentation)
LLL(...,ChangeMatrix=>...) -- also find change of basis matrix
markedGB(...,ChangeMatrix=>...) -- see markedGB(Matrix,Matrix) -- make a marked Gröbner basis
smithNormalForm(...,ChangeMatrix=>...) -- see smithNormalForm(Matrix) -- smith normal form for a matrix over ZZ or a PID

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

Synopsis

Description

Further information

See also

Functions with optional argument named ChangeMatrix :