This is AllMarkovBases.info, produced by Macaulay2, version 1.26.06

AllMarkovBases -- compute all minimal Markov Bases of a toric ideal
*******************************************************************

Description
===========

Fix a matrix $A = (a_{i,j}) \in \ZZ^{d \times n}$ satisfying $\ker(A) \cap
(\ZZ_{\ge 0})^n = \{0\}$. The toric ideal $I_A$ is the kernel of the associated
monomial map $\phi_A : k[x_1, \dots, x_n] \rightarrow k[t_1, \dots, t_d]$ given
by $\phi(x_i) = t_1^{a_{1,i}} t_2^{a_{2,i}} \dots t_d^{a_{d,i}}$ for each $i
\in [n]$. A Markov basis is a minimal generating set for a toric ideal. Markov
bases are used in Algebraic Statistics in hypothesis testing for contingency
tables; for further details we refer to: M. Drton, B. Sturmfels, and S.
Sullivant Lectures on Algebraic Statistics

This package computes the set of all minimal Markov bases of a given toric
ideal $I_A$. We do this by using FourTiTwo, to
efficiently compute one Markov basis $M$. We then compute all spanning forests
of the fiber graph of $A$ in the generating fibers using the well-known
bijection of Prüfer. Each spanning forest corresponds to a Markov basis, which
gives us an efficient way to compute the number of Markov bases of $A$ as well
as produce the Markov bases. For further theoretical details, see H.
Charalambous, K. Anargyros, A. Thoma Minimal systems of binomial generators and
the indispensable complex of a toric ideal.

Below is an example showing how to compute all Markov bases for the matrix $A =
(7 \ 8 \ 9 \ 10) \in \ZZ^{1 \times 4}$.

+---------------------------+
|i1 : A = matrix "7,8,9,10";|
|                           |
|              1       4    |
|o1 : Matrix ZZ  <-- ZZ     |
+---------------------------+
|i2 : countMarkov A         |
|                           |
|o2 = 4                     |
+---------------------------+
|i3 : netList markovBases A |
|                           |
|     +--------------+      |
|o3 = || 1 -2 1  0  ||      |
|     || 1 -1 -1 1  ||      |
|     || 0 1  -2 1  ||      |
|     || 4 -1 0  -2 ||      |
|     || 3 1  -1 -2 ||      |
|     || 2 2  0  -3 ||      |
|     +--------------+      |
|     || 1 -2 1  0  ||      |
|     || 1 -1 -1 1  ||      |
|     || 0 1  -2 1  ||      |
|     || 4 -1 0  -2 ||      |
|     || 3 1  -1 -2 ||      |
|     || 3 0  1  -3 ||      |
|     +--------------+      |
|     || 1 -2 1  0  ||      |
|     || 1 -1 -1 1  ||      |
|     || 0 1  -2 1  ||      |
|     || 4 0  -2 -1 ||      |
|     || 3 1  -1 -2 ||      |
|     || 2 2  0  -3 ||      |
|     +--------------+      |
|     || 1 -2 1  0  ||      |
|     || 1 -1 -1 1  ||      |
|     || 0 1  -2 1  ||      |
|     || 4 0  -2 -1 ||      |
|     || 3 1  -1 -2 ||      |
|     || 3 0  1  -3 ||      |
|     +--------------+      |
+---------------------------+

The format of the output follows that of toricMarkov (FourTiTwo),
so each minimal Markov basis is given by a matrix
whose rows correspond to elements of the Markov basis.

If the configuration matrix has too many minimal Markov bases, then it may be
convenient to use a random Markov basis. This package provides a method to
produce a random minimal Markov basis that is uniformly sampled from the set of
all minimal Markov bases.

+-----------------------------------+
|i4 : A = matrix "2,3,5,7,30,31,32";|
|                                   |
|              1       7            |
|o4 : Matrix ZZ  <-- ZZ             |
+-----------------------------------+
|i5 : countMarkov A                 |
|                                   |
|o5 = 228960                        |
+-----------------------------------+
|i6 : randomMarkov A                |
|                                   |
|o6 = | 1  1  -1 0  0  0  0  |      |
|     | 3  -2 0  0  0  0  0  |      |
|     | 2  1  0  -1 0  0  0  |      |
|     | 3  0  2  2  -1 0  0  |      |
|     | 0  8  0  1  0  -1 0  |      |
|     | 11 1  0  1  0  0  -1 |      |
|                                   |
|              6       7            |
|o6 : Matrix ZZ  <-- ZZ             |
+-----------------------------------+

The package also provides methods to compute the indispensable set and
universal Markov basis; see toricIndispensableSet,
and toricUniversalMarkov. These methods exploit
the fiber graph to compute these respective sets of binomials.

References
==========

  * B. Sturmfels.    Groebner bases and Convex Polytopes. Volume 8 of
    University Lecture Series. American Mathematical Society, Providence, RI,
    1996.
  * M. Drton, B. Sturmfels, and S. Sullivant.    Lectures on Algebraic
    Statistics.Oberwolfach Seminar Series39 Basel, Switzerland, Birkhäuser
    Verlag, 2009.
  * H. Charalambous, K. Anargyros, and A. Thoma. Minimal systems of binomial
    generators and the indispensable complex of a toric ideal. Volume 135 of
    Proceedings of the American Mathematical Society2007.
  * Prüfer, H. (1918). Neuer Beweis eines Satzes über Permutationen.Arch. Math.
    Phys. 27: 742–744.

