## `lllint` -- compute an LLL-reduced basis of a lattice

#### Introduction

`lllint(`A`)` applies the LLL algorithm to the columns of the (not necessary square) matrix `A` with integer entries.

#### Call(s)

`lllint(A, All)`
`lllint(A)`

#### Parameters

`A` | - | a matrix, given as a list of row vectors, each row being a list of integers

#### Returns

- With option All, a list `[T, B]` is returned, such that `B = A*T` and the columns of `B` form an LLL-reduced basis of the lattice spanned by the columns of `A`. Both `T` and `B` are given as lists of row vectors.

- Without option All, `lllint` only returns the transformation matrix `T` as a list of row vectors.

#### Related Functions

`linalg::basis`, `linalg::factorLU`, `linalg::factorQR`, `linalg::gaussElim`, `linalg::hermiteForm`, `linalg::orthog`

#### Details

- `lllint` applies the LLL algorithm to the columns of the matrix `A`. Mathematically, the input matrix can be an arbitrary matrix with integer entries, possibly non-square, and possibly without full column rank.

  The matrix is passed to `lllint` in form of a list of row vectors, where each row vector is again a list of integers. The number of entries in each row must be equal. The matrices returned by `lllint` have this form as well.

  The computations are done entirely with integers and are both accurate and quite fast.

- You can use `matrix` to obtain a nicer screen output of the matrices. See example 1.

- `lllint` is a function of the system kernel.

#### Example 1

We apply the LLL algorithm to a matrix with two rows and three columns:

    >> A := [[1, 2, 3], [4, 5, 6]]:
       [T, B] := lllint(A, All)

                  [[[-1, 4], [1, -3], [0, 0]], [[1, -2], [1, 1]]]

We use `matrix` to print `A,T`, and `B` in a nicer form and check that indeed `B = A*T`:

    >> matrix(A), matrix(T), matrix(B)

                                    +-        -+
                     +-         -+  |  -1,  4  |  +-       -+
                     |  1, 2, 3  |  |          |  |  1, -2  |
                     |           |, |   1, -3  |, |         |
                     |  4, 5, 6  |  |          |  |  1,  1  |
                     +-         -+  |   0,  0  |  +-       -+
                                    +-        -+

    >> matrix(B) = matrix(A)*matrix(T)

                             +-       -+   +-       -+
                             |  1, -2  |   |  1, -2  |
                             |         | = |         |
                             |  1,  1  |   |  1,  1  |
                             +-       -+   +-       -+

The result is to be interpreted as follows: the two column vectors

    +- -+     +-  -+
    | 1 |     | -2 |
    |   | and |    |
    | 1 |     |  1 |
    +- -+     +-  -+

form an LLL-reduced basis of the integer lattice generated by the three column vectors

    +- -+  +- -+      +- -+
    | 1 |  | 2 |      | 3 |
    |   |, |   |, and |   |.
    | 4 |  | 5 |      | 6 |
    +- -+  +- -+      +- -+

Without the option All, `lllint` returns only the transformation matrix `T`:

    >> matrix(lllint([[1, 2, 3], [4, 5, 6]]))

                                   +-        -+
                                   |  -1,  4  |
                                   |          |
                                   |   1, -3  |
                                   |          |
                                   |   0,  0  |
                                   +-        -+

#### Background

- References:

  A. K. Lenstra, H. W. Lenstra Jr., and L. Lovasz, Factoring polynomials with rational coefficients. Math. Ann. 261, 1982, pp. 515-534.

  Joachim von zur Gathen and Jürgen Gerhard, Modern Computer Algebra. Cambridge University Press, 1999, Chapter 16.

  George L. Nemhauser and Laurence A. Wolsey, Integer and Combinatorial Optimization. New York, Wiley, 1988.

  A. Schrijver, Theory of Linear and Integer Programming. New York, Wiley, 1986.

#### Changes

- no changes

Do you have questions or comments?
Copyright © SciFace Software GmbH & Co. KG 2000