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 = | 54522  75196  -44875 -77800 0      0      0      -21694 0      0     
     | -14686 -41750 0      0      -85492 38879  -6205  -45200 0      -74872
     | 0      61454  0      -98950 0      -75521 85873  0      0      0     
     | -808   0      -47645 0      0      -13451 0      85223  0      0     
     | 0      35318  0      0      0      0      0      89801  0      28105 
     | 81745  0      0      0      15217  -92137 -53264 -21565 -69767 64493 
     | -80986 0      68716  -36494 0      -60310 855    0      -32487 0     
     | 0      0      0      50165  87369  19208  0      -50097 -13071 0     
     | -21938 0      77563  81859  38418  -68959 -48078 0      0      -95264
     | 0      -48603 -89544 35683  0      -45914 9718   6196   352    0     
     ------------------------------------------------------------------------
     |
     |
     |
     |
     |
     |
     |
     |
     |
     |

              10        10
o1 : Matrix ZZ   <--- ZZ

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

o2 = (| 2604   0      2604   54522   75196  -65549 -2604  27513  -2604 
      | -37537 0      -43742 -14686  -41750 20859  -47955 45434  -31130
      | -48377 0      37496  0       61454  24419  48377  -13538 -37496
      | 0      0      0      -808    0      -48453 0      -35962 0     
      | -35318 0      -35318 0       35318  -35318 35318  44258  63423 
      | -1286  -69767 15217  11978   0      28481  16503  -38099 49276 
      | 3152   -32487 36494  -113473 0      -11415 -3152  52755  -36494
      | 24133  -13071 37204  -13071  0      0      63236  -11240 -37204
      | 4637   0      -43441 -21938  0      7547   33781  -42069 -51823
      | 3554   352    12920  352     -48603 -31223 -3554  8553   -12920
     ------------------------------------------------------------------------
     -30117 |, | 0  0 0  1 0 1  0  -2 0  2  |)
     30982  |  | -1 0 -1 0 1 -1 1  3  1  -2 |
     -13606 |  | 0  0 0  0 0 1  0  -1 0  1  |
     22511  |  | -1 0 -1 0 0 0  1  2  1  -1 |
     -8940  |  | 1  0 1  0 0 0  0  -2 -1 1  |
     17015  |  | 0  0 0  0 0 0  0  0  0  1  |
     -83730 |  | -1 0 0  0 0 1  1  0  0  1  |
     19386  |  | 0  0 0  0 0 0  0  -1 0  1  |
     -31527 |  | 1  1 0  1 0 0  -1 -1 0  -1 |
     -58373 |  | 0  0 0  0 0 0  0  1  1  -1 |

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