Authors
=======

  * Alexander Milner (see https://alexandermilner.github.io/ )
    <A.J.C.Milner@sms.ed.ac.uk>
  * Oliver Clarke (see https://www.oliverclarkemath.com/ )
    <oliver.clarke@durham.ac.uk>

Version
=======

This documentation describes version 1.0 of AllMarkovBases, released May 08,
2025.

Citation
========

If you have used this package in your research, please cite it as follows:

+-----------------------------------------------------------------------------+
|@misc{AllMarkovBasesSource,                                                  |
|  title = {{AllMarkovBases: computing all minimal Markov bases of            |
|  author = {Alexander Milner and Oliver Clarke},                             |
|  howpublished = {A \emph{Macaulay2} package available at                    |
|    \url{https://github.com/Macaulay2/M2/tree/stable/M2/Macaulay2/           |
|}                                                                            |
|-----------------------------------------------------------------------------|
|a configuration matrix. Version~1.0}},                                       |
|                                                                             |
|                                                                             |
|packages}}                                                                   |
+-----------------------------------------------------------------------------+

Exports
=======

  * Functions and commands
      * computeFiber -- compute a single fiber of
        configuration matrix
      * countMarkov -- the number of minimal Markov bases
        of a configuration matrix
      * fiberGraph -- generating fibers of a configuration
        matrix
      * markovBases -- all minimal Markov bases of a
        configuration matrix
      * pruferSequence -- the edge set of a spanning
        tree corresponding to a Prüfer sequence
      * randomMarkov -- get a random minimal Markov basis
      * toricIndispensableSet -- the
        indispensable set of toric binomials
      * toricUniversalMarkov -- the universal
        Markov basis
  * Methods
      * "computeFiber(Matrix,Vector)" -- see computeFiber,
        -- compute a single fiber of configuration matrix
      * "countMarkov(Matrix)" -- see countMarkov, -- the
        number of minimal Markov bases of a configuration matrix
      * "fiberGraph(Matrix)" -- see fiberGraph, -- generating
        fibers of a configuration matrix
      * "markovBases(Matrix)" -- see markovBases, -- all
        minimal Markov bases of a configuration matrix
      * "markovBases(Matrix,Ring)" -- see markovBases, --
        all minimal Markov bases of a configuration matrix
      * "pruferSequence(List)" -- see pruferSequence, --
        the edge set of a spanning tree corresponding to a Prüfer sequence
      * "randomMarkov(Matrix)" -- see randomMarkov, -- get
        a random minimal Markov basis
      * "randomMarkov(Matrix,Ring)" -- see randomMarkov, --
        get a random minimal Markov basis
      * "toricIndispensableSet(Matrix)" -- see toricIndispensableSet,
        -- the indispensable set of toric binomials
      * "toricIndispensableSet(Matrix,Ring)" -- see
        toricIndispensableSet, -- the indispensable set
        of toric binomials
      * toricIndispensableSet(Matrix,Matrix) (missing documentation)
      * "toricUniversalMarkov(Matrix)" -- see toricUniversalMarkov,
        -- the universal Markov basis
      * "toricUniversalMarkov(Matrix,Ring)" -- see toricUniversalMarkov,
        -- the universal Markov basis
  * Symbols
      * "FiberAlgorithm" -- see computeFiber, -- compute a
        single fiber of configuration matrix
      * "ReturnConnectedComponents" -- see computeFiber, --
        compute a single fiber of configuration matrix
      * "AlwaysReturnList" -- see randomMarkov, -- get a
        random minimal Markov basis
      * "NumberOfBases" -- see randomMarkov, -- get a
        random minimal Markov basis
      * ReturnFiberValues (missing documentation)

For the programmer
==================

The object AllMarkovBases, is a package (Macaulay2Doc),
defined in AllMarkovBases.m2.

-------------------------------------------------------------------------------

The source of this document is in AllMarkovBases.m2:680:0.

randomMarkov -- get a random minimal Markov basis
*************************************************

  * Usage:
        B = randomMarkov A
        I = randomMarkov(A, R)
  * Inputs:
      * A, a matrix (Macaulay2Doc), the configuration matrix
      * R, a ring (Macaulay2Doc), with one generator for each
        column of $A$
  * Optional inputs (Macaulay2Doc),:
      * NumberOfBases => an integer (Macaulay2Doc), default value 1,
        the number of Markov bases to return
      * AlwaysReturnList => a Boolean value (Macaulay2Doc),
        default value false, if true (or NumberOfBases > 1) then returns the
        result as a list
  * Outputs:
      * B, a matrix (Macaulay2Doc), a random Markov basis of $A$
      * I, an ideal (Macaulay2Doc), an ideal in $R$ generated by a
        random Markov basis of $A$

Description
===========

This method outputs one minimal Markov basis of $A$ chosen uniformly at random.

+----------------------------------+
|i1 : randomMarkov matrix "1,2,3,4"|
|                                  |
|o1 = | 2 -1 0  0  |               |
|     | 1 1  -1 0  |               |
|     | 4 0  0  -1 |               |
|                                  |
|              3       4           |
|o1 : Matrix ZZ  <-- ZZ            |
+----------------------------------+
|i2 : A = matrix "2,3,5,7,30,31,32"|
|                                  |
|o2 = | 2 3 5 7 30 31 32 |         |
|                                  |
|              1       7           |
|o2 : Matrix ZZ  <-- ZZ            |
+----------------------------------+
|i3 : randomMarkov A               |
|                                  |
|o3 = | 1  1  -1 0  0  0  0  |     |
|     | 3  -2 0  0  0  0  0  |     |
|     | 1  0  1  -1 0  0  0  |     |
|     | 10 0  2  0  -1 0  0  |     |
|     | 0  1  0  4  0  -1 0  |     |
|     | 0  4  4  0  0  0  -1 |     |
|                                  |
|              6       7           |
|o3 : Matrix ZZ  <-- ZZ            |
+----------------------------------+

The option NumberOfBases, allows us specify how many Markov
bases to return. If this number is greater than one, then the function returns
a list of Markov bases. Since each Markov basis is produced independently, it
is possible for the list to contain repeats. One may check how many minimal
Markov bases exist with the function countMarkov, and the
list of all Markov bases can be computed with markovBases.
Just like markovBases, we may specify a ring, which
produces an ideal whose generating set is given by a random minimal Markov
basis.

+-----------------------------------------------------------------------------+
|i4 : A = matrix "2,3,5,7,30,31,32"                                           |
|                                                                             |
|o4 = | 2 3 5 7 30 31 32 |                                                    |
|                                                                             |
|              1       7                                                      |
|o4 : Matrix ZZ  <-- ZZ                                                       |
+-----------------------------------------------------------------------------+
|i5 : randomMarkov(A, NumberOfBases => 2)                                     |
|                                                                             |
|o5 = {| 1 1  -1 0  0  0  0  |, | 1  1  -1 0  0  0  0  |}                     |
|      | 3 -2 0  0  0  0  0  |  | 3  -2 0  0  0  0  0  |                      |
|      | 1 0  1  -1 0  0  0  |  | 2  1  0  -1 0  0  0  |                      |
|      | 1 2  3  1  -1 0  0  |  | 2  7  1  0  -1 0  0  |                      |
|      | 2 2  0  3  0  -1 0  |  | 13 0  1  0  0  -1 0  |                      |
|      | 1 10 0  0  0  0  -1 |  | 3  7  1  0  0  0  -1 |                      |
|                                                                             |
|o5 : List                                                                    |
+-----------------------------------------------------------------------------+
|i6 : countMarkov A                                                           |
|                                                                             |
|o6 = 228960                                                                  |
+-----------------------------------------------------------------------------+
|i7 : R = ZZ[x_1 .. x_7]                                                      |
|                                                                             |
|o7 = R                                                                       |
|                                                                             |
|o7 : PolynomialRing                                                          |
+-----------------------------------------------------------------------------+
|i8 : netList randomMarkov(A, R, NumberOfBases => 2)                          |
|                                                                             |
|     +-----------------------------------------------------------------------|
|     |                   3    2   2          3 3 3        4   2        10    |
|o8 = |ideal (x x  - x , x  - x , x x  - x , x x x  - x , x x x  - x , x  x x |
|     |        1 2    3   1    2   1 2    4   1 2 3    5   2 3 4    6   1  3 4|
|     +-----------------------------------------------------------------------|
|     |                   3    2              15        8 5          10       |
|     |ideal (x x  - x , x  - x , x x  - x , x   - x , x x  - x , x x   - x ) |
|     |        1 2    3   1    2   1 3    4   1     5   1 2    6   1 2     7  |
|     +-----------------------------------------------------------------------|
|-----------------------------------------------------------------------------|
|------+                                                                      |
|      |                                                                      |
| - x )|                                                                      |
|    7 |                                                                      |
|------+                                                                      |
|      |                                                                      |
|      |                                                                      |
|      |                                                                      |
|------+                                                                      |
+-----------------------------------------------------------------------------+

See also
========

  * markovBases -- all minimal Markov bases of a
    configuration matrix
  * countMarkov -- the number of minimal Markov bases of a
    configuration matrix

Ways to use randomMarkov:
=========================

  * "randomMarkov(Matrix)"
  * "randomMarkov(Matrix,Ring)"

For the programmer
==================

The object randomMarkov, is a method function with options (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in AllMarkovBases.m2:969:0.

countMarkov -- the number of minimal Markov bases of a configuration matrix
***************************************************************************

  * Usage:
        N = countMarkov A
  * Inputs:
      * A, a matrix (Macaulay2Doc), configuration matrix
  * Optional inputs (Macaulay2Doc),:
      * FiberAlgorithm => a string (Macaulay2Doc), default value
        "fast", Choices are "fast", "decompose", "markov" or "lattice". See
        computeFiber(...,FiberAlgorithm=>...).
  * Outputs:
      * N, an integer (Macaulay2Doc), the number of minimal Markov
        bases of $A$

Description
===========

This method counts all minimal Markov bases of $A$.

+------------------------------------------------------+
|i1 : countMarkov matrix "3,4,5" -- unique Markov basis|
|                                                      |
|o1 = 1                                                |
+------------------------------------------------------+
|i2 : countMarkov matrix "1,2,3"                       |
|                                                      |
|o2 = 2                                                |
+------------------------------------------------------+
|i3 : countMarkov matrix "2,3,5,7,30,31,32"            |
|                                                      |
|o3 = 228960                                           |
+------------------------------------------------------+

This method does not produce all minimal Markov bases, so it is much faster to
use countMarkov A than #markovBases A. This method computes the fiber graphs of
$A$, see fiberGraph. The speed of this computation depends
on the choice of algorithm, which may be specified using the option
FiberAlgorithm. For more details, see
computeFiber(...,FiberAlgorithm=>...).

See also
========

  * markovBases -- all minimal Markov bases of a
    configuration matrix
  * fiberGraph -- generating fibers of a configuration
    matrix
  * computeFiber -- compute a single fiber of
    configuration matrix

Ways to use countMarkov:
========================

  * "countMarkov(Matrix)"

For the programmer
==================

The object countMarkov, is a method function with options (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in AllMarkovBases.m2:910:0.

fiberGraph -- generating fibers of a configuration matrix
*********************************************************

  * Usage:
        G = fiberGraph A
  * Inputs:
      * A, a matrix (Macaulay2Doc), configuration matrix
  * Optional inputs (Macaulay2Doc),:
      * ReturnConnectedComponents => a Boolean value (Macaulay2Doc),
        default value false, if true then return the
        list of connected components of each fiber, otherwise return the whole
        graphs
      * FiberAlgorithm => a string (Macaulay2Doc), default value
        "fast", affects the computation only when
        ReturnConnectedComponents, is true. Choices are "fast",
        "decompose", "markov" or "lattice": "fast" is recommended as the most
        reliably quick option, however, if the generating fibers are
        particularly large, we recommend "decompose" for smaller input matrices
        $A$ and "markov" for larger input matrices $A$. If the values of the
        input matrix $A$ are very large, it is worth trying "lattice".
  * Outputs:
      * G, a list (Macaulay2Doc), a list of graphs, one for each
        generating fiber of A

Description
===========

This function constructs the generating fibers of the configuration matrix $A$.
The fibers are returned as a list of graphs where two vectors in a fiber are
adjacent if their supports have non-trivial intersection.

If the option ReturnConnectedComponents, is false, the
default setting, then the generating fibers are exhaustively searched using a
breadth first search algorithm and vectors in the fibers are added to graph
objects from the package Graphs, with edges added between
two vectors if they have non-trivial support.

If the option ReturnConnectedComponents, is true then,
instead of returning a list of graphs, the function returns a list of the
connected components of each fiber. In this case, an algorithm for the
computation can then be chosen using the FiberAlgorithm,
option and these algorithms are much more efficient than using the breadth
first search algorithm alonside the Graphs, package, which
is used when the option ReturnConnectedComponents, is
false.

+-----------------------------------------------------------------------------+
|i1 : netList fiberGraph matrix "3,4,5"                                       |
|                                                                             |
|     +----------------------+                                                |
|o1 = |Graph{{0, 2, 0} => {}}|                                                |
|     |      {1, 0, 1} => {} |                                                |
|     +----------------------+                                                |
|     |Graph{{0, 1, 1} => {}}|                                                |
|     |      {3, 0, 0} => {} |                                                |
|     +----------------------+                                                |
|     |Graph{{0, 0, 2} => {}}|                                                |
|     |      {2, 1, 0} => {} |                                                |
|     +----------------------+                                                |
+-----------------------------------------------------------------------------+
|i2 : netList fiberGraph matrix "1,2,3"                                       |
|                                                                             |
|     +-------------------------------+                                       |
|o2 = |Graph{{0, 1, 0} => {}}         |                                       |
|     |      {2, 0, 0} => {}          |                                       |
|     +-------------------------------+                                       |
|     |Graph{{0, 0, 1} => {}         }|                                       |
|     |      {1, 1, 0} => {{3, 0, 0}} |                                       |
|     |      {3, 0, 0} => {{1, 1, 0}} |                                       |
|     +-------------------------------+                                       |
+-----------------------------------------------------------------------------+
|i3 : netList fiberGraph(matrix "1,2,3", ReturnConnectedComponents => true,   |
|                                                                             |
|     +----------------------+-----------+                                    |
|o3 = |{{0, 1, 0}}           |{{2, 0, 0}}|                                    |
|     +----------------------+-----------+                                    |
|     |{{1, 1, 0}, {3, 0, 0}}|{{0, 0, 1}}|                                    |
|     +----------------------+-----------+                                    |
|-----------------------------------------------------------------------------|
|FiberAlgorithm => "decompose")                                               |
+-----------------------------------------------------------------------------+
|i4 : netList fiberGraph(matrix "3,4,6,8,12", ReturnConnectedComponents => tru|
|                                                                             |
|     +---------------------------------------------------+-----------------+-|
|o4 = |{{0, 0, 0, 1, 0}}                                  |{{0, 2, 0, 0, 0}}| |
|     +---------------------------------------------------+-----------------+-|
|     |{{4, 0, 0, 0, 0}, {0, 0, 2, 0, 0}, {2, 0, 1, 0, 0}}|{{0, 0, 0, 0, 1}}|{|
|     +---------------------------------------------------+-----------------+-|
|     |{{0, 0, 1, 0, 0}}                                  |{{2, 0, 0, 0, 0}}| |
|     +---------------------------------------------------+-----------------+-|
|-----------------------------------------------------------------------------|
|e, FiberAlgorithm => "fast")                                                 |
|                                                                             |
|---------------------------------+                                           |
|                                 |                                           |
|---------------------------------+                                           |
|{0, 1, 0, 1, 0}, {0, 3, 0, 0, 0}}|                                           |
|---------------------------------+                                           |
|                                 |                                           |
|---------------------------------+                                           |
+-----------------------------------------------------------------------------+

See also
========

  * computeFiber -- compute a single fiber of
    configuration matrix
  * markovBases -- all minimal Markov bases of a
    configuration matrix
  * AllMarkovBases -- computing all minimal Markov bases of a
    configuration matrix

Ways to use fiberGraph:
=======================

  * "fiberGraph(Matrix)"

For the programmer
==================

The object fiberGraph, is a method function with options (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in AllMarkovBases.m2:797:0.

markovBases -- all minimal Markov bases of a configuration matrix
*****************************************************************

  * Usage:
        K = markovBases A
        L = markovBases(A, R)
  * Inputs:
      * A, a matrix (Macaulay2Doc), configuration matrix
      * R, a ring (Macaulay2Doc), ring with one generator for each
        column of $A$
  * Outputs:
      * K, a list (Macaulay2Doc), the minimal Markov bases A
      * L, a list (Macaulay2Doc), ideals in R generated by the
        minimal Markov bases of $A$

Description
===========

This method produces all minimal Markov bases of a given configuration matrix
$A \in \ZZ^{d \times n}$. By default, the output is formatted in the same way
as toricMarkov (FourTiTwo),: each Markov basis is a $k \times
n$ matrix whose rows correspond to the elements of the Markov basis.

+--------------------------------------------------------------+
|i1 : netList markovBases matrix "3,4,5" -- unique Markov basis|
|                                                              |
|     +-----------+                                            |
|o1 = || 1 -2 1  ||                                            |
|     || 3 -1 -1 ||                                            |
|     || 2 1  -2 ||                                            |
|     +-----------+                                            |
+--------------------------------------------------------------+
|i2 : netList markovBases matrix "1,2,3"                       |
|                                                              |
|     +-----------+                                            |
|o2 = || 2 -1 0  ||                                            |
|     || 1 1  -1 ||                                            |
|     +-----------+                                            |
|     || 2 -1 0  ||                                            |
|     || 3 0  -1 ||                                            |
|     +-----------+                                            |
+--------------------------------------------------------------+
|i3 : netList markovBases matrix "1,2,3,4"                     |
|                                                              |
|     +--------------+                                         |
|o3 = || 2 -1 0  0  ||                                         |
|     || 1 1  -1 0  ||                                         |
|     || 0 2  0  -1 ||                                         |
|     +--------------+                                         |
|     || 2 -1 0  0  ||                                         |
|     || 1 1  -1 0  ||                                         |
|     || 1 0  1  -1 ||                                         |
|     +--------------+                                         |
|     || 2 -1 0  0  ||                                         |
|     || 1 1  -1 0  ||                                         |
|     || 2 1  0  -1 ||                                         |
|     +--------------+                                         |
|     || 2 -1 0  0  ||                                         |
|     || 1 1  -1 0  ||                                         |
|     || 4 0  0  -1 ||                                         |
|     +--------------+                                         |
|     || 2 -1 0  0  ||                                         |
|     || 3 0  -1 0  ||                                         |
|     || 0 2  0  -1 ||                                         |
|     +--------------+                                         |
|     || 2 -1 0  0  ||                                         |
|     || 3 0  -1 0  ||                                         |
|     || 1 0  1  -1 ||                                         |
|     +--------------+                                         |
|     || 2 -1 0  0  ||                                         |
|     || 3 0  -1 0  ||                                         |
|     || 2 1  0  -1 ||                                         |
|     +--------------+                                         |
|     || 2 -1 0  0  ||                                         |
|     || 3 0  -1 0  ||                                         |
|     || 4 0  0  -1 ||                                         |
|     +--------------+                                         |
+--------------------------------------------------------------+
|i4 : netList markovBases matrix "1,2,3,4;4,5,6,7"             |
|                                                              |
|     +-------------+                                          |
|o4 = || 1 -2 1  0 ||                                          |
|     || 1 -1 -1 1 ||                                          |
|     || 0 1  -2 1 ||                                          |
|     +-------------+                                          |
+--------------------------------------------------------------+

Similarly to toricMarkov (FourTiTwo), we may also specify a
ring $R$. In this case, the method produces a list of ideals in $R$ with each
ideal generated by a different minimal Markov basis of $A$.

+-----------------------------------------------------------+
|i5 : markovBases(matrix "1,2,3",QQ[x_1,x_2,x_3])           |
|                                                           |
|              2                           2        3       |
|o5 = {ideal (x  - x , x x  - x ), ideal (x  - x , x  - x )}|
|              1    2   1 2    3           1    2   1    3  |
|                                                           |
|o5 : List                                                  |
+-----------------------------------------------------------+
|i6 : gens \ (markovBases(matrix "1,2,3",QQ[x_1,x_2,x_3]))  |
|                                                           |
|o6 = {| x_1^2-x_2 x_1x_2-x_3 |, | x_1^2-x_2 x_1^3-x_3 |}   |
|                                                           |
|o6 : List                                                  |
+-----------------------------------------------------------+

See also
========

  * randomMarkov -- get a random minimal Markov basis

Ways to use markovBases:
========================

  * "markovBases(Matrix)"
  * "markovBases(Matrix,Ring)"

For the programmer
==================

The object markovBases, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in AllMarkovBases.m2:871:0.

pruferSequence -- the edge set of a spanning tree corresponding to a Prüfer sequence
************************************************************************************

  * Usage:
        E = pruferSequence L
  * Inputs:
      * L, a list (Macaulay2Doc), Prüfer sequence, an element of
        $\{0, \dots, n-1\}^{n-2}
  * Outputs:
      * E, a list (Macaulay2Doc), the edge set of the spanning tree
        corresponding $L$

Description
===========

Cayley's formula in graph theory is the result that the number of trees with
vertices labelled from $0$ to $n-1$ is $n^{n-2}$. The Prüfer sequence of a
labelled tree is an element of $\{0, \dots, n-1\}^{n-2}$ and gives an explicit
bijection between the two sets.

This function produces the edge set of the spanning tree corresponding to a
given Prüfer sequence.

+-----------------------------------------------------------------+
|i1 : pruferSequence {2}                                          |
|                                                                 |
|o1 = {set {0, 2}, set {1, 2}}                                    |
|                                                                 |
|o1 : List                                                        |
+-----------------------------------------------------------------+
|i2 : pruferSequence {1,3}                                        |
|                                                                 |
|o2 = {set {0, 1}, set {1, 3}, set {2, 3}}                        |
|                                                                 |
|o2 : List                                                        |
+-----------------------------------------------------------------+
|i3 : pruferSequence {3,3,3,4}                                    |
|                                                                 |
|o3 = {set {0, 3}, set {1, 3}, set {2, 3}, set {4, 3}, set {4, 5}}|
|                                                                 |
|o3 : List                                                        |
+-----------------------------------------------------------------+

Ways to use pruferSequence:
===========================

  * "pruferSequence(List)"

For the programmer
==================

The object pruferSequence, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in AllMarkovBases.m2:827:0.

toricIndispensableSet -- the indispensable set of toric binomials
*****************************************************************

  * Usage:
        S = toricIndispensableSet A
        I = toricIndispensableSet(A, R)
  * Inputs:
      * A, a matrix (Macaulay2Doc), the configuration matrix
      * R, a ring (Macaulay2Doc), with one generator for each
        column of $A$
  * Optional inputs (Macaulay2Doc),:
      * ReturnFiberValues => a Boolean value (Macaulay2Doc),
        default value false, whether to return the fibers of indispensable
        binomials
  * Outputs:
      * S, a matrix (Macaulay2Doc), indispensable set of toric
        binomials
      * I, an ideal (Macaulay2Doc), an ideal in $R$ generated by
        the indispensable binomials

Description
===========

A binomial $x^u - x^v$ of a toric ideal $I_A$ is called indispensable if it
belongs to every minimal Markov basis of A. The set of all indispensable
elements is called the indispensable set, and is often denoted with $S(A)$.

This method computes the indispensable set of a matrix $A$ and returns the
indispensibles as the rows of a matrix. Similarly to markovBases,
if a ring $R$ is supplied, then the result is an ideal generated
by the indispensable set.

+-----------------------------------------------------------------+
|i1 : A = matrix "7,8,9,10";                                      |
|                                                                 |
|              1       4                                          |
|o1 : Matrix ZZ  <-- ZZ                                           |
+-----------------------------------------------------------------+
|i2 : toricIndispensableSet A                                     |
|                                                                 |
|o2 = | 0 1  -2 1  |                                              |
|     | 1 -2 1  0  |                                              |
|     | 1 -1 -1 1  |                                              |
|     | 3 1  -1 -2 |                                              |
|                                                                 |
|              4       4                                          |
|o2 : Matrix ZZ  <-- ZZ                                           |
+-----------------------------------------------------------------+
|i3 : toricIndispensableSet(A, QQ[x_1 .. x_4])                    |
|                                                                 |
|               2            2                         3        2 |
|o3 = ideal (- x  + x x , - x  + x x , - x x  + x x , x x  - x x )|
|               3    2 4     2    1 3     2 3    1 4   1 2    3 4 |
|                                                                 |
|o3 : Ideal of QQ[x ..x ]                                         |
|                  1   4                                          |
+-----------------------------------------------------------------+

If the optional argument ReturnFiberValues is set to true, then the function
instead returns the list of fibers of the indispensable binomials.

+--------------------------------------------------------+
|i4 : toricIndispensableSet(A, ReturnFiberValues => true)|
|                                                        |
|o4 = {{18}, {16}, {17}, {29}}                           |
|                                                        |
|o4 : List                                               |
+--------------------------------------------------------+

The function computes the indispensable elements by checking the connected
components of the fiber graph of $A$; see fiberGraph. A
fiber gives rise to an indispensable element if and only if it has exactly two
connected components and each component contains a single a single point in the
fiber.

See also
========

  * markovBases -- all minimal Markov bases of a
    configuration matrix
  * fiberGraph -- generating fibers of a configuration
    matrix

Ways to use toricIndispensableSet:
==================================

  * "toricIndispensableSet(Matrix)"
  * "toricIndispensableSet(Matrix,Ring)"
  * toricIndispensableSet(Matrix,Matrix) (missing documentation)

For the programmer
==================

The object toricIndispensableSet, is a
method function with options (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in AllMarkovBases.m2:1024:0.

toricUniversalMarkov -- the universal Markov basis
**************************************************

  * Usage:
        U = toricUniversalMarkov A
        I = toricUniversalMarkov(A, R)
  * Inputs:
      * A, a matrix (Macaulay2Doc), the configuration matrix
      * R, a ring (Macaulay2Doc), with one generator for each
        column of $A$
  * Outputs:
      * U, a matrix (Macaulay2Doc), the universal Markov basis of
        $A$
      * I, an ideal (Macaulay2Doc), an ideal in $R$ generated by
        the universal Markov basis of $A$

Description
===========

The universal Markov basis, often denoted $U(A)$, of a configuration matrix $A$
is the union of all minimal Markov bases of $A$. This method computes the
universal Markov basis of $A$ and returns the elements as the rows of a matrix.
Similarly to markovBases, if a ring $R$ is supplied, then
the result is an ideal generated by the universal Markov basis.

+-----------------------------------------------------------------------------+
|i1 : A = matrix "7,8,9,10";                                                  |
|                                                                             |
|              1       4                                                      |
|o1 : Matrix ZZ  <-- ZZ                                                       |
+-----------------------------------------------------------------------------+
|i2 : toricUniversalMarkov A                                                  |
|                                                                             |
|o2 = | -1 2  -1 0  |                                                         |
|     | -1 1  1  -1 |                                                         |
|     | 0  -1 2  -1 |                                                         |
|     | 4  0  -2 -1 |                                                         |
|     | 4  -1 0  -2 |                                                         |
|     | 3  1  -1 -2 |                                                         |
|     | 3  0  1  -3 |                                                         |
|     | 2  2  0  -3 |                                                         |
|                                                                             |
|              8       4                                                      |
|o2 : Matrix ZZ  <-- ZZ                                                       |
+-----------------------------------------------------------------------------+
|i3 : toricUniversalMarkov(A, QQ[x_1 .. x_4])                                 |
|                                                                             |
|             2                       2          4    2     4      2   3      |
|o3 = ideal (x  - x x , x x  - x x , x  - x x , x  - x x , x  - x x , x x  -  |
|             2    1 3   2 3    1 4   3    2 4   1    3 4   1    2 4   1 2    |
|     ------------------------------------------------------------------------|
|        2   3      3   2 2    3                                              |
|     x x , x x  - x , x x  - x )                                             |
|      3 4   1 3    4   1 2    4                                              |
|                                                                             |
|o3 : Ideal of QQ[x ..x ]                                                     |
|                  1   4                                                      |
+-----------------------------------------------------------------------------+

The function computes the universal Markov basis elements using the the fiber
graph of $A$; see fiberGraph. An irreducible binomial $x^u -
x^v$ is an element of the universal Markov basis if and only if $u$ and $v$
belong to different connected components of the fiber graph.

See also
========

  * markovBases -- all minimal Markov bases of a
    configuration matrix
  * fiberGraph -- generating fibers of a configuration
    matrix

Ways to use toricUniversalMarkov:
=================================

  * "toricUniversalMarkov(Matrix)"
  * "toricUniversalMarkov(Matrix,Ring)"

For the programmer
==================

The object toricUniversalMarkov, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in AllMarkovBases.m2:1068:0.

computeFiber -- compute a single fiber of configuration matrix
**************************************************************

  * Usage:
        F = computeFiber(A,b)
  * Inputs:
      * A, a matrix (Macaulay2Doc), configuration matrix
      * b, a vector (Macaulay2Doc), value of fiber
  * Optional inputs (Macaulay2Doc),:
      * ReturnConnectedComponents => a Boolean value (Macaulay2Doc),
        default value false, if true then return the
        list of connected components of the fiber, otherwise return fiber as
        list of vectors
      * FiberAlgorithm => a string (Macaulay2Doc), default value
        "decompose", Choices are "decompose", "markov", "fast" or "lattice":
        when using "decompose", lots of smaller fibers will autmoaticaly be
        computed and stored in A.cache. Thus, when computing lots of fibers for
        one configuration matrix, we recommend "decompose", especially for
        large fibers. "markov" works very similarly to "decompose" and will be
        faster for complicated input matrices with lots of rows and columns.
        Otherwise, "fast" is the best for a one-off computation of a smaller
        fiber and, if the values of the input matrix $A$ are very large, it is
        worth trying "lattice".
  * Outputs:
      * F, a list (Macaulay2Doc), a complete list of vectors in the
        fiber b

Description
===========

This function constructs one fiber $b$ of the configuration matrix $A$, which
is returned as a list of vectors.

The algorithm used to compute the fiber can be one of "decompose", "markov",
"fast" or "lattice" with "decompose" as the default option. All algorithms will
return either the fiber as a list of vectors or a list of the connected
components of the fiber, depending on whether the
ReturnConnectedComponents, option is set to false or true.

When computing lots of fibers for one configuration matrix, we recommend
"decompose", especially for large fibers. "markov" works very similarly to
"decompose" and will be faster for complicated input matrices with lots of rows
and columns. Otherwise, "fast" is the best for a one-off computation of a
smaller fiber and, if the values of the input matrix $A$ are very large, it is
worth trying "lattice".

+-----------------------------------------------------------------------------+
|i1 : computeFiber(matrix "3,5,11", vector {27})                              |
|                                                                             |
|o1 = {| 9 |, | 0 |, | 2 |, | 4 |}                                            |
|      | 0 |  | 1 |  | 2 |  | 3 |                                             |
|      | 0 |  | 2 |  | 1 |  | 0 |                                             |
|                                                                             |
|o1 : List                                                                    |
+-----------------------------------------------------------------------------+
|i2 : netList computeFiber(matrix "3,4,6,8,12", vector {12},                  |
|                                                                             |
|     +---------------+---------------+---------------+                       |
|o2 = |{0, 1, 0, 1, 0}|{0, 3, 0, 0, 0}|               |                       |
|     +---------------+---------------+---------------+                       |
|     |{4, 0, 0, 0, 0}|{0, 0, 2, 0, 0}|{2, 0, 1, 0, 0}|                       |
|     +---------------+---------------+---------------+                       |
|     |{0, 0, 0, 0, 1}|               |               |                       |
|     +---------------+---------------+---------------+                       |
|-----------------------------------------------------------------------------|
|ReturnConnectedComponents => true)                                           |
+-----------------------------------------------------------------------------+
|i3 : computeFiber(matrix "51,52,53,54,55,56", vector {614}, FiberAlgorithm =>|
|                                                                             |
|o3 = {|  0 |, | 0 |, | 10 |, | 11 |}                                         |
|      |  0 |  | 0 |  |  2 |  |  0 |                                          |
|      |  0 |  | 0 |  |  0 |  |  1 |                                          |
|      |  1 |  | 0 |  |  0 |  |  0 |                                          |
|      |  0 |  | 2 |  |  0 |  |  0 |                                          |
|      | 10 |  | 9 |  |  0 |  |  0 |                                          |
|                                                                             |
|o3 : List                                                                    |
|-----------------------------------------------------------------------------|
|"fast")                                                                      |
+-----------------------------------------------------------------------------+
|i4 : computeFiber(matrix "2,4,5,8;7,2,6,1;11,4,3,10", vector{26828,37890,6279|
|                                                                             |
|o4 = {| 3992 |, | 4012 |, | 4004 |, | 3996 |, | 3988 |, | 4016 |, | 4008 |, ||
|      |  918 |  | 3623 |  | 2541 |  | 1459 |  |  377 |  | 4164 |  | 3082 |  ||
|      | 1156 |  |  376 |  |  688 |  | 1000 |  | 1312 |  |  220 |  |  532 |  ||
|      | 1174 |  |  304 |  |  652 |  | 1000 |  | 1348 |  |  130 |  |  478 |  ||
|     ------------------------------------------------------------------------|
|     4000 |}                                                                 |
|     2000 |                                                                  |
|      844 |                                                                  |
|      826 |                                                                  |
|                                                                             |
|o4 : List                                                                    |
|-----------------------------------------------------------------------------|
|2}, FiberAlgorithm => "lattice")                                             |
+-----------------------------------------------------------------------------+

See also
========

  * fiberGraph -- generating fibers of a configuration
    matrix
  * markovBases -- all minimal Markov bases of a
    configuration matrix
  * AllMarkovBases -- computing all minimal Markov bases of a
    configuration matrix

Ways to use computeFiber:
=========================

  * "computeFiber(Matrix,Vector)"

For the programmer
==================

The object computeFiber, is a method function with options (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in AllMarkovBases.m2:738:0.

ReturnFiberValues
*****************

Functions with optional argument named ReturnFiberValues:
=========================================================

  * "toricIndispensableSet(...,ReturnFiberValues=>...)" -- see
    toricIndispensableSet, -- the indispensable set of
    toric binomials

For the programmer
==================

The object ReturnFiberValues (missing documentation) is a symbol (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in currentString:1:380.