# Iterating over all matrices with fixed row and column sums

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.

-
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
It still doesn't say "integer". – joriki Oct 1 '11 at 13:08

## 1 Answer

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.

-