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

[N. J. A. Sloane]

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

>From simin.he at ieee.org  Mon Dec 29 22:58:08 2003
>Delivered-To: njas at research.att.com
>Reply-To: "He, Simin" <simin.he at ieee.org>
>From: "He, Simin" <simin.he at ieee.org>
>To: <dmanet at zpr.uni-koeln.de>, <njas at research.att.com>,
>        <mathworld at wolfram.com>
>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 (1.212.2.1-2003-12-09-exp) on 
>	mail-brown.research.att.com
>X-Spam-Level: 
>X-Spam-Status: No, hits=-203.4 required=4.0 tests=BAYES_00,MIME_BASE64_LATIN,
>	MIME_BASE64_TEXT,USER_IN_ALL_SPAM_TO,USER_IN_WHITELIST autolearn=no 
>	version=2.61
>X-MIME-Autoconverted: from base64 to 8bit by fry.research.att.com 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!
>
>Best,
>
>Simin He
>