% $Id: integerMatrices.tex,v 1.1.1.8 2004/10/04 17:25:16 nthiery Exp $
\begin{Mhelppage}{integerMatrices}{T.~Gómez-Díaz, F.~Hivert and N.~Thiéry}
  [ImplState=stable,TestState=stable,DocState=stable]
\Mproofread{hivert}{10/2003}{proofread}

\begin{MInfo}
  \eng{integer matrices}
\end{MInfo}

\begin{MIntro}
  \eng{The library \Mthis{} provides functions for counting,
    generating, and manipulating integer matrices of fixed
    row and column sum.}
\end{MIntro}

\MKeywords{combinatorics, integer matrices, row sum condition, column sum condition}

\begin{MDetails}
  \eng{An \emph{integer matrix} $m$ with column sums $c:=
    (c_1,...,c_k)$ and row sums $l:= (l_1,...,l_n)$ where
    $c_1+...+c_k$ is equal to $l_1+...+l_n$, is a $n \times k$ matrix
    $m=(m_{i,j})$ such that $m_{1,j}+\dots+m_{n,j} =c_j$, for all $j$
    and $m_{i,1}+\dots+m_{i,k} =l_i$, for all $i$.}
  
  \eng{An integer matrix is represented in \mupad{} as a list of rows,
    each row being represented by a list of nonnegative integers. Its
    row and column sums are represented by lists of nonnegative
    integers. }
  
  \eng{This representation of integer matrices is ambiguous for
    matrices with zero rows.  Indeed, \Mex{[]} represents
    simultaneously the $0\times0$, $0\times1$, or $0\times5$,
    matrices. Unless the number of columns is provided from the
    context, the convention is to consider \Mex{[]} as the $0\times0$
    matrix.}
\end{MDetails}

\begin{MCategories}
\Mup{Cat::CombinatorialClass}
\end{MCategories}

\MRelatedDomains{combinat::integerVectors}

\begin{MDomEntries}
  \MDomEntry{domtype}
     \eng{The \mupad{} domain used to represent integer matrices : \Mex{DOM_LIST}}
\end{MDomEntries}

\begin{MMethodDetails}{isA}
  \infoEng{check if an object is an integer matrix}%
  \call{\Mtype{obj} obj, \Mopt{\Mtype{columns sum} c, \Mtype{row sum} l, min part, max part}}%
  \eng{Returns \Mex{TRUE} is \Mpar{obj} is an integer matrix. If some of the 
    optional arguments \Mpar{c}, \Mpar{l}, \Mtype{min part}, \Mtype{max part} are given, 
    it also checks for these extra conditions.} 
\end{MMethodDetails}

\begin{MMethodDetails}{nrows}
  \infoEng{number of rows of an integer matrix}%
  \call{\Mtype{integer matrix} m}%
  \eng{Return the number of rows of the integer matrix \Mpar{m}.}
\end{MMethodDetails}

\begin{MMethodDetails}{ncols}
  \infoEng{number of columns of an integer matrix}%
  \call{\Mtype{integer matrix} m}%
  \eng{Return the number of columns of the integer matrix \Mpar{m}.}
\end{MMethodDetails}

\begin{MMethodDetails}{rowSums}
  \infoEng{row sums of an integer matrix}%
  \call{\Mtype{integer matrix} m}%
  \eng{Return the row sums of the integer matrix \Mpar{m}.}
\end{MMethodDetails}

\begin{MMethodDetails}{columnSums}
  \infoEng{column sums of an integer matrix}%
  \call{\Mtype{integer matrix} m}%
  \eng{Return the column sums of the integer matrix \Mpar{m}.}
\end{MMethodDetails}

\begin{MMethodDetails}{isSquare}
  \infoEng{"is square" predicate}%
  \call{\Mtype{integer matrix} m}%
  \eng{Return whether \Mpar{m} is square.}
\end{MMethodDetails}

\begin{MMethodDetails}{count}
  \infoEng{number of integer matrices}%
  \call{\Mtype{columns sum} c, \Mtype{row sum} l \Mopt{, min part, max part}}%
  \eng{Returns the number of integer matrices of row sum \Mpar{c} and column sum \Mpar{l}
    where the sum of elements in \Mpar{c} is equal to the sum of elements in \Mpar{l}.
    If given, \Mtype{min part} and \Mtype{max part} bound the entries of the matrices in the result.}
\end{MMethodDetails}

\begin{MMethodDetails}{generator}
  \infoEng{generator for integer matrices}%
  \call{\Mtype{columns sum} c, \Mtype{row sum} l \Mopt{, min part, max part}}%
    \eng{Returns a generator for the integer matrices of row sum \Mpar{c} and column sum \Mpar{l}
    where the sum of elements in \Mpar{c} is equal to the sum of elements in \Mpar{l}.
    If given, \Mtype{min part} and \Mtype{max part} bound the entries of the matrices in the result.}
