by **Guest** » Wed Oct 12, 2016 11:12 am

I thought about it a bit more, and you can ignore my comments about using linear programming or integer programming, there is a simple way (specifically for your problem) to force the solution to only contain non-negative integers.

Step 1 : First create the solution where everything except the first row and column have an entry of zero.

Step 2 : If the cell in the first row and column (call it (1, 1)) is negative (this is the only cell that could be), then find a column, call it c, such that cell (1, c) is positive (and not zero), and find a row, call it r, such that cell (r, 1) is positive (and not zero) (you will always be able to find such an r, and c). Add 1 to cells (1, 1), (r, c), and subtract 1 from (r, 1) and (1, c).

Step 3: If cell (1, 1) is still negative, keep repeating Step 2.

When cell (1, 1) eventually becomes zero, the solution will contain only non-negative integer values.

For example:

Suppose I have 3 rows and columns and the constraints that row i sums to i, and column j sums to j.

By Step 1 my table looks like

[tex]\begin{tabular}{ |c|c|c| }

\hline

-4 & 2 & 3 \\ \hline

2 & 0 & 0 \\ \hline

3 & 0 & 0 \\

\hline

\end{tabular}[/tex]

Applying step 2 to r=2, c=2, gives

[tex]\begin{tabular}{ |c|c|c| }

\hline

-3 & 1 & 3 \\ \hline

1 & 1 & 0 \\ \hline

3 & 0 & 0 \\

\hline

\end{tabular}[/tex]

Applying step 2 to r=2, c=3, (changing c to 3 just for fun) gives

[tex]\begin{tabular}{ |c|c|c| }

\hline

-2 & 1 & 2 \\ \hline

0 & 1 & 1 \\ \hline

3 & 0 & 0 \\

\hline

\end{tabular}[/tex]

Applying step 2 to r=3, c=3, gives

[tex]\begin{tabular}{ |c|c|c| }

\hline

-1 & 1 & 1 \\ \hline

0 & 1 & 1 \\ \hline

2 & 0 & 1 \\

\hline

\end{tabular}[/tex]

Applying step 2 to r=3, c=3, gives

[tex]\begin{tabular}{ |c|c|c| }

\hline

0 & 1 & 0 \\ \hline

0 & 1 & 1 \\ \hline

1 & 0 & 2 \\

\hline

\end{tabular}[/tex]

We've found a solution with all entries non-negative integers.

Note that if we choose different values for r and c at step 2, we would end up with different solutions.

Hope this helped,

R. Baber.