Algorithms: Using maximum flow to calculate correct matrix values

Question

I am given an matrix A with size N x M with N,M <= 100. Matrix A consists of integer values A(i,j) where i and j are 0 < i < M and 0 < j < N. I am also given the "correct" column sums and row sums of the matrix. The given values A(i,j) are "incorrect" (they do not match the "correct" sums) and therefore we are provided with corresponding "incorrectness" values B(i,j), where B(i,j) ranges from 0 to A(i,j).

The goal is to calculate the "correct" values C(i,j) in the matrix, where A(i,j) - C(i,j) =< B(i,j), the C(i,j) values must also match the given row and column sums. I think I have to use maximum flow, but my attempts have not worked. How can I achieve this?

Answer 1

I'll just give you an example here.

matrix A:
 10 10 10
 10 10 10
 10 10 10

matrix B:
  2  3  4
  5  6  4
  3  2  1

matrix A-B:
  8  7  6
  5  4  6
  7  8  9

So you have the formula A[i,j] - C[i,j] <= B[i,j]. You can transform it into A[i,j] - B[i,j] <= C[i,j] which means that B[i,j] is the smallest thing that you need to subtract from A[i,j] to get something smaller or equal to C[i,j]. From here you know that you need to add something to the entries in matrix A-B.

Let's now find what and where to add.

Let's assume you are given the following row and column sizes:

c1 = 20/20
c2 = 19/21
c3 = 21/24

r1 = 21/21
r2 = 15/17
r3 = 24/27

Above I wrote things in the form of:

(current flow through column or row) / (goal flow through column or row).

Now let's build a network:

Now note that the total sum of rows = total sum of columns. So you try to push 'given sum of entries' - 'current sum of entries' from 's' to 't'.

Now, let's assume that the nodes are enumerated from left to right by natural numbers. Now, when you push something from a second level node to a third level node, say, you push something from node i, to node j, you also add whatever you pushed to NewMatrix[i,j], where NewMatrix is the matrix A-B and you get the matrix you want.

Also note that in the beginning, in the matrix A-B, you had the smallest C[i,j] that you had to subtract from A[i,j] to get something smaller or equal to B[i,j], and now that you added something to that C[i,j] the inequality A[i,j]-C[i,j]<=B[i,j] still holds.