Quandaries and Queries
  

 

Hi,
I want to know if is it possible to solve this problem:
I have an empty NxM matrix and I know totals (sum) by rows and totals by column.
Is there any algorithm to fill the matrix so that the summary of columns and rows gives the original values I have?
Thanks

Marcelo
 

 

Hi Marcelo,

If you just have the row and column sums there may be more than one matrix with those sums. For example

2 0
0 2

and

1 1
1 1

have the same row and column sums. Also you can't just take and numbers to be the row sums and column sums, since the sum of the row sums, and the sum of the column sums, must be the same. In either case you have the sum of all the entries in the matrix.

I talked to a couple of people here who know a lot more about matrices than I do. They told me that you can do something if you know that the matrix is composed of zeros and ones.

Suppose that you start with a matrix of zeros and ones, for example

0 1 0
1 0 0
0 1 1

The row sums are 1,1,2 and the column sums are 1,2,1. I am going to produce other matrices with the same row and column sums. The technique is the following

  • if you see the submatrix
    1 0
    0 1
    replace it with
    0 1
    1 0

  • if you see the submatrix
    0 1
    1 0
    replace it with
    1 0
    0 1

So in the original matrix I see

0 1 0
1 0 0
0 1 1

so I construct the new matrix

1 0 0
0 1 0
0 1 1

Also in the original matrix I see

0 1 0
1 0 0
0 1 1

so I construct the new matrix

0 1 0
0 1 0
1 0 1

In this matrix I see

0 1 0
0 1 0
1 0 1

so I construct the new matrix

0 1 0
0 0 1
1 1 0

Finally in this matrix I see

0 1 0
0 0 1
1 1 0

so I construct the new matrix

0 0 1
0 1 0
1 1 0

All five of these matrices have row sums 1,1,2 and column sums 1,2,1. The interesting fact here is that these are the only 33, zero-one matrices with these row and column sums.

Harley

  
 

Go to Math Central