[Previous] [Next] [Contents]

## `combinat::integerMatrices` -- integer matrices

#### Introduction

The library `combinat::integerMatrices` provides functions for counting, generating, and manipulating integer matrices of fixed row and column sum.

#### Details

- An integer matrix m with sum of columns c:= (c1,...,ck) and sum of rows l:= (l1,...,ln) where c1+...+ck is equal to l1+...+ln, is a n ×k matrix m=(mi,j), where m1,j+...+mn,j =cj and mi,1+...+mi,k =li.

- Row and column sums of integer matrices are represented in MuPAD by list of nonnegative integers. Integer matrices are represented by the list of its rows.

#### Categories

`Cat::CombinatorialClass`

#### Related Domains

`combinat::integerVectors`

#### Entries

domtype

The MuPAD domain used to represent integer matrices : `DOM_LIST`

#### Method isA: check if an object is an integer matrix

- `isA(obj obj, <columns sum c, row sum l, min part, max part>)`

- Returns `TRUE` is `obj` is an integer matrix. If some of the optional arguments `c`, `l`, min part, max part are given, it also checks for these extra conditions.

#### Method count: number of integer matrices

- `count(columns sum c, row sum l <, min part, max part>)`

- Returns the number of integer matrices of row sum `c` and column sum `l` where the sum of elements in `c` is equal to the sum of elements in `l`. If given, min part and max part bound the entries of the matrices in the result.

#### Method generator: generator for integer matrices

- `generator(columns sum c, row sum l <, min part, max part>)`

- Returns a generator for the integer matrices of row sum `c` and column sum `l` where the sum of elements in `c` is equal to the sum of elements in `l`. If given, min part and max part bound the entries of the matrices in the result.

#### Method list: list of the integer matrices

- `list(columns sum c, row sum l <, min part, max part>)`

- Returns the list of the integer matrices of row sum `c` and column sum `l` where the sum of elements in `c` is equal to the sum of elements in `l`. If given, min part and max part bound the entries of the matrices in the result.

#### Method standard: standardised permutation of the matrix

- `standard(integer matrix m )`

- Returns the standardized permutation of the integer matrix `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 SL Sn / SC where Si is the symmetric group and S(i1,...,ik) = Si1 ×...× Sik. The standardised permutation of the integer matrix `m` is defined as the shortest permutation of the double coset associated to `m`. See 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.

#### Method fromStandard: matrix from its standardised permutation

- `fromStandard(permutation p <, column sum, row sum>)`

- Inverse of the standard function, it returns an integer matrix `m` related to the permutation `p` and verifying the row and column conditions. If no column sums or row sums are given, the smallest matrix is computed.

#### Method transpose: transpose matrix

- `transpose(integer matrix m)`

- Returns the transpose of m.

- With this data representation, there is no way to make a difference between a 0×3 and 0×4 matrix. So, in the special case of matrices with 0 rows or 0 lines, transpose is not involutive.

#### Method printPretty: graphic representation of a matrix

- `printPretty(integer matrix m)`

- Returns a graphic representation of the matrix as rows of boxes filled with the entries of `m`.

#### Method printCompact: graphic representation of a skew partition

- `printCompact(integer matrix m)`

- Same as above, but in a more compact way, where only the entries of `m` appear.

#### Example 1

There are 6 integer matrices of column sum [2,0,5] and row sum [3,2,2]:

    >> combinat::integerMatrices::count([2,0,5],[3,2,2])

                                         6

Here is the list:

    >> combinat::integerMatrices::list([2,0,5],[3,2,2])

          [[[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]]]

Here is a graphic representation of the list:

    >> map(combinat::integerMatrices::list([2,0,5],[3,2,2]),
       combinat::integerMatrices::printPretty)

          -- +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
          |  | 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 |  |
             +---+---+---+  +---+---+---+ --

Here is a more compact graphic representation of the same list:

    >> map(combinat::integerMatrices::list([2,0,5],[3,2,2]),
       combinat::integerMatrices::printCompact)

            -- |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| --

Among these matrices, only three have entries bounded between 0 and 2:

    >> combinat::integerMatrices::count([2, 0, 5], [3, 2, 2], 0, 2)

                                         3

Here is the list:

    >> combinat::integerMatrices::list([2, 0, 5], [3, 2, 2], 0, 2)

          [[[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]]]

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:

    >> g := combinat::integerMatrices::generator([2,0,5],[3,2,2]):
       g(); g(); g(); g(); g(); g(); g();

                         [[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

Typically, this would be used as follows:

    >> g := combinat::integerMatrices::generator([2,0,5],[3,2,2]):
       while (p := g()) <> FAIL do print(p): end:

                         [[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]]

#### Example 2

In this example we check the type of some matrices. All the following tests return `TRUE`:

    >> 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);

                                       TRUE

                                       TRUE

                                       TRUE

                                       TRUE

                                       TRUE

Obviously the entries of the vector `[2,0,5]` are the sums of the rows of the matrix, and the entries of `[3,2,2]` are the sums of the columns.

    >> combinat::integerMatrices::rowSums([[2,0,1], [0,0,2], [0,0,2]]);
       combinat::integerMatrices::columnSums([[2,0,1], [0,0,2], [0,0,2]]);

                                     [3, 2, 2]

                                     [2, 0, 5]

And here are some examples that return either `FALSE` or an error.

    >> 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]);

                                       FALSE

                                       FALSE

                                       FALSE
          Error: Sum mismatch : [4, 0, 5] and [3, 2, 2] [combinat::integ\
          erMatrices::isA]

#### Example 3

To compute the standardised permutation of the matrix [[0,2,1],[1,1,0],[0,1,1]], the MuPAD command is:

    >> combinat::integerMatrices::standard([[0,2,1],[1,1,0],[0,1,1]])

                               [4, 1, 2, 5, 6, 3, 7]

The next integer matrix gives the same standardised permutation:

    >> combinat::integerMatrices::standard([[0,2,1],[1,2,1]])

                               [4, 1, 2, 5, 6, 3, 7]

This integer matrix is the one computed by the `fromStandard` function when there is no more arguments than the permutation:

    >> combinat::integerMatrices::fromStandard([4,1,2,5,6,3,7])

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

It is possible to recover other matrices with the same standardised permutation by giving row sum and column sum conditions:

    >> combinat::integerMatrices::fromStandard([4,1,2,5,6,3,7],
                 [3,2,2], [3,2,2])

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

#### Example 4

We transpose a little 2×2 matrix:

    >> combinat::integerMatrices::transpose([[1, 2], [3, 4]])

                                 [[1, 3], [2, 4]]

Note that when transposing a n×0 matrix, we lose the information about the number of rows:

    >> combinat::integerMatrices::transpose([[], [], []])

                                        []

This is the only case where the `combinat::integerMatrices::transpose` is not involutive:

    >> combinat::integerMatrices::transpose(
           combinat::integerMatrices::transpose([[], [], []]))

                                        []

#### Background

- Except for the trivial cases, counting is done by brute force generation.

#### Super-Domain

`Dom::BaseDomain`

#### Axioms

`Ax::systemRep`

#### Changes

- `combinat::integerMatrices` is a new library

[Previous] [Next] [Contents]

MuPAD Combinat, an open source algebraic combinatorics package