next | previous | forward | backward | up | top | index | toc | Macaulay2 web site
Normaliz :: The Hilbert basis and the support hyperplanes of a rational cone.

The Hilbert basis and the support hyperplanes of a rational cone.

We want to calculate the Hilbert basis of a rational cone. The cone may be given by

First of all consider the cone generated by the 16 vectors

 1 0 0 0 0 0 0             1 0 1 0 1 0 1
 0 1 0 0 0 0 0             1 0 0 1 0 1 1
 0 0 1 0 0 0 0             1 0 0 0 1 1 1
 0 0 0 1 0 0 0             0 1 1 0 0 1 1
 0 0 0 0 1 0 0             0 1 0 1 1 0 1
 0 0 0 0 0 1 0             0 1 0 0 1 1 1
 1 1 1 0 0 0 1             0 0 1 1 1 0 1
 1 1 0 1 0 0 1             0 0 1 1 0 1 1

in dimension 7. We compute its integral closure in the ambient lattice ℤ7. The fastest way is applying the function intclToricRing to the ideal that is generated by the monomials whose exponent vectors are the generators of the cone (to compute it in the group of the monoid generated by these vectors use normalToricRing) .

One can convert the vectors to monomials in the following way:

i1 : R=ZZ/37[x_1..x_7];
i2 : l={{1, 0, 0, 0, 0, 0, 0},
        {0, 1, 0, 0, 0, 0, 0},
        {0, 0, 1, 0, 0, 0, 0},
        {0, 0, 0, 1, 0, 0, 0},
        {0, 0, 0, 0, 1, 0, 0},
        {0, 0, 0, 0, 0, 1, 0},
        {1, 1, 1, 0, 0, 0, 1},
        {1, 1, 0, 1, 0, 0, 1},
        {1, 0, 1, 0, 1, 0, 1},
        {1, 0, 0, 1, 0, 1, 1},
        {1, 0, 0, 0, 1, 1, 1},
        {0, 1, 1, 0, 0, 1, 1},
        {0, 1, 0, 1, 1, 0, 1},
        {0, 1, 0, 0, 1, 1, 1},
        {0, 0, 1, 1, 1, 0, 1},
        {0, 0, 1, 1, 0, 1, 1}};
i3 : L=for i in l list R_i

o3 = {x , x , x , x , x , x , x x x x , x x x x , x x x x , x x x x ,
       1   2   3   4   5   6   1 2 3 7   1 2 4 7   1 3 5 7   1 4 6 7 
     ------------------------------------------------------------------------
     x x x x , x x x x , x x x x , x x x x , x x x x , x x x x }
      1 5 6 7   2 3 6 7   2 4 5 7   2 5 6 7   3 4 5 7   3 4 6 7

o3 : List
i4 : S=intclToricRing L

     ZZ                                                                                                                                          2
o4 = --[x , x , x , x , x x x x , x x x x , x , x x x x , x x x x , x x x x , x , x x x x , x x x x , x x x x , x x x x , x x x x , x x x x x x x ]
     37  6   5   4   3   3 4 6 7   3 4 5 7   2   2 5 6 7   2 4 5 7   2 3 6 7   1   1 5 6 7   1 4 6 7   1 3 5 7   1 2 4 7   1 2 3 7   1 2 3 4 5 6 7

o4 : monomial subalgebra of R

The function intclToricRing returns a MonomialSubalgebra. The Hilbert basis of the cone consists of the exponent vectors of the generators of the subalgebra. The generators can be extracted with generators.

i5 : hb = flatten \ exponents \  gens S

o5 = {{0, 0, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 1, 0, 0}, {0, 0, 0, 1, 0, 0, 0},
     ------------------------------------------------------------------------
     {0, 0, 1, 0, 0, 0, 0}, {0, 0, 1, 1, 0, 1, 1}, {0, 0, 1, 1, 1, 0, 1}, {0,
     ------------------------------------------------------------------------
     1, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 1, 1, 1}, {0, 1, 0, 1, 1, 0, 1}, {0, 1,
     ------------------------------------------------------------------------
     1, 0, 0, 1, 1}, {1, 0, 0, 0, 0, 0, 0}, {1, 0, 0, 0, 1, 1, 1}, {1, 0, 0,
     ------------------------------------------------------------------------
     1, 0, 1, 1}, {1, 0, 1, 0, 1, 0, 1}, {1, 1, 0, 1, 0, 0, 1}, {1, 1, 1, 0,
     ------------------------------------------------------------------------
     0, 0, 1}, {1, 1, 1, 1, 1, 1, 2}}

