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
Consequences:
- The routine returns a pair of matrices, rather than just one
Outputs:
- B, a matrix, the LLL matrix (also having d rows)
- U, a matrix, the n by n invertible transform matrix

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 = | 0      0      -61720 -41808 0      51992  0      56037  0      0     |
     | 74012  44792  -9807  0      35186  99616  0      44312  0      0     |
     | 0      -86023 -13424 3595   0      45292  -69904 0      -29059 0     |
     | 0      0      0      0      0      -90510 -41552 0      0      0     |
     | 35944  0      0      22334  0      0      0      -71985 0      0     |
     | 0      -84756 -65163 19744  0      47487  -57859 -18728 31242  35987 |
     | 0      -3486  36171  0      -57299 0      71414  0      0      0     |
     | -60746 -4614  1606   39540  0      0      42343  0      65103  68122 |
     | 42610  0      0      33410  0      98415  -9776  0      0      61759 |
     | -51408 0      0      75257  35973  0      0      0      58812  25261 |

              10        10
o1 : Matrix ZZ   <--- ZZ

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

o2 = (| 0      -61720 41808  0      0      19912  43869  4045   28035  -53597
      | 35186  -9807  -9606  9606   -9606  9807   28716  -504   -9279  327   
      | 0      -13424 12524  -45178 16119  -23826 -6921  16005  7935   5397  
      | 0      0      -41552 41552  -41552 -41552 7406   7406   -14812 -14812
      | 0      0      -22334 0      0      22334  8627   -36041 -22237 -8627 
      | 0      -65163 7153   4345   26897  -4194  10153  -7676  27715  24885 
      | -57299 36171  17601  -17601 17601  35243  16673  35202  -30747 45081 
      | 0      1606   7417   18146  46957  15174  -25784 36187  -40591 -2845 
      | 0      0      -43186 9776   -9776  23634  -8537  -13598 -6214  2986  
      | 35973  0      -39284 22839  35973  16445  17455  -13013 9581   540   
     ------------------------------------------------------------------------
     |, | 0 0 0  0  0  0  1  1  -2 -1 |)
     |  | 0 0 -1 1  -1 0  -1 -2 3  2  |
     |  | 0 1 0  0  0  -1 -2 0  1  3  |
     |  | 0 0 -1 0  0  1  2  0  -1 -2 |
     |  | 1 0 1  -1 1  0  1  2  -4 -4 |
     |  | 0 0 0  0  0  0  -1 -1 2  2  |
     |  | 0 0 1  -1 1  1  2  2  -4 -4 |
     |  | 0 0 0  0  0  0  1  1  -1 -1 |
     |  | 0 0 0  1  0  -1 -2 -1 3  5  |
     |  | 0 0 0  0  0  0  0  1  -2 -2 |

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