       Re: random matrix from row and column sums

• To: mathgroup at smc.vnet.net
• Subject: [mg53598] Re: random matrix from row and column sums
• From: Paul Abbott <paul at physics.uwa.edu.au>
• Date: Wed, 19 Jan 2005 02:00:27 -0500 (EST)
• Organization: The University of Western Australia
• References: <csinpt\$njk\$1@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

```In article <csinpt\$njk\$1 at smc.vnet.net>, adiggle at agric.wa.gov.au wrote:

> Is there an efficient method in Mathematica to generate random tables
> of nonnegative integers from a list of row sums and a list of column
> sums?
>
> For example for row sums of {7,3,2} and column sums of {2,9,1} the
> following two tables satisfy the constraints:
>
> {{2, 5, 0}, {0, 2, 1}, {0, 2, 0}}
> and
>
> {{1, 6, 0}, {1, 2, 0}, {0, 1, 1}}

Here is one way to do this. The following module

 constructs an arbitrary matrix of dimension implied by the row and
column sums (need not be square);

 uses Reduce to apply the conditions that the entries are nonnegative
integers to determine all possible solutions;

 turns this output into a list of replacement rules; and

 returns a list of _all_ matrices satisfying the constraints.

NonnegativeIntegerMatrices[rows_, cols_] := Module[
{mat, r, c, a, vars, cond, red, m = Length[rows], n = Length[cols]},
mat = Table[a[i, j], {i, m}, {j, n}];
r = Thread[Plus @@ Transpose[mat] == rows];
c = Thread[Plus @@ mat == cols];
vars = Flatten[mat];
red = {ToRules[Reduce[Join[r, c, cond], vars, Integers]]};
If[red != {}, mat /. red, {}]
]

Once you have the complete list of solutions, say

sols = NonnegativeIntegerMatrices[{7,3,2}, {2,9,1}]

it is easy to select one at random

sols[[ Random[Integer, {1, Length[sols]}] ]]

However, this approach is not optimal if you have to work with large
numbers of different row and column sums. Also, computing all solutions
can be slow even for rather small matrices, e.g., try

sols = NonnegativeIntegerMatrices[Range, Range]

In such cases a random search method will be more efficient -- and I'm

Cheers,
Paul

--
Paul Abbott                                   Phone: +61 8 6488 2734
School of Physics, M013                         Fax: +61 8 6488 1014
The University of Western Australia      (CRICOS Provider No 00126G)
35 Stirling Highway
Crawley WA 6009                      mailto:paul at physics.uwa.edu.au
AUSTRALIA                            http://physics.uwa.edu.au/~paul

```

• Prev by Date: Re: Matrix Problem
• Next by Date: Nonatomic expression error encountered with Intersection
• Previous by thread: Re: random matrix from row and column sums
• Next by thread: Re: Re: random matrix from row and column sums