combinat::integerMatrices
--
integer matrices
The library combinat::integerMatrices
provides functions for counting,
generating, and manipulating integer matrices of fixed
row and column sum.
Cat::CombinatorialClass
The MuPAD domain used to represent integer matrices : DOM_LIST
isA(obj obj, <columns sum c, row sum l, min part, max part>)
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.
count(columns sum c, row sum l <, min part, max part>)
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.
generator(columns sum c, row sum l <, min part, max part>)
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.
list(columns sum c, row sum l <, min part, max part>)
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.
standard(integer matrix m )
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.
fromStandard(permutation p <, column sum, row sum>)
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.
transpose(integer matrix 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.
printPretty(integer matrix m)
m
.
printCompact(integer matrix m)
m
appear.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]]
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]
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]]
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([[], [], []]))
[]
Except for the trivial cases, counting is done by brute force generation.
Ax::systemRep
combinat::integerMatrices
is a new library
MuPAD Combinat, an open source algebraic combinatorics package