chirotopeString(Matrix) -- compute the chirotope string of a point or vector configuration

Synopsis

Function: chirotopeString
Usage:

chirotopeString A
Inputs:
- A, a matrix,
Optional inputs:
- Homogenize => a Boolean value, default value true
Outputs:
- a string,

Description

Let $A^h$ be the matrix obtained from $A$ by adding a row of one's (called the homogenization of $A$). Sort all of the subsets of size $d+1$ of $0, \ldots, n-1$ lexicographically. The resulting string has two parts: the header, which has $n$ and $d+1$, and then a single string consisting of "0", "-" and "+", one for each subset, where the character records the sign of the determinant of the submatrix consisting of the columns in the subset.

i1 : A = matrix {
         {0, -1, 2, 3, 4, -5, 6},
         {0, 1, -4, 9, 16, 25, 36},
         {0, 1, 8, -27, 64, 125, -216}}

o1 = | 0 -1 2  3   4  -5  6    |
     | 0 1  -4 9   16 25  36   |
     | 0 1  8  -27 64 125 -216 |

              3       7
o1 : Matrix ZZ  <-- ZZ

i2 : om = chirotopeString A

o2 = 7,4:
     ---0++-+----+-++++++--+-+++++++-+++

i3 : om == naiveChirotopeString A

o3 = true

Topcom often works as follows: it creates the oriented matroid (string, or an internal version of it), and uses that to find triangulations. It is important to note that one can find all triangulations this way. However, one needs the matrix $A$ to be able to determine if a given triangulation is regular.

i4 : orientedCircuits om

o4 = {{{0}, {1, 2, 6}}, {{0, 2, 4, 6}, {3}}, {{0, 3}, {2, 5, 6}}, {{0, 3, 5},
     ------------------------------------------------------------------------
     {1, 4}}, {{0, 4}, {1, 2, 3}}, {{0, 4}, {2, 3, 5}}, {{0, 4}, {2, 5, 6}},
     ------------------------------------------------------------------------
     {{0, 4, 6}, {1, 3}}, {{0, 4, 6}, {3, 5}}, {{0, 5}, {1, 2, 3}}, {{0, 5},
     ------------------------------------------------------------------------
     {1, 2, 4}}, {{0, 5, 6}, {1, 3}}, {{0, 5, 6}, {1, 4}}, {{1, 2, 4, 6},
     ------------------------------------------------------------------------
     {3}}, {{1, 3}, {2, 5, 6}}, {{1, 4}, {2, 3, 5}}, {{1, 4}, {2, 5, 6}},
     ------------------------------------------------------------------------
     {{1, 4, 6}, {3, 5}}, {{2, 4, 5, 6}, {3}}}

o4 : List

i5 : orientedCocircuits om

o5 = {{{3, 4, 5}, {}}, {{2, 4, 5}, {6}}, {{2, 5}, {3, 6}}, {{2}, {3, 4, 6}},
     ------------------------------------------------------------------------
     {{1, 4, 5}, {6}}, {{1, 5}, {3, 6}}, {{1}, {3, 4, 6}}, {{1, 5, 6}, {2}},
     ------------------------------------------------------------------------
     {{1, 6}, {2, 4}}, {{1, 4, 5}, {2}}, {{1, 3, 6}, {2}}, {{1, 5}, {2, 3}},
     ------------------------------------------------------------------------
     {{1}, {2, 3, 4}}, {{0, 6}, {4, 5}}, {{0, 3, 6}, {5}}, {{0, 3, 4, 6},
     ------------------------------------------------------------------------
     {}}, {{0, 2}, {5, 6}}, {{0, 2, 4}, {6}}, {{0, 2}, {4, 5}}, {{0, 2}, {3,
     ------------------------------------------------------------------------
     6}}, {{0, 2, 3}, {5}}, {{0, 2, 3, 4}, {}}, {{0, 1, 5}, {6}}, {{0, 1, 6},
     ------------------------------------------------------------------------
     {4}}, {{0, 1, 5}, {4}}, {{0, 1, 3, 6}, {}}, {{0, 1, 3, 5}, {}}, {{0, 1},
     ------------------------------------------------------------------------
     {3, 4}}, {{0, 1, 2}, {6}}, {{0, 1, 5}, {2}}, {{0, 1, 2}, {4}}, {{0, 1,
     ------------------------------------------------------------------------
     2, 3}, {}}}

o5 : List

Caveat

If the number of minors of size $(d+1) \times (d+1)$ of $A^h$ is too large, then this won't work so well....! For example, in dimension 4, with 100 vertices, the number of such determinants is about 75 million. That is fine perhaps, but for 200 vertices, the size jumps to 2.5 billion.

Ways to use this method: