Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Can anyone suggest an algorithm for iterating once through all matrices with non-negative integer entries which are $2$ by $n$ with fixed row sums ($r_1$ and $r_2$) and fixed column sums ($c_1, c_2, \ldots c_n$)? For instance, for row and column sums $r_1= r_2 = c_1 = c_2 = 2$, (if I haven't make a mistake) the possible matrices would be

$\left(\begin{array}{cc} 2 & 0\\ 0 & 2 \end{array}\right)$

$\left(\begin{array}{cc} 1 & 1\\ 1 & 1 \end{array}\right)$

$\left(\begin{array}{cc} 0 & 2\\ 2 & 0 \end{array}\right)$

However, I would want to do this for general $2$ by $n$ matrices, not just $2$ by $2$.

I would also like to know if there is a quick way to compute the total number of matrices I would have to iterate over.

share|improve this question
    
It seems you're interested only in matrices with non-negative integer entries? –  joriki Oct 1 '11 at 13:01
    
@joriki, Good catch. –  Henry B. Oct 1 '11 at 13:04
1  
It still doesn't say "integer". –  joriki Oct 1 '11 at 13:08

1 Answer 1

up vote 3 down vote accepted

If you are doing 2xn enumerating them is easy, as all you need to do is enumerate the first row, (the second row is forced) and this is just the problem of enumerating all vectors with a given sum and bounds on each element. This is easy to do recursively, but if you want the total count and a nice, easy to compute bijection with the natural numbers, see "On uniform generation of two-way tables with fixed margins and the conditional volume test of Diaconis and Efron" by Holmes and Jones (see section 2b). Larger tables are considerably more difficult.

See also the answers to these two math.stackexchange questions.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.