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
sage.combinat.integer_matrices.IntegerMatrices

The class of non-negative integer matrices with prescribed row sums and column sums.

An 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\).

EXAMPLES:

There are \(6\) integer matrices with row sums \([3,2,2]\) and column sums \([2,5]\):

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
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 tuple
  • column_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]]