Need Formula to fill in the missing cells

[Guest]

In the spreadsheet are two math squares both are the same except the bottom has the center results missing. I need a formula to calculate them back one cell at a time using the given info. The row and columns add up vertically and horizontally giving a total of 25022486. Using the given info of the total sum and the individual sums of the row and columns I would like to a method to regenerate the center cells. I can be reached at tony@phoenixsequence.com

Thank you

Tony

p.s. here is a link to the spreadsheet I assure you it is NOT malicious.

http://phoenixsequence.com/misc/magic_square.xlsx

[Guest]

The center cells cannot be reconstructed uniquely (in general they could only be uniquely constructed if there was only one row or one column, in which case it is pretty easy to do). To see why they cannot be reconstructed uniquely, consider the given solution indicated by the upper table, add 1 to cells B2, and C3, and subtract 1 from cells B3 and C2. This won't have changed the sum of any of the rows or columns, so is also a solution.

Although the center cells can't be uniquely determined, you can find a set of values which will work (they just won't be the only set of values that will work). One way to do this is to set everything to zero except the first row and column. The values of the remaining cells are then really easy to determine, everything in the first row has the value of the column sum of the column it is in (except for the cell in the first row and first column), everything in the first column has the row sum of the row it is in (except for the cell in the first row and first column), the cell in the first row and column has a value of "row sum" plus "column sum" minus "total sum".

For example in your example:
C2 would be 3647 (=C1), D2 would be 4879 (=D1), E2 would be 11718478 (=E1), etc.
B3 would be 73119 (=A3), B4 would be 398613 (=A4), B5 would be 630308 (=A5), etc.
B2 would be -25013886 (=A2+B1-M1)

In general B2 is likely to be negative by the method I've just described. If you want all entries to be positive, the problem becomes significantly harder, but is still solvable by converting it into a linear programming:
the variables are the center cells you will have 100 of them,
there are 20 constraints (one for each row and column),
you should probably add 20 slack variables (one for each constraint).
So the constraints look like "v1+v2+...+v10+slack = row/col sum".
The objective function should just be to minimize the sum of slack variables.
There are lots of free linear program solvers online which will do the job of solving the linear program for you, very efficiently (this is not something you should try doing by hand).

The variables returned will all be non-negative, but they almost certainly won't be integers. If you only want non-negative integer solutions then you will need to look at integer linear programming, which is in general tricky and very hard to solve.

Hope this helped,

R. Baber.

[Guest]

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.

[Guest]

Thank you for the response. I'm trying to understand. My problem is that I'm constrained to the values already given by the totals. Those cannot change. So using the information given want to recreate the center cells. I can see there's a symmetry such as the total sums of the rows and columns equaling the same. Subtracting the given numbers in cells A2 and B2 gives a result of 404 (4502- 4098 = 404) Which is the same as 25022486 - 4502 = 25017984 and 25022486 - 4908 = 25018388 (25018388 - 25017984 = 404). I just need a way to push that thinking and using that to solve for the missing center cells one at a time.

Again thank you for all your help.

[Guest]

The problem you have is that your problem is underconstrained. See
https://en.wikipedia.org/wiki/Underdetermined_system
You have 100 values you want to work out but only 20 equations (actually because of the symmetry that you pointed out regarding the sum of row sums equaling the sum of column sums there is actually only 19 equations, but this is a bit technical). There is simply no way you can get back the original information.

For example consider a simplified version of your problem: I have two numbers 5, 4 and they add up to 9. If I only tell you that I have two numbers and they add up to 9, you can't work out they are 5 and 4, they could be 6 and 3, or 7 and 2, or 8 and 1. There's not enough information, so you have to fill in the gaps in an arbitrary way. I have 2 unknowns and only one equation x+y=9, to determine x and y I need an extra equation (2 unknowns need 2 equations). I am free to choose that equation as I like, so I could choose as my extra equation x = 2, now I have enough information to determine that the two numbers are 2 and 7. If I chose a different equation such as x-y=3, I'll get a different answer (6 and 3).

In your original problem you have 100 unknowns and 19 equations, which means you have 100-19 = 81 pieces of missing information, or put another way you need an additional 81 equations. There's no way to cleverly get around this, no amount of mathematical manipulation will help. You have to make a choice or guess for what those equations are. I chose to make everything not in row 1 or column 1 to be zero, there are precisely 81 cells that aren't in row 1 or column 1, so I gained 81 new bits of information, meaning that I could determine all the cells.

Given the 20 sums there is simply no way to get back the 100 cells. The best you can do is what I outlined in my previous post: a solution but not necessarily the one you started with.

Hope this helped,

R. Baber.