Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

I have matrix like this:

enter image description here

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:

good

Bad:

bad

share|improve this question
1  
A multitude of solutions can be found here DiagonalMatrix[RandomInteger[{1, 10}, 10]] –  image_doctor Nov 17 '12 at 12:48
4  
Or even simpler: Set every element in the matrix to zero. –  nikie Nov 17 '12 at 12:54

1 Answer 1

up vote 9 down vote accepted

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:

Mathematica graphics

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.