50.37 ShortestVectors

ShortestVectors( G, m )
ShortestVectors( G, m, "positive" )

computes all vectors x with x G x^{tr} leq m, where G is a matrix of a symmetric bilinear form, and m is a nonnegative integer. If the optional argument "positive" is entered, only those vectors x with nonnegative entries are computed.

ShortestVectors returns a record with components

vectors:

the list of vectors x, and

norms:

the list of their norms according to the Gram matrix G.

    gap> g:= [ [ 2, 1, 1 ], [ 1, 2, 1 ], [ 1, 1, 2 ] ];;
    gap> ShortestVectors(g,4);
    rec(
      vectors := [ [ -1, 1, 1 ], [ 0, 0, 1 ], [ -1, 0, 1 ], [ 1, -1, 1 ],
          [ 0, -1, 1 ], [ -1, -1, 1 ], [ 0, 1, 0 ], [ -1, 1, 0 ],
          [ 1, 0, 0 ] ],
      norms := [ 4, 2, 2, 4, 2, 4, 2, 2, 2 ] )

This algorithm is used in OrthogonalEmbeddings OrthogonalEmbeddings.

Previous Up Top Next
Index