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 [1] constructs an arbitrary matrix of dimension implied by the row and column sums (need not be square); [2] uses Reduce to apply the conditions that the entries are nonnegative integers to determine all possible solutions; [3] turns this output into a list of replacement rules; and [4] 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]; cond = Thread[Flatten[mat] >= 0]; 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[4], Range[4]] In such cases a random search method will be more efficient -- and I'm confident that other posters will help you here. 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

**Follow-Ups**:**Re: Re: random matrix from row and column sums***From:*DrBob <drbob@bigfoot.com>