o5 : List

It is also possible to call Normaliz directly to do this computation by using the function normaliz. It takes as input the matrix containing the generators as rows, and the type for the computation.

i6 : M=matrix l;

              16        7
o6 : Matrix ZZ   <--- ZZ
i7 : d=(normaliz(M,"normalization"))#"gen"

o7 = | 0 0 0 0 0 1 0 |
     | 0 0 0 0 1 0 0 |
     | 0 0 0 1 0 0 0 |
     | 0 0 1 0 0 0 0 |
     | 0 0 1 1 0 1 1 |
     | 0 0 1 1 1 0 1 |
     | 0 1 0 0 0 0 0 |
     | 0 1 0 0 1 1 1 |
     | 0 1 0 1 1 0 1 |
     | 0 1 1 0 0 1 1 |
     | 1 0 0 0 0 0 0 |
     | 1 0 0 0 1 1 1 |
     | 1 0 0 1 0 1 1 |
     | 1 0 1 0 1 0 1 |
     | 1 1 0 1 0 0 1 |
     | 1 1 1 0 0 0 1 |
     | 1 1 1 1 1 1 2 |

              17        7
o7 : Matrix ZZ   <--- ZZ
i8 : set entries d===set hb

o8 = true

The result is an object of type RationalCone from which you obtain the Hilbert basis via the key "gen".

The support hyperplanes are stored in the Normaliz file <filename>.sup. To inspect these, one has to assure that the computations by Normaliz are kept. This can be done by specifying a filename, that is, assigning a non-empty string to the global variable nmzFilename, see also Keeping results of the computation by Normaliz. Then use readNmzData to read the .sup file.

i9 : nmzFilename="rproj2";
i10 : intclToricRing L;
i11 : hypes=readNmzData("sup")

o11 = | 0 0 0 0 0 0 1  |
      | 0 0 0 0 0 1 0  |
      | 0 0 0 0 1 0 0  |
      | 0 0 0 1 0 0 0  |
      | 0 0 1 0 0 0 0  |
      | 0 0 1 1 0 1 -1 |
      | 0 0 1 1 1 0 -1 |
      | 0 1 0 0 0 0 0  |
      | 0 1 0 0 1 1 -1 |
      | 0 1 0 1 1 0 -1 |
      | 0 1 1 0 0 1 -1 |
      | 0 1 1 1 1 1 -2 |
      | 1 0 0 0 0 0 0  |
      | 1 0 0 0 1 1 -1 |
      | 1 0 0 1 0 1 -1 |
      | 1 0 1 0 1 0 -1 |
      | 1 0 1 1 1 1 -2 |
      | 1 1 0 1 0 0 -1 |
      | 1 1 0 1 1 1 -2 |
      | 1 1 1 0 0 0 -1 |
      | 1 1 1 0 1 1 -2 |
      | 1 1 1 1 0 1 -2 |
      | 1 1 1 1 1 0 -2 |
      | 1 1 1 1 1 1 -3 |

               24        7
o11 : Matrix ZZ   <--- ZZ

This means there are 24 support hyperplanes in ℤ7. So in contrast to the convention of M2 Normaliz writes vectors as rows. If you don't want to keep the results of the computations any longer, use rmNmzFiles to delete the files created by Normaliz.

i12 : rmNmzFiles();

Conversely, suppose the cone is given by the above hyperplanes. In that case, to compute the Hilbert basis, you should use Normaliz in type inequalities. The result is an object of type RationalCone. The Hilbert basis is accessible via the key "gen". Not surprisingly, it is the same Hilbert basis as above (but in another order).

i13 : normaliz(hypes,"inequalities")

