Counting, generating, and manipulating non-negative integer matrices¶
Counting, generating, and manipulating non-negative integer matrices with prescribed row sums and column sums.
AUTHORS:
- Franco Saliola
-
class
sage.combinat.integer_matrices.
IntegerMatrices
(row_sums, column_sums)¶ Bases:
sage.structure.unique_representation.UniqueRepresentation
,sage.structure.parent.Parent
The class of non-negative integer matrices with prescribed row sums and column sums.
An integer matrix
with column sums
and row sums
where
is equal to
, is a
matrix
such that
, for all
and
, for all
.
EXAMPLES:
There are
integer matrices with row sums
and column sums
:
sage: from sage.combinat.integer_matrices import IntegerMatrices sage: IM = IntegerMatrices([3,2,2], [2,5]); IM Non-negative integer matrices with row sums [3, 2, 2] and column sums [2, 5] sage: IM.list() [ [2 1] [1 2] [1 2] [0 3] [0 3] [0 3] [0 2] [1 1] [0 2] [2 0] [1 1] [0 2] [0 2], [0 2], [1 1], [0 2], [1 1], [2 0] ] sage: IM.cardinality() 6
-
cardinality
()¶ The number of integer matrices with the prescribed row sums and columns sums.
EXAMPLES:
sage: from sage.combinat.integer_matrices import IntegerMatrices sage: IntegerMatrices([2,5], [3,2,2]).cardinality() 6 sage: IntegerMatrices([1,1,1,1,1], [1,1,1,1,1]).cardinality() 120 sage: IntegerMatrices([2,2,2,2], [2,2,2,2]).cardinality() 282 sage: IntegerMatrices([4], [3]).cardinality() 0 sage: len(IntegerMatrices([0,0], [0]).list()) 1
This method computes the cardinality using symmetric functions. Below are the same examples, but computed by generating the actual matrices:
sage: from sage.combinat.integer_matrices import IntegerMatrices sage: len(IntegerMatrices([2,5], [3,2,2]).list()) 6 sage: len(IntegerMatrices([1,1,1,1,1], [1,1,1,1,1]).list()) 120 sage: len(IntegerMatrices([2,2,2,2], [2,2,2,2]).list()) 282 sage: len(IntegerMatrices([4], [3]).list()) 0 sage: len(IntegerMatrices([0], [0]).list()) 1
-
column_sums
()¶ The column sums of the integer matrices in
self
.OUTPUT:
- Composition
EXAMPLES:
sage: from sage.combinat.integer_matrices import IntegerMatrices sage: IM = IntegerMatrices([3,2,2], [2,5]) sage: IM.column_sums() [2, 5]
-
row_sums
()¶ The row sums of the integer matrices in
self
.OUTPUT:
- Composition
EXAMPLES:
sage: from sage.combinat.integer_matrices import IntegerMatrices sage: IM = IntegerMatrices([3,2,2], [2,5]) sage: IM.row_sums() [3, 2, 2]
-
to_composition
(x)¶ The composition corresponding to the integer matrix.
This is the composition obtained by reading the entries of the matrix from left to right along each row, and reading the rows from top to bottom, ignore zeros.
INPUT:
x
– matrix
EXAMPLES:
sage: from sage.combinat.integer_matrices import IntegerMatrices sage: IM = IntegerMatrices([3,2,2], [2,5]); IM Non-negative integer matrices with row sums [3, 2, 2] and column sums [2, 5] sage: IM.list() [ [2 1] [1 2] [1 2] [0 3] [0 3] [0 3] [0 2] [1 1] [0 2] [2 0] [1 1] [0 2] [0 2], [0 2], [1 1], [0 2], [1 1], [2 0] ] sage: for m in IM: print IM.to_composition(m) [2, 1, 2, 2] [1, 2, 1, 1, 2] [1, 2, 2, 1, 1] [3, 2, 2] [3, 1, 1, 1, 1] [3, 2, 2]
-
-
sage.combinat.integer_matrices.
integer_matrices_generator
(row_sums, column_sums)¶ Recursively generate the integer matrices with the prescribed row sums and column sums.
INPUT:
row_sums
– list or tuplecolumn_sums
– list or tuple
OUTPUT:
- an iterator producing a list of lists
EXAMPLES:
sage: from sage.combinat.integer_matrices import integer_matrices_generator sage: iter = integer_matrices_generator([3,2,2], [2,5]); iter <generator object integer_matrices_generator at ...> sage: for m in iter: print m [[2, 1], [0, 2], [0, 2]] [[1, 2], [1, 1], [0, 2]] [[1, 2], [0, 2], [1, 1]] [[0, 3], [2, 0], [0, 2]] [[0, 3], [1, 1], [1, 1]] [[0, 3], [0, 2], [2, 0]]