Find a matrix with given row and column sums

Question

Please forgive my intrusion. I've been working for days on this problem and it's vexing me. It doesn't seem to have a solution and I could really use some help. I have a "math square" (not a magic square) that looks like this when filled in

$$ \begin{array}{ccccc|c} 9 & 4 & 8 & 4 & 7 & 32 \\ 7 & 9 & 15 & 7 & 5 & 43 \\ 3 & 2 & 9 & 10 & 9 & 33 \\ 5 & 3 & 5 & 6 & 4 & 23 \\ \hline 24 & 18 & 37 & 27 & 25 & 131 \\ \end{array} $$

However, the puzzle when empty looks like this.

$$ \begin{array}{ccccc|c} x & x & x & x & x & 32 \\ x & x & x & x & x & 43 \\ x & x & x & x & x & 33 \\ x & x & x & x & x & 23 \\ \hline 24 & 18 & 37 & 27 & 25 & 131 \\ \end{array} $$

I need an equation of some sort to fill in the unknowns ($X$'s) and recreate the missing values.

There appears to be some symmetry with the puzzle as the columns and row all add up to be the same which in this case is $131$. If you separate them by every other row to perhaps break it down to make it easier to solve you get. You could also do this with the columns but for simplicity I haven't written it here.

$$ \begin{array}{ccccc|c} 9 & 4 & 8 & 4 & 7 & 32 \\ 3 & 2 & 9 & 10 & 9 & 33 \\ \hline 12 & 6 & 17 & 14 & 16 & 65 \\ \end{array} \dots \begin{array}{ccccc|c} 7 & 9 & 15 & 7 & 5 & 43 \\ 5 & 3 & 5 & 6 & 4 & 23\\ \hline 12 & 12 & 20 & 13 & 9 & 86 \\ \end{array} $$

using these givens in the puzzle is allowed, but not the $X$'s

If it is indeed unsolvable I would like to know but if it can what missing component can be add to achieve that goal?

Your help is very much appreciated and thank you!

Regards,

Tony

p.s. sorry about the formatting.

Answer 1

You are looking for a matrix with given row and column sums. (Your particular example is $4 \times 5$, and you seem to want an integer solution.)

You are right to note in the title that there are lots of unknowns: $20$ in your case. But you have only $9$ equations, one for each row and column. In fact you have only $8$ independent equations, since the sum of the row sums must equal the sum of the column sums ($131$ in your problem). That means there will be lots of solutions: $20-9+1 = 12$ dimensions of them. So you can't hope for an algorithm to find "the" solution.

If you don't need integers, just put $r_ic_j/T$ in position $(i,j)$, where $r_i$ is the sum for row $i$, $c_j$ the sum for row $j$ and $T$ the total.

Here's a way to find one positive integer solution. Find the smallest sum - it's $18$ in the second column. Put that $18$ in the row with the smallest sum, make the rest of the $18$ column $0$ and reduce the problem to a $4 \times 4$ one, this way:

$$ \begin{array}{ccccc|c} x & 0 & x & x & x & 32 \\ x & 0 & x & x & x & 43 \\ x & 0 & x & x & x & 33 \\ x & 18 & x & x & x & 23-18=5 \\ \hline 24 & 18 & 37 & 27 & 25 & 131-18 = 113\\ \end{array} $$

Then do this again, until you're done.

This strategy is well known, and very general.

If you search for "matrices with given row and column sums" or "transportation polytopes" you'll find lots of literature - probably more than you need.

Answer 2

Here is a theorem I found referenced by Alexander Barvinok in his "Matrices with prescribed row and column sums" where he in turn references Section 6.2 of "Combinatorial Matrix Theory" by Brualdi and Ryser:

Let $R = (r_1, r_2, \dots, r_m)$ and $S = (s_1, s_2, \dots, s_n)$ be non-negative integral vectors. There exists an $m$ by $n$ non-negative integral matrix with row sum vector $R$ and column sum vector $S$ if and only if $\sum_{i = 1}^{m}r_i = \sum_{j = 1}^n s_j$

Proof: if there exists such a matrix, then the equality of the sums holds. Conversely, suppose that the equality holds. Now let's inductively construct the matrix $A = [a_{ij}]$ with row sum vector $R$ and column sum vector $S$:

If $m = 1$, then we let $A = [s_1, s_2, \dots, s_n]$

If $n = 1$, then we let $A = [r_1, r_2, \dots, r_n]$

Now we assume $n > 1, m > 1$ and proceed by induction on $m + n$ (this is the tricky bit):

Let $a_{11} = min(r_1, s_1)$, then there are two options:

Suppose $a_{11} = r_1$, then let $a_{12} = \dots = a_{1n} = 0$ and the new vectors become: $R' = (r_2, r_3, \dots, r_m)$ and $S' = (s_1 - r_1, s_2, \dots, s_n)$ For these vectors we can check that the equality holds:

$$ r_2 + r_3 + \dots + r_m = (s_1 - r_1) + s_2 + \dots + s_n$$

So, there exists a matrix $A'$ such that it has non-negative elements and has row sum vector $R'$ and column sum vector $S'$. If we add the row $[r_1, 0, 0, \dots, 0]$ "on top" of that matrix $A'$, we've constructed the desired matrix $A$.

Suppose $a_{11} = s_1$, then we have a symmetrical case. We just construct the matrix $A$ by adding a column on the left of $A'$ this time.

Answer 3

As this answer notes:

If you don't need integers, just put $r_ic_j/T$ in position $(i,j)$, where $r_i$ is the sum for row $i$, $c_j$ the sum for row $j$ and $T$ the total.

But even if you need integers, you can execute the following step for every cell: write $\left \lfloor{r_ic_j/T}\right \rfloor$ into $(i,j)$. This takes $n \times m$ steps. Then iterate over the matrix and substract the value of $(i, j)$ from ${r_i}$ and ${c_j}$ both. This also takes $n \times m$ steps. Since rounding down decreases the value by less than one the sum of all cells is at most $n \times m$ less than the desired total. Also, the new $r_i < m$ and $c_j < n$ for the same reason.

After this process, pick some $i | r_i > 0$ and a $j | c_j > 0$ and increase $(i,j)$ by one and decrease both $r_i$ and $c_j$ by one. Repeat this until finished -- this takes at most $n \times m$ steps because the total grows by one at every step. Thus, this algorithm is also $O(n \times m)$. Also note no cell will be increased more than $\min(n, m)$. Thus if the sum values were significantly bigger than $\min(n, m)$, the ratio of adjacent cells will be very close to the relevant sum ratio which is sometimes more desirable than the greedy filling of the matrix.

Answer 4

The problem is that your problem has twelve degrees of freedom. That is to say, you can set the twelve numbers in the $3 \times 4$ array in the upper left corner equal to anything and then fill in the remaining eight positions with numbers that will give you a solution with the row and column sums indicated.

$$\begin{array}{ccccc|c} A & B & C & D & 32-(A+B+C+D) & 32 \\ E & F & G & H & 43-(E+F+G+H) & 43 \\ I & J & K & L & 33-(I+J+K+L) & 33 \\ 24-(A+E+I) & 18-(B+F+J) & 37-(C+G+K) & 27-(D+H+L) & -83+\left(\begin{array}{l} A+B+C+D+ \\ E+F+G+H+ \\ I+J+K+L \\ \end{array} \right) & 23 \\ \hline 24 & 18 & 37 & 27 & 25 & 131\\ \end{array}$$

The point is, unless you are given more information. There is no way to find (only) the solution you started with.