o13 = RationalCone{gen => | 0 0 0 0 0 1 0 |                                       }
                          | 0 0 0 0 1 0 0 |
                          | 0 0 0 1 0 0 0 |
                          | 0 0 1 0 0 0 0 |
                          | 0 0 1 1 0 1 1 |
                          | 0 0 1 1 1 0 1 |
                          | 0 1 0 0 0 0 0 |
                          | 0 1 0 0 1 1 1 |
                          | 0 1 0 1 1 0 1 |
                          | 0 1 1 0 0 1 1 |
                          | 1 0 0 0 0 0 0 |
                          | 1 0 0 0 1 1 1 |
                          | 1 0 0 1 0 1 1 |
                          | 1 0 1 0 1 0 1 |
                          | 1 1 0 1 0 0 1 |
                          | 1 1 1 0 0 0 1 |
                          | 1 1 1 1 1 1 2 |
                   inv => HashTable{ => (1, 1, 1, 1, 1, 1, 1)                    }
                                    class group => 1 : (17)
                                    degree 1 elements => 16
                                    dim max subspace => 0
                                    embedding dim => 7
                                    external index => 1
                                    graded => true
                                    grading => (1, 1, 1, 1, 1, 1, -2)
                                    grading denom => 1
                                    hilbert basis elements => 17
                                    hilbert quasipolynomial denom => 60
                                    hilbert series denom => (1, 1, 1, 1, 1, 1, 1)
                                    hilbert series num => (1, 9, 31, 25, 6)
                                    inhomogeneous => false
                                    multiplicity => 72
                                    multiplicity denom => 1
                                    number extreme rays => 16
                                    number support hyperplanes => 24
                                    rank => 7
                                    size triangulation => 69
                                    sum dets => 72

o13 : RationalCone
i14 : set entries oo#"gen"===set hb

o14 = true

Note that for the comparison set has to be used because the order of the generators may differ.


To illustrate the third possibility we compute the Hilbert basis of the cone given by the equations

1 1 1 -1 -1 -1  0  0  0
1 1 1  0  0  0 -1 -1 -1
0 1 1 -1  0  0 -1  0  0
1 0 1  0 -1  0  0 -1  0
1 1 0  0  0 -1  0  0 -1
0 1 1  0 -1  0  0  0 -1
1 1 0  0 -1  0 -1  0  0

(this is the solution cone for a 3x3 magic square). To this end one has to choose type 5.

i15 : eq=matrix {{1, 1, 1, -1, -1, -1,  0,  0,  0}, {1, 1, 1,  0,  0,  0, -1, -1, -1}, {0, 1, 1, -1,  0,  0, -1,  0,  0}, {1, 0, 1,  0, -1,  0,  0, -1,  0}, {1, 1, 0,  0,  0, -1,  0,  0, -1}, {0, 1, 1,  0, -1,  0,  0,  0, -1}, {1, 1, 0,  0, -1,  0, -1,  0,  0}};

               7        9
o15 : Matrix ZZ  <--- ZZ
i16 : normaliz(eq,"equations")

o16 = RationalCone{gen => | 0 2 1 2 1 0 1 0 2 |                            }
                          | 1 0 2 2 1 0 0 2 1 |
                          | 1 1 1 1 1 1 1 1 1 |
                          | 1 2 0 0 1 2 2 0 1 |
                          | 2 0 1 0 1 2 1 2 0 |
                   inv => HashTable{ => (1, 1, 1)                         }
                                    class group => (1, 2, 2)
                                    degree 1 elements => 5
                                    dim max subspace => 0
                                    embedding dim => 9
                                    external index => 1
                                    graded => true
                                    grading => (0, 0, 0, 0, 1, 0, 0, 0, 0)
                                    grading denom => 1
                                    hilbert basis elements => 5
                                    hilbert quasipolynomial denom => 1
                                    hilbert series denom => (1, 1, 1)
                                    hilbert series num => (1, 2, 1)
                                    inhomogeneous => false
                                    multiplicity => 4
                                    multiplicity denom => 1
                                    number extreme rays => 4
                                    number support hyperplanes => 4
                                    rank => 3
                                    size triangulation => 2
                                    sum dets => 4

o16 : RationalCone
Again the rows of this matrix are the elements of the Hilbert basis.