\end{MMethodDetails}

\begin{MMethodDetails}{list}
  \infoEng{list of the integer matrices}%
  \call{\Mtype{columns sum} c, \Mtype{row sum} l \Mopt{, min part, max part}}%
  \eng{Returns the list of the integer matrices of row sum \Mpar{c} and column sum \Mpar{l}
    where the sum of elements in \Mpar{c} is equal to the sum of elements in \Mpar{l}.
    If given, \Mtype{min part} and \Mtype{max part} bound the entries of the matrices in the result.}
\end{MMethodDetails}

\begin{MMethodDetails}{standard}
  \infoEng{standardised permutation of the matrix}%
  \call{\Mtype{integer matrix} m }%
  \eng{Returns the standardized permutation of the integer matrix
  \Mpar{m}. An integer matrix of row sum $L$ and column sum $C$ can
  be considered as an element of a coset in the double quotient
  ${\mathfrak S}_L \backslash {\mathfrak S}_n / {\mathfrak S}_C$
  where ${\mathfrak S}_i$ is the symmetric group and
  ${\mathfrak S}_{(i_1,\dots,i_k)} = {\mathfrak S}_{i_1} \times \dots \times
  {\mathfrak S}_{i_k}$. The standardised permutation of the integer matrix
  \Mpar{m} is defined as the shortest permutation of the double coset
  associated to \Mpar{m}.
  See \textit{NonCommutative Symmetric Functions IV: Free Quasi-Symmetric
  Functions and Related Algebras}, G. Duchamp, F. Hivert and J.-Y. Thibon,
  International Journal of Algebra and Computation, Vol. 12, No. 5 (2002) 671-717.} 
\end{MMethodDetails}

\begin{MMethodDetails}{fromStandard}
  \infoEng{matrix from its standardised permutation}%
  \call{\Mtype{permutation} p \Mopt{, column sum, row sum}}%
  \eng{Inverse of the standard function, it returns an integer matrix \Mpar{m}
    related to the permutation \Mpar{p} and verifying the row and column
    conditions. If no column sums or row sums are given, the smallest matrix is
    computed.}
    
\end{MMethodDetails}

\begin{MMethodDetails}{transpose}
  \infoEng{transpose matrix}%
  \call{\Mtype{integer matrix} m}%
  \eng{Returns the transpose of m.}
  
  \eng{\Mwarn{With this data representation, there is no way to make a
      difference between a $0\times 3$ and $0\times4$ matrix. So, in
      the special case of matrices with $0$ rows or $0$ lines,
      transpose is not involutive.}}
\end{MMethodDetails}

\begin{MMethodDetails}{printPretty}
  \infoEng{graphic representation of a matrix}
  \call{\Mtype{integer matrix} m}%
  \eng{Returns a graphic representation of the matrix
       as rows of boxes filled with the entries of \Mpar{m}.}
\end{MMethodDetails}

\begin{MMethodDetails}{printCompact}
  \infoEng{graphic representation of a skew partition}
  \call{\Mtype{integer matrix} m}%
  \eng{Same as above, but in a more compact way, where only the
       entries of \Mpar{m} appear.}
\end{MMethodDetails}

\begin{MExample}{im-basic}
  \eng{There are $6$ integer matrices of column sum $[2,0,5]$ and row sum $[3,2,2]$:}
  \begin{Mexin}
combinat::integerMatrices::count([2,0,5],[3,2,2])
  \end{Mexin}
  \begin{Mexout}
                               6
  \end{Mexout}

  \eng{Here is the list:}
  \begin{Mexin}
combinat::integerMatrices::list([2,0,5],[3,2,2])
  \end{Mexin}
  \begin{Mexout}
[[[2, 0, 1], [0, 0, 2], [0, 0, 2]],

   [[1, 0, 2], [1, 0, 1], [0, 0, 2]],

   [[1, 0, 2], [0, 0, 2], [1, 0, 1]],

   [[0, 0, 3], [2, 0, 0], [0, 0, 2]],

   [[0, 0, 3], [1, 0, 1], [1, 0, 1]],

   [[0, 0, 3], [0, 0, 2], [2, 0, 0]]]
  \end{Mexout}

  \eng{Here is a graphic representation of the list:}
  \begin{Mexin}
map(combinat::integerMatrices::list([2,0,5],[3,2,2]),
combinat::integerMatrices::printPretty)
  \end{Mexin}
  \begin{Mexout}
