How to modify a matrix to satisfy a special condition?

Question

I have matrix like this:

How do I modify this matrix to make it satisfy the following condition:

For each element {i, j} in the matrix the sum of the elements of row i must be equal to the sum of the elements of column j. Zeros can't be modified.

Examples

Good:

Bad:

Answer 1

There is no unique solution to your problem, but you can use Reduce to find all solutions.

Say your matrix is m:

m = {{0, 1, 0, 0, 0, 0, 1, 0, 0, 0},
   {0, 0, 1, 0, 1, 0, 0, 0, 0, 0},
   {0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
   {0, 0, 1, 0, 1, 0, 0, 0, 0, 0},
   {0, 0, 0, 0, 0, 1, 0, 0, 0, 0},
   {0, 0, 1, 0, 0, 0, 0, 0, 0, 0},
   {0, 0, 0, 0, 0, 0, 0, 0, 1, 1},
   {0, 0, 0, 0, 0, 0, 1, 0, 0, 0},
   {0, 0, 1, 1, 0, 0, 0, 0, 0, 0},
   {1, 0, 0, 0, 0, 0, 0, 0, 0, 0}};

Now modify the matrix so every cell that can be modified contains a variable:

coefficients = Array[a, Dimensions[m]] m

the result matrix look like this:

Now, collect the variables used:

vars = Select[Flatten[coefficients], ! NumberQ[#] &]

And pass your conditions to Reduce:

Reduce[Total[coefficients, {1}] == Total[coefficients, {2}], vars]

Result:

a[2, 5] == a[1, 2] - a[2, 3] && 
 a[5, 6] == a[1, 2] - a[2, 3] + a[4, 5] && 
 a[6, 3] == a[1, 2] - a[2, 3] + a[4, 5] && 
 a[7, 9] == -a[1, 2] + a[3, 8] && a[7, 10] == a[1, 2] + a[1, 7] && 
 a[8, 7] == a[3, 8] && 
 a[9, 3] == -a[1, 2] + a[3, 8] - a[4, 3] - a[4, 5] && 
 a[9, 4] == a[4, 3] + a[4, 5] && a[10, 1] == a[1, 2] + a[1, 7]

In this case, you have 15 variables and only 10 equations, so you can add 5 different conditions to get a unique solution.

Alternatively, you can use a little linear algebra. You want to find the set of coefficients, for which:

Total[coefficients, {1}] - Total[coefficients, {2}] == 0

That's just the null space of the matrix spanned by these equations:

nullSpace = NullSpace[D[Total[coefficients, {1}] - Total[coefficients, {2}], {vars}]]

Result:

=> {{0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1}, 
    {-1, 1, -1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0},
    {-1, 1, -1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0}, 
    {1, -1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0}, 
    {0, 0, -1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0}, 
    {0, 0, 1, -1, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0}}

each of these lines describes one matrix that fulfills your conditions. For example, the first line means that if you set the 2nd, 11th and 15th coefficient to 1, you get a matrix that fulfills your condition. Any linear combination of these 6 matrices also fulfills your conditions.

You can get these "base matrices" using:

bases = nullSpace.(D[coefficients, #] & /@ vars);

Now bases contains 6 matrices, and every linear combination of these 6 matrices will fulfill your conditions.