[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

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

Method count: number of integer matrices

Method generator: generator for integer matrices

Method list: list of the integer matrices

Method standard: standardised permutation of the matrix

Method fromStandard: matrix from its standardised permutation

Method transpose: transpose matrix

Method printPretty: graphic representation of a matrix

Method printCompact: graphic representation of a skew partition

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

Super-Domain

Dom::BaseDomain

Axioms

Ax::systemRep

Changes

[Previous] [Next] [Contents]


MuPAD Combinat, an open source algebraic combinatorics package