-- +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
|  | 2 | 0 | 1 |  | 1 | 0 | 2 |  | 1 | 0 | 2 |  | 0 | 0 | 3 |
|  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
|  | 0 | 0 | 2 |, | 1 | 0 | 1 |, | 0 | 0 | 2 |, | 2 | 0 | 0 |,
|  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
|  | 0 | 0 | 2 |  | 0 | 0 | 2 |  | 1 | 0 | 1 |  | 0 | 0 | 2 |
-- +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+

   +---+---+---+  +---+---+---+ --
   | 0 | 0 | 3 |  | 0 | 0 | 3 |  |
   +---+---+---+  +---+---+---+  |
   | 1 | 0 | 1 |, | 0 | 0 | 2 |  |
   +---+---+---+  +---+---+---+  |
   | 1 | 0 | 1 |  | 2 | 0 | 0 |  |
   +---+---+---+  +---+---+---+ --
  \end{Mexout}

  \eng{Here is a more compact graphic representation of the same list:}
  \begin{Mexin}
map(combinat::integerMatrices::list([2,0,5],[3,2,2]),
combinat::integerMatrices::printCompact)
  \end{Mexin}
  \begin{Mexout}
  -- |2|0|1|  |1|0|2|  |1|0|2|  |0|0|3|  |0|0|3|  |0|0|3| --
  |  |0|0|2|, |1|0|1|, |0|0|2|, |2|0|0|, |1|0|1|, |0|0|2|  |
  -- |0|0|2|  |0|0|2|  |1|0|1|  |0|0|2|  |1|0|1|  |2|0|0| --
  \end{Mexout}

  \eng{Among these matrices, only three have entries bounded between 0 and 2:}

  \begin{Mexin}
combinat::integerMatrices::count([2, 0, 5], [3, 2, 2], 0, 2)
  \end{Mexin}
  \begin{Mexout}
                               3
  \end{Mexout}

  \eng{Here is the list:}

  \begin{Mexin}
combinat::integerMatrices::list([2, 0, 5], [3, 2, 2], 0, 2)
  \end{Mexin}
  \begin{Mexout}
[[[2, 0, 1], [0, 0, 2], [0, 0, 2]],

   [[1, 0, 2], [1, 0, 1], [0, 0, 2]],

   [[1, 0, 2], [0, 0, 2], [1, 0, 1]]]
  \end{Mexout}
  
  \eng{If you want to run through the integer matrices verifying some row and
    column sum conditions you can generate them one by one to save memory:}
  \begin{Mexin}
g := combinat::integerMatrices::generator([2,0,5],[3,2,2]):
g(); g(); g(); g(); g(); g(); g();
  \end{Mexin}
  \begin{Mexout}
               [[2, 0, 1], [0, 0, 2], [0, 0, 2]]

               [[1, 0, 2], [1, 0, 1], [0, 0, 2]]

               [[1, 0, 2], [0, 0, 2], [1, 0, 1]]

               [[0, 0, 3], [2, 0, 0], [0, 0, 2]]

               [[0, 0, 3], [1, 0, 1], [1, 0, 1]]

               [[0, 0, 3], [0, 0, 2], [2, 0, 0]]

                             FAIL
  \end{Mexout}

  \eng{Typically, this would be used as follows:}
  \begin{Mexin}
g := combinat::integerMatrices::generator([2,0,5],[3,2,2]):
while (p := g()) <> FAIL do print(p): end:
  \end{Mexin}
  \begin{Mexout}
               [[2, 0, 1], [0, 0, 2], [0, 0, 2]]

               [[1, 0, 2], [1, 0, 1], [0, 0, 2]]

               [[1, 0, 2], [0, 0, 2], [1, 0, 1]]

               [[0, 0, 3], [2, 0, 0], [0, 0, 2]]

               [[0, 0, 3], [1, 0, 1], [1, 0, 1]]

               [[0, 0, 3], [0, 0, 2], [2, 0, 0]]
  \end{Mexout}
\end{MExample}

\begin{MExample}{im-isA}
  \eng{In this example we check the type of some matrices. All the following
       tests return \Mex{TRUE}:}
  \begin{Mexin}
combinat::integerMatrices::isA([[2,0,1], [0,0,2], [0,0,2]]);
combinat::integerMatrices::isA([[2,0,1], [0,0,2], [0,0,2]],
    [2,0,5]);
combinat::integerMatrices::isA([[2,0,1], [0,0,2], [0,0,2]],
    [2,0,5], [3,2,2]);
combinat::integerMatrices::isA([[2,0,1], [0,0,2], [0,0,2]],
    [2,0,5], [3,2,2], 0);
