isLLL -- is a basis an LLL basis?

Synopsis

Usage:

isLLL m
Inputs:
- m, a matrix, over ZZ, whose columns are linearly independent
Optional inputs:
- Threshold (missing documentation) => ..., default value 3/4,
Outputs:
- a Boolean value, Whether the columns of the matrix form an LLL basis with respect to the Threshold (which has default 3/4)

Description

This function is provided by the package LLLBases.

If the matrix is not in LLL reduced form, then the offending conditions are displayed. For example,

i1 : m = matrix {{1, 0}, {1, 1}, {1, 2}, {1, 3}}

o1 = | 1 0 |
     | 1 1 |
     | 1 2 |
     | 1 3 |

              4       2
o1 : Matrix ZZ  <-- ZZ

i2 : isLLL m
LLL size failure 1,0: 1.5
LLL Lovasz failure 1: -.833333

o2 = false

i3 : n = LLL m

o3 = | 1 -1 |
     | 1 0  |
     | 1 1  |
     | 1 2  |

              4       2
o3 : Matrix ZZ  <-- ZZ

i4 : isLLL n

o4 = true

If the optional argument Threshold is given, the conditions are checked using that value.

i5 : m = matrix {{1, 0}, {1, 1}, {1, 2}, {1, 3}}

o5 = | 1 0 |
     | 1 1 |
     | 1 2 |
     | 1 3 |

              4       2
o5 : Matrix ZZ  <-- ZZ

i6 : isLLL(m, Threshold=>1)
LLL size failure 1,0: 1.5
LLL Lovasz failure 1: -1

o6 = false

Caveat

A Gram-Schmidt reduction is done over QQ, so this can be computationally intensive for larger matrix sizes. It is usually easier and faster to see if LLL returns the same matrix. This routine was used to debug and test the LLL routines here, and is provided as an alternate check of correctness.The matrix must be defined over the ring ZZ. It should be possible to allow real and rational matrices too, but this is not yet implemented.

Ways to use isLLL :

isLLL(Matrix)

For the programmer