4
$\begingroup$

Suppose $r_i$, $1 \le i \le n$, and $c_j$, $1 \le j \le m$, are nonnegative integers. When does there exist an $n \times m$ matrix in $\text{Mat}_{n \times m} (\mathbb{Z}^+)$, i.e. nonnegative entries, such that $r_i$ is the sum of the entries in its $i$th row and $c_j$ is the sum of the entries in its $j$th columns?

$\endgroup$
  • 1
    $\begingroup$ @user314: Why the algebra-precalculus tag? $\endgroup$ – Mike Spivey Nov 16 '10 at 5:50
6
$\begingroup$

Non-negative integer solutions exist whenever the (also necessary) "balance condition" is met:

$$ \sum_i r_i = \sum_j c_j $$

which simply sums the total matrix entries in two ways.

There is a survey paper by Alexander Barvinok on this: http://www.math.lsa.umich.edu/~barvinok/linalg.pdf

$\endgroup$
  • 1
    $\begingroup$ Yes, it's a very active area. One of my fellow graduate students is working on this for his thesis. $\endgroup$ – Timothy Wagner Nov 16 '10 at 5:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy