Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

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>