combinat::integerMatrices::isA([[2,0,1], [0,0,2], [0,0,2]],
    [2,0,5], [3,2,2], 0, 2);
  \end{Mexin}
  \begin{Mexout}
                             TRUE

                             TRUE

                             TRUE

                             TRUE

                             TRUE
  \end{Mexout}
  \eng{Obviously the entries of the vector \Mex{[2,0,5]} are the sums of the
       rows of the matrix, and the entries of \Mex{[3,2,2]} are the sums of the
       columns.}
  \begin{Mexin}
combinat::integerMatrices::rowSums([[2,0,1], [0,0,2], [0,0,2]]);
combinat::integerMatrices::columnSums([[2,0,1], [0,0,2], [0,0,2]]);
  \end{Mexin}
  \begin{Mexout}
                           [3, 2, 2]

                           [2, 0, 5]
  \end{Mexout}

  \eng{And here are some examples that return either \Mex{FALSE} or an
       error.}
  \begin{Mexin}
combinat::integerMatrices::isA([[2,0,1], [0,0,2], [0,0,2]],
    [4,0,5]);
combinat::integerMatrices::isA([[2,0,1], [0,0,2], [0,0,2]],
    [2,0,5], [3,2,2], 1);
combinat::integerMatrices::isA([[2,0,1], [0,0,2], [0,0,2]],
    [2,0,5], [3,2,2], 0, 1);
combinat::integerMatrices::isA([[2,0,1], [0,0,2], [0,0,2]],
    [4,0,5], [3,2,2]);
  \end{Mexin}
  \begin{Mexout}
                             FALSE

                             FALSE

                             FALSE
Error: Sum mismatch : [4, 0, 5] and [3, 2, 2] [combinat::integ\
erMatrices::isA]
  \end{Mexout}
\end{MExample}

\begin{MExample}{im-standard}
  \eng{\begin{sloppypar}
    To compute the standardised permutation of the matrix
    $[[0,2,1],[1,1,0],[0,1,1]]$, the \mupad\ command is:
       \end{sloppypar}}
  \begin{Mexin}
combinat::integerMatrices::standard([[0,2,1],[1,1,0],[0,1,1]])
  \end{Mexin}
  \begin{Mexout}
                     [4, 1, 2, 5, 6, 3, 7]
  \end{Mexout}
  \eng{The next integer matrix gives the same standardised permutation:}
  \begin{Mexin}
combinat::integerMatrices::standard([[0,2,1],[1,2,1]])
  \end{Mexin}
  \begin{Mexout}
                     [4, 1, 2, 5, 6, 3, 7]
  \end{Mexout}
  \eng{This integer matrix is the one computed by the
    \Mup[combinat,integerMatrices]{fromStandard}
    function when there is no more arguments than the permutation:}
  \begin{Mexin}
combinat::integerMatrices::fromStandard([4,1,2,5,6,3,7])
  \end{Mexin}
  \begin{Mexout}
                    [[0, 2, 1], [1, 2, 1]]
  \end{Mexout}
  \eng{It is possible to recover other matrices with the same
    standardised permutation by giving row sum and column sum conditions:}
  \begin{Mexin}
combinat::integerMatrices::fromStandard([4,1,2,5,6,3,7],
          [3,2,2], [3,2,2])
  \end{Mexin}
  \begin{Mexout}
               [[2, 0, 1], [1, 1, 0], [0, 1, 1]]
  \end{Mexout}
\end{MExample}

\begin{MExample}{transpose}
  \eng{We transpose a little $2\times 2$ matrix:}
  \begin{Mexin}
combinat::integerMatrices::transpose([[1, 2], [3, 4]])
  \end{Mexin}
  \begin{Mexout}
                       [[1, 3], [2, 4]]
  \end{Mexout}
  
  \eng{Note that when transposing a $n\times 0$ matrix, we lose the
    information about the number of rows:}
  \begin{Mexin}
combinat::integerMatrices::transpose([[], [], []])
  \end{Mexin}
  \begin{Mexout}
                              []
  \end{Mexout}
  \eng{This is the only case where the
    \Mup[combinat,integerMatrices]{combinat::integerMatrices::transpose} is not involutive:}
  \begin{Mexin}
combinat::integerMatrices::transpose(
    combinat::integerMatrices::transpose([[], [], []]))
  \end{Mexin}
  \begin{Mexout}
                              []
  \end{Mexout}
\end{MExample}

% -----------------------------------------------------------
% --------- Superdomain / Axioms                   ----------
% -----------------------------------------------------------

\begin{MBackground}
  \eng{\Mwarn{Except for the trivial cases, counting is done by brute
      force generation.}}
\end{MBackground}

\MSuperDomain{Dom::BaseDomain}

\begin{MAxioms}
  \Mup{Ax::systemRep}
\end{MAxioms}

\begin{MChanges}
  \version{3.0}%
  \eng[New library]{\Mthis{} is a new library}
\end{MChanges}

\end{Mhelppage}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: main
%%% End: 
