reconstruct a matrix from its row and column sums

Question

Take a n*m matrix filled with floating point values between 0 and 1.

Example:

0    0.5  0    0
0    0.5  1    0.4
0.2  1    0.3  0
0    1    0    0

The goal is to reconstruct the values in this matrix.

I do not have access to this matrix, so I do not know any of its values at the beginning. There is a function to calculate each value, calc_value(m,n). So a simple way to reconstruct this matrix is to call calc_value(m,n) for each value.
But calling this function is a very expensive operation, so I would like to call this function as few times as possible.

I know the total sum of all values in the matrix, and the sum of values in each individual row and column. (calculating each of these sums is no more expensive than a call to calc_value(m,n))

Using the row and column sums as additional information, how can I fill all values in the matrix with the least amount of calls to calc_value()?

Is it possible with fewer than O(n*m) calls?

There is one additional constraint for the matrix that may help: the values in each row and column will be be monotonous increasing up to a maximum, then monotonous decreasing after that maximum. So a single row could look like this:

0 0.5 0.5 1 1 0.5 0

but not like this:

0 1 0 1 0 1 

e.g. more than one distinct local maximum is not allowed

---

This is the status of my own attempts:

So far I discovered the following inequalities. For a given value of the matrix M(n,m):

M(n,m) <= Min ( sum_of_row_n, sum_of_column_m)
M(n,m) >= sum_of_row_n - sum_of_all_columns_except_m
M(n,m) >= sum_of_column_m - sum_of_all_rows_except_n

But these inequalities do not provide enough information to deduce the value M(n,m), except for some trivial cases.

Answer 1

From what you describe it seems that your matrix has m*n degrees of freedom. The range and monotonicity constraints do not reduce the degrees of freedom. Each sum (row, column, total) removes one degree of freedom - until (m-1)*(n-1) degrees have been reached. (Since the sum of all row sums and the sum of all column sums equals the total sum you can only exploit m+n-1 of these constraints).

So with the given information all you can do is:

1. calculate the matrix elements a_ij, 1 <= i< m, 1 <=j < n with calc_value(i,j)
2. compute the missing element of each row/column and a_mn via the row/col sum properties