%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % 4ti2 User Guide, Beginner's guide % % $Id$ % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \chapter{Beginner's guide} \label{Chapter: Beginner's guide} %\FourTiTwo{} is a software package that is specifically tailored for %certain computational problems on linear spaces and integer %lattices. In this part, we use a few sample problems to introduce you to the basic functionality of \FourTiTwo{}. After working through this part, you should know about \emph{linear systems} and their encodings in \FourTiTwo{}, and should be able to do computations using the following functions: \begin{itemize} \item \File{qsolve}, \File{rays}, \File{circuits} \item \File{zsolve}, \File{hilbert}, \File{graver}, \File{ppi} \item \File{minimize}, \File{groebner}, \File{normalform} \item \File{genmodel}, \File{markov} \end{itemize} \section{Linear systems and their encodings} In this section you learn about the data structure \File{linear system} and how it is specified in \FourTiTwo. \subsection{Linear systems and integer linear systems} In \FourTiTwo, a \emph{linear system} is defined by $d$ constraints $Ax\sim b$ in $n$ unknowns $x$, where each constraint is either $\leq$, $=$ or $\geq$, that is $\sim\;\in\{\leq,=,\geq\}^d$. Moreover, one may specify sign constraints on the variables that need to be respected in an explicit continuous/integer representation of all solutions. There is no particular difference in \FourTiTwo{} between a linear system and an integer linear system. Currently, the user chooses between one of the two by calling the appropriate functions on the linear system. \subsection{Specifying a linear system in \FourTiTwo} In order to use a linear system as input, we need to specify its parts to \FourTiTwo. As our running example, take \[ \left( \begin{array}{cccc} 1 & 1 & 1 & 1\\ 1 & 2 & 3 & 4\\ \end{array} \right)x \begin{array}{c} \leq\\ \leq\\ \end{array} \left( \begin{array}{c} 6\\ 10\\ \end{array} \right) \] with sign constraints $(1,2,2,0)$, which we will explain below. First, we have to give our problem a project name, say \File{PROJECT}. \begin{itemize} \item The matrix $A$ has to be put into the file \File{PROJECT.mat}. \begin{myverbatim} 2 4 1 1 1 1 1 2 3 4 \end{myverbatim} \item The relations $\sim$ then have to be specified in \File{PROJECT.rel}. \begin{myverbatim} 1 2 < < \end{myverbatim} \item The right-hand side vector goes into \File{PROJECT.rhs}. \begin{myverbatim} 1 2 6 10 \end{myverbatim} \item And finally, the sign constraints end up in \File{PROJECT.sign}. \begin{myverbatim} 1 4 1 2 2 0 \end{myverbatim} \end{itemize} {\bf Note.} \begin{itemize} \item The input files all have the format of a matrix, preceded by the matrix dimensions. As the dimensions already specify how many symbols have to be read, the matrix could also be given in only one line or even in many lines of different lengths. \item In \FourTiTwo{} version 1.3.1 and later, all appearing numbers have to be integers. \item Consequently, this implies that, at the moment, \File{qsolve} only supports homogeneous linear systems, that is systems with $b=0$, since minimal inhomogeneous solutions could have rational components. \end{itemize} \subsection{What does an explicit solution to linear systems look like?} If the system is solved over $\R$ (using \File{qsolve}), \FourTiTwo{} returns two sets of integer vectors: \begin{itemize} \item a set $H$ of support-minimal homogeneous solutions, and \item a set $F$ defining the linear vector space the solution set lives in. \end{itemize} As only \emph{homogeneous} linear systems are supported in this version of \FourTiTwo, no list of minimal inhomogeneous solutions is computed. Any solution $z$ of the linear system can now be written as \begin{equation}\label{Equation: Continuous representation} z=\sum \alpha_j h_j+ \sum \beta_k f_k \end{equation} with $h_j\in H$, $f_k\in F$, and $\alpha_j\geq 0$. If the system is solved over $\Z$ (using \File{zsolve}), \FourTiTwo{} returns three sets of integer vectors: \begin{itemize} \item a set $H$ of minimal homogeneous \emph{integer} solutions, \item a set $I$ of minimal inhomogeneous \emph{integer} solutions, and \item a set $F$ defining the sublattice of $\Z^n$ the solution set lives in. \end{itemize} Any solution $z$ of the linear system can now be written as \begin{equation}\label{Equation: Integer representation} z=i+ \sum \alpha_j h_j+\sum \beta_k f_k \end{equation} for some $i\in I$ and with $h_j\in H$, $f_j\in F$, and $\alpha_j\in\Z_+$. {\bf Sign file.} Let us finally clarify what the sign file \File{PROJECT.sign} is good for. The sign file may declare a variable to be non-negative ($1$), to be non-positive ($-1$), or to consider both cases independently and unite the answers ($2$). If a nonzero sign has been assigned to a variable, the explicit representations (\ref{Equation: Continuous representation}) and (\ref{Equation: Integer representation}) above of a solution $z$ have to respect the sign on that variable. The default setting for each variable is $0$ (when using \File{qsolve} and \File{zsolve}), that is, the sign need not be respected in the explicit representation. In our example above, the first variable is declared to be non-negative, the second and the third one expand to $2\cdot 2=4$ orthant constraints, and the fourth variable is unconstrained. Note, however, that \FourTiTwo{} does \emph{not} decompose the problem internally into the four problems with sign patterns $(1,1,1,0)$, $(1,1,-1,0)$, $(1,-1,1,0)$, and $(1,-1,-1,0)$, but deals with them more efficiently at the same time. \section{Brief tutorial} \subsection{Solving linear systems over $\Z$ with \File{zsolve}} In this example you learn about the function % s \File{qsolve} and \File{zsolve}. Let us have a look at the linear system %%%% \[ %%%% \begin{array}{rcrcrlcl} %%%% x & - & y & \leq & 2\\ %%%% -3x & + & y & \leq & 1\\ %%%% x & + & y & \geq & 1\\ %%%% & & y & \geq & 0\\ %%%% \end{array} %%%% \] %%%% and let us solve it over $\R$, we have to create the files encoding %%%% the linear system. Let us call our project \File{system}. Then the %%%% input files look as follows: %%%% \begin{center} %%%% \begin{tabular}{|l|l|l|l|} %%%% \hline %%%% \text{ system.mat } & \text{ system.rel } & \text{ system.rhs } & \text{ system.sign }\\ %%%% \hline %%%% $\begin{array}{rrrr}& 3 & 2 & \\& 1 & -1\\& -3 & 1\\& 1 & 1 &\\ \end{array}$ & %%%% $\begin{array}{rrrrr}& 1 & 3 & \\& < & < & > & \\ \\ \\\end{array}$ & %%%% $\begin{array}{rrrrr}& 1 & 3 & \\& 2 & 1 & 1 & \\ \\ \\\end{array}$ & %%%% $\begin{array}{rrrr}& 1 & 2 & \\& 0 & 1 & \\ \\ \\\end{array}$\\ %%%% \hline %%%% \end{tabular} %%%% \end{center} %%%% and then call %%%% \begin{center} %%%% {\tt ./qsolve system} %%%% \end{center} %%%% This call creates three files %%%% \begin{center} %%%% \begin{tabular}{|l|l|l|} %%%% \hline %%%% \text{ system.qinhom } & \text{ system.qhom } & \text{ system.qfree }\\ %%%% \hline %%%% $\begin{array}{rrrr}& 3 & 2 &\\& 0 & 1 &\\& 0 & 2 &\\& 1 & 0 &\\\end{array}$ & %%%% $\begin{array}{rrrr}& 2 & 2 &\\& 1 & 1 &\\& 1 & 3 & \\ \\\end{array}$ & %%%% $\begin{array}{rrrr}& 0 & 2 & \\ \\ \\ \\ \end{array}$\\ %%%% \hline %%%% \end{tabular} %%%% \end{center} %%%% which correspond to the explicit description of all solutions: %%%% \begin{center} %%%% \begin{tabular}{cc} %%%% \emph{Feasible solutions} & \emph{Computed representation}\\ %%%% \input{feasible_LP.pdf_t} & \input{solved_LP.pdf_t} \\ %%%% \end{tabular} %%%% \end{center} %%%% \[ %%%% \conv\left({1\choose 0},{2\choose 0},{0\choose 1}\right) + \cone\left({1\choose 1},{1\choose 3}\right). %%%% \] %%%% Note that in the second picture above, the three colored cones are %%%% only a simplification and shall visualize the covering of the %%%% feasible region by infinitely many shifted copies of the cone %%%% \[ %%%% \cone\left({1\choose 1},{1\choose 3}\right), %%%% \] %%%% one appended to each point in %%%% \[ %%%% \conv\left({1\choose 0},{2\choose 0},{0\choose 1}\right). %%%% \] %%%% Let us now turn to the integer situation, that is, let us solve the system \[ \begin{array}{rcrcrlcl} x & - & y & \leq & 2\\ -3x & + & y & \leq & 1\\ x & + & y & \geq & 1\\ & & y & \geq & 0\\ \end{array} \] over $\Z$. %% As the linear system itself is unchanged, we can use the %% same input files as above in order to specify the linear system. We have to create the files encoding the linear system. Let us call our project \File{system}. Then the input files look as follows: \begin{center} \begin{tabular}{|l|l|l|l|} \hline \text{ system.mat } & \text{ system.rel } & \text{ system.rhs } & \text{ system.sign }\\ \hline $\begin{array}{rrrr}& 3 & 2 & \\& 1 & -1\\& -3 & 1\\& 1 & 1 &\\ \end{array}$ & $\begin{array}{rrrrr}& 1 & 3 & \\& < & < & > & \\ \\ \\\end{array}$ & $\begin{array}{rrrrr}& 1 & 3 & \\& 2 & 1 & 1 & \\ \\ \\\end{array}$ & $\begin{array}{rrrr}& 1 & 2 & \\& 0 & 1 & \\ \\ \\\end{array}$\\ \hline \end{tabular} \end{center} Then % , however, we call \begin{center} {\tt 4ti2-zsolve system} \end{center} This call creates two files \begin{center} \begin{tabular}{|l|l|} \hline \text{ system.zinhom } & \text{ system.zhom } %%%% & \text{ system.zfree } \\ \hline $\begin{array}{rrrr}& 4 & 2 &\\& 0 & 1 &\\& 2 & 0 &\\& 1 & 0 &\\ & 1 & 1 &\\\end{array}$ & $\begin{array}{rrrr}& 3 & 2 &\\& 1 & 1 &\\& 1 & 2 &\\& 1 & 3 & \\ \\\end{array}$ %% $\begin{array}{rrrr}& 0 & 2 & \\ \\ \\ \\ \\ \end{array}$ \\ \hline \end{tabular} \end{center} which correspond to the explicit description of all integer solutions: \begin{center} \begin{tabular}{cc} \emph{Feasible solutions} & \emph{Computed representation}\\ \input{feasible.pdf_t} & \input{solved_IP.pdf_t} \\ \end{tabular} \end{center} \[ \left\{{1\choose 0},{2\choose 0},{0\choose 1},{1\choose 1}\right\} + \monoid\left({1\choose 1},{1\choose 2},{1\choose 3}\right). \] Note that in the pictures above, we are only interested in the \emph{lattice points} inside the colored regions! The full regions are colored only for the purpose of visualizing the covering of all feasible integer solutions by finitely many shifted copies of the monoid \[ \monoid\left({1\choose 1},{1\choose 2},{1\choose 3}\right). \] \subsection{Solving linear systems over $\Q$ with \File{qsolve}} \File{qsolve} solves linear systems over $\Q$; however, note that it only supports homogeneous linear systems, that is, systems with $b=0$. %%% We should have an example here. \begin{center} {\tt 4ti2-qsolve system} \end{center} This call creates files \begin{center} \begin{tabular}{|l|l|} \hline \text{ system.qhom } & \text{ system.qfree }\\ \hline \end{tabular} \end{center} To solve an inhomogeneous system $Ax=b$, $x\geq0$, you (still) need to do some work yourself: \begin{enumerate} \item Solve system $Ax-bu=0$, $x\geq 0$, $u\geq 0$ using \File{qsolve}. \item Keep those solutions with $u=0$. (These generate the recession cone (of unbounded directions). \item Normalize those solutions with $u>0$ to have $u=1$ (by dividing the vector by~$u$). Be aware that this could create rational numbers. \item Drop the $u$-component. \end{enumerate} Any solution to $Ax=b$, $x\geq 0$ can then be obtained by adding one solution from 3.\ to a nonnegative linear combination of solutions from 2. \subsection{Computing extreme rays and Hilbert bases} In this example you learn about the functions \File{rays} and \File{hilbert}. (They are convenient versions of \File{qsolve} and \File{zsolve} for particular cases.) Let us consider the set of magic $3\times 3$ squares with non-negative real entries, that is, the set of all $3\times 3$ arrays with non-negative real entries whose row sums, column sums, and main diagonal sums all add up to the same number, the magic constant of the square. \vspace{-0.3cm} \begin{center} \input{magicsqs.pdf_t} \end{center} \vspace{-0.4cm} Clearly, addition of two magic squares gives another magic square, as well as does multiplication of a magic square by a non-negative number. Therefore, we may talk about the \emph{cone} of magic $3\times 3$ squares. In fact, this cone is a pointed rational polyhedral cone described by the linear system \begin{eqnarray*} x_{11}+x_{12}+x_{13} & = & x_{21}+x_{22}+x_{23}\\ & = & x_{31}+x_{32}+x_{33}\\ & = & x_{11}+x_{21}+x_{31}\\ & = & x_{12}+x_{22}+x_{32}\\ & = & x_{13}+x_{23}+x_{33}\\ & = & x_{11}+x_{22}+x_{33}\\ & = & x_{31}+x_{22}+x_{13}\\ & & x_{ij} \geq 0,\;\;\; \text{ for all } i,j=1,2,3. \end{eqnarray*} Bringing all $x_{ij}$ to the left-hand side of these equations, the matrix $A_{3\times 3}$ defining this linear system is \[ A_{3\times 3}=\left( \begin{array}{rrrrrrrrr} 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\\ \end{array} \right). \] Below, we will deal with the more interesting case of \emph{integer} magic squares. For the moment, however, we wish to compute the extreme rays of the magic square cone $\{z:A_{3\times 3}z=0,z\geq 0\}$. %%%% In test-suite, this is test/rays/33} In order to call the function \File{rays}, we only have to create one file, say \File{magic3x3.mat}, in which we specify the problem matrix $A_{3\times 3}$. The remaining data is set by default to "equations only", to "homogeneous system", and to "all variables are non-negative". Note that we are allowed to change these defaults (except homogeneity) by specifying data in \File{magic3x3.rel} and \File{magic3x3.sign} \begin{center} \begin{tabular}{|l|} \hline \text{ magic3x3.mat } \\ \hline $\begin{array}{rrrrrrrrrrr} & 7 & 9 & & & & & & & & \\ & 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 & \\ \end{array}$\\ \hline \end{tabular} \end{center} Now we call \begin{center} {\tt 4ti2-rays magic3x3} \end{center} which creates the single file \begin{center} \begin{tabular}{|l|} \hline \text{ magic3x3.ray }\\ \hline $\begin{array}{rrrrrrrrrrr}& 4 & 9 &&&&&&&&\\ & 0 & 2 & 1 & 2 & 1 & 0 & 1 & 0 & 2 & \\ & 1 & 2 & 0 & 0 & 1 & 2 & 2 & 0 & 1 & \\ & 2 & 0 & 1 & 0 & 1 & 2 & 1 & 2 & 0 & \\ & 1 & 0 & 2 & 2 & 1 & 0 & 0 & 2 & 1 & \\\end{array}$\\ \hline \end{tabular} \end{center} that corresponds to the four extremal rays of the $3\times 3$ magic square cone: \vspace{-0.3cm} \begin{center} \input{magicsqs_ray.pdf_t} \end{center} \vspace{-0.4cm} Every magic $3\times 3$ square is a non-negative linear combination of these four magic squares. If we turn now to \emph{integer} magic squares, we are looking for a Hilbert basis of the $3\times 3$ magic square cone. As the default settings for \File{hilbert} are the same as for \File{rays}, we can use the same input file %%%% In test-suite, this is test/hilbert/magic33 \begin{center} \begin{tabular}{|l|} \hline \text{ magic3x3.mat } \\ \hline $\begin{array}{rrrrrrrrrrr} & 7 & 9 & & & & & & & & \\ & 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 & \\ \end{array}$\\ \hline \end{tabular} \end{center} for this computation. However, to compute the Hilbert basis, we call \begin{center} {\tt 4ti2-hilbert magic3x3} \end{center} which creates the single output file \begin{center} \begin{tabular}{|l|} \hline \text{ magic3x3.hil }\\ \hline $\begin{array}{rrrrrrrrrrr}& 5 & 9 &&&&&&&&\\ & 0 & 2 & 1 & 2 & 1 & 0 & 1 & 0 & 2 & \\ & 1 & 2 & 0 & 0 & 1 & 2 & 2 & 0 & 1 & \\ & 2 & 0 & 1 & 0 & 1 & 2 & 1 & 2 & 0 & \\ & 1 & 0 & 2 & 2 & 1 & 0 & 0 & 2 & 1 & \\ & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \\\end{array}$\\ \hline \end{tabular} \end{center} that corresponds to the five elements in the minimal Hilbert basis of the $3\times 3$ magic square cone: \vspace{-0.3cm} \begin{center} \input{magicsqs_hil.pdf_t} \end{center} \vspace{-0.4cm} Every integer magic $3\times 3$ square is a non-negative \emph{integer} linear combination of these five integer magic squares. Note that the all-$1$ square is in the interior of the magic square cone. See \cite[section 3.8]{deloera-hemmecke-koeppe:book} or \cite{Hemmecke:2003} for details on the algorithm implemented. \subsection{Computing circuits and Graver bases} In this example you learn about the functions \File{graver}, \File{ppi}, and \File{circuits}. As an example of a Graver basis computation, let us compute the primitive partition identities of order $n=4$. Before we do the simple computation, let us explain what a primitive partition identity is. A \important{partition identity} is any identity of the form \[ a_1+\ldots+a_k=b_1+\ldots+b_l \] with (generally not distinct) integer numbers $0