Problem of Enumerating Integer NxN Matrices with Line Sum Equal to D

N. J. A. Sloane njas at
Tue Dec 30 12:14:16 CET 2003

The following message may be of interest to seq-fans. - njas

>From simin.he at  Mon Dec 29 22:58:08 2003
>Delivered-To: njas at
>Reply-To: "He, Simin" <simin.he at>
>From: "He, Simin" <simin.he at>
>To: <dmanet at>, <njas at>,
>        <mathworld at>
>Subject: Problem of Enumerating Integer NxN Matrices with Line Sum Equal to D
>Date: Tue, 30 Dec 2003 11:55:40 +0800
>X-Priority: 3
>X-MSMail-Priority: Normal
>X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2800.1165
>X-Spam-Checker-Version: SpamAssassin 2.61 ( on 
>X-Spam-Status: No, hits=-203.4 required=4.0 tests=BAYES_00,MIME_BASE64_LATIN,
>	version=2.61
>X-MIME-Autoconverted: from base64 to 8bit by id WAA57346
>Dear friends,
>I come across a combinatorial generation problem:
>The task is to enumerate all N x N square matrices of non-negative integer elements, with line (column or row) sum equal to a common positive integer D. This type of matrix represents a regular (with degree D) bipartite multigraph. I need to enumerate all such bigraphs to test a conjecture.
>In order to make the test efficient, a further problem is to avoid equivalent and degenerate matrices. A matrix has not changed in essence after row swapping, column swapping or transposing. A matrix is degenerate if it is a composition of independent blocks, i.e., no connection among blocks. Non-degenerate matrices are fundamental generating units.
>This problem is a extension of permutation enumeration or integer partitioning enumeration to 2-dimensional and hence is more complicated.
>The third problem is to UNIFORMLY generate random distinct instances, with or without equivalence reduction.
>I want to know whether there has been any PROVED and elegant algorithm available to contend with the first problem, the third, and the second.
>I hope you are interested in this problem and could provide some clues.
>Happy New Year!
>Simin He

More information about the SeqFan mailing list