Find a matrix with given row and column sums

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

• I'm very surprised by two downvotes for this very interesting question. – Ethan Bolker Oct 15 '16 at 14:31
• Does the "math square" need to be filled with integers? – Rodrigo de Azevedo Oct 15 '16 at 15:04

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.

• The grid is actually $4 \times 5$ so there are only $20$ unknowns, but the idea is correct. You could note that add one to the top left and bottom right and subtracting one from the top right and bottom left leaves all the row and column sums the same. There are many other patterns like this, which shows there is not a unique solution. – Ross Millikan Oct 15 '16 at 14:15
• @RossMillikan Edited thanks. – Ethan Bolker Oct 15 '16 at 14:26

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.