Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The general problem

Given a matrix, I would like to permute the order of values in each row, so that all the columns of the matrix sums to the same value.

A simple example

For example, given:

 0     0     2     6
 0     0     6    18
 0     0    10    30
 0     0    14    42
 0     0    18    54
 0     0    22    66

One solution is:

 0     0     2     6
 0    18     6     0
30     0    10     0
42     0    14     0
 0    54    18     0
 0     0    22    66

Notice that each column sums to 72. Of course, the solution is not unique; one may permute the columns themselves to obtain different solutions, such as:

 0     0     2     6
18     0     6     0
 0    30    10     0
 0    42    14     0
54     0    18     0
 0     0    22    66

The specific problem

Here I am looking at a simple $30 \times 5$ matrix. The matrix is defined thus: the contents of row $n$ is $[0, 0, 2f(n), 6f(n), 12f(n)+2]$ where $f(n) = 4n^2+4n+1$ and $n = 0, 1, 2, ...,29$.

Here is what the matrix looks like:

       0           0           2           6          14
       0           0          18          54         110
       0           0          50         150         302
       0           0          98         294         590
       0           0         162         486         974
       0           0         242         726        1454
       0           0         338        1014        2030
       0           0         450        1350        2702
       0           0         578        1734        3470
       0           0         722        2166        4334
       0           0         882        2646        5294
       0           0        1058        3174        6350
       0           0        1250        3750        7502
       0           0        1458        4374        8750
       0           0        1682        5046       10094
       0           0        1922        5766       11534
       0           0        2178        6534       13070
       0           0        2450        7350       14702
       0           0        2738        8214       16430
       0           0        3042        9126       18254
       0           0        3362       10086       20174
       0           0        3698       11094       22190
       0           0        4050       12150       24302
       0           0        4418       13254       26510
       0           0        4802       14406       28814
       0           0        5202       15606       31214
       0           0        5618       16854       33710
       0           0        6050       18150       36302
       0           0        6498       19494       38990
       0           0        6962       20886       41774

Obviously, the desired sum for each column is equal to the sum of all elements in the matrix divided by the number of columns. Here it is $\frac{1}{5}\left(60 + 20\sum_{n=0}^{29} f(n)\right) = 143972$.

We certainly cannot do this by brute force: For an $m\times n$ matrix the number of possibilities are: $(n!)^m$ which combinatorially explodes. Here, two of the columns given are zeros so we have $\left(\frac{n!}{2}\right)^m$ unique ways to permute the values of each row - which is not much better.

Fortunately, this matrix has a well-defined pattern to it, and I am wondering: can this pattern can be exploited to derive solutions more easily?

EDIT: I have made a recursive depth-first search to find solutions. On each iteration, it attempts to construct a vector that sums to the desired result (in this case 143972) by choosing each entry in the vector from a different row in the matrix. Once one such vector has been created, it removes the chosen entries from the matrix thereby changing it from an $m\times n$ matrix to an $m \times n-1$ one. This repeats until either no solution can be found, or a the matrix becomes empty. In the worst case, it runs on the order of $n^m$ for an $m\times n$ matrix (but it turns out that finding one solution is fast because my matrix has many, many solutions apparently).

Here are three sample solutions I have found using this approach:

Solution 1

       6          14           0           0           2
       0          54          18         110           0
      50           0           0         302         150
       0           0          98         590         294
       0           0         162         486         974
       0           0         242        1454         726
     338           0        1014           0        2030
       0         450           0        2702        1350
       0           0         578        1734        3470
       0           0         722        2166        4334
       0           0         882        2646        5294
       0           0        1058        3174        6350
       0           0        1250        3750        7502
       0           0        1458        4374        8750
       0           0        1682        5046       10094
       0           0        1922       11534        5766
       0        2178           0        6534       13070
       0           0        2450        7350       14702
       0           0        2738       16430        8214
       0           0        3042       18254        9126
    3362           0       20174       10086           0
       0        3698       22190       11094           0
       0       12150       24302        4050           0
       0       26510       13254        4418           0
       0       28814       14406        4802           0
   31214       15606        5202           0           0
   33710       16854        5618           0           0
   36302       18150        6050           0           0
   38990       19494        6498           0           0
       0           0        6962       20886       41774

Solution 2

       6           0           2           0          14
       0         110           0          54          18
       0         150           0          50         302
     294         590           0           0          98
     486         974           0         162           0
     726         242        1454           0           0
    1014        2030           0         338           0
    2702         450        1350           0           0
    1734        3470         578           0           0
    4334        2166         722           0           0
    5294        2646         882           0           0
    3174        6350        1058           0           0
    7502        3750        1250           0           0
    8750        4374           0        1458           0
   10094        5046        1682           0           0
   11534        5766        1922           0           0
   13070        6534        2178           0           0
   14702        7350        2450           0           0
   16430        8214        2738           0           0
   18254        9126        3042           0           0
   20174       10086        3362           0           0
    3698       22190       11094           0           0
       0       24302       12150        4050           0
       0       13254       26510           0        4418
       0        4802       28814       14406           0
       0           0       15606       31214        5202
       0           0        5618       33710       16854
       0           0        6050       18150       36302
       0           0        6498       19494       38990
       0           0        6962       20886       41774

Solution 3

       0          14           0           6           2
       0          18         110           0          54
       0           0         302         150          50
       0         590         294          98           0
     162         974           0         486           0
    1454         242         726           0           0
       0        1014        2030         338           0
     450        1350        2702           0           0
       0        1734        3470           0         578
     722        4334        2166           0           0
       0        2646        5294         882           0
    1058        3174        6350           0           0
       0        3750        7502        1250           0
    1458        4374        8750           0           0
       0        5046       10094        1682           0
    5766       11534        1922           0           0
    2178           0       13070        6534           0
    7350       14702        2450           0           0
       0        2738        8214       16430           0
   18254        9126        3042           0           0
       0        3362       10086       20174           0
   11094       22190        3698           0           0
       0        4050       12150       24302           0
   26510       13254        4418           0           0
       0           0        4802       14406       28814
   31214       15606        5202           0           0
       0           0        5618       16854       33710
   36302       18150        6050           0           0
       0           0        6498       19494       38990
       0           0        6962       20886       41774

But I still don't know whether there's a way to count the number of solutions, or how to generate more solutions more efficiently. And my depth-first-search algorithm is a rather brute-force way that doesn't take advantage of the known sequence that the original matrix is made up of.

share|improve this question
add comment

1 Answer

You can construct your "vector" using dynamic programing. Let $g(i, j) = x$ represents "There are $x$ ways to satisfy $\sum_{r=0}^i A(r, c(r)) = j$, where $ c(r) = 0, 1, 2, 3, m-1$ ". Then $$ g(i, j) = \sum_{k=0}^{m-1} g(i - 1, j - A(i, k)) $$ In this way you can find the number of all valid "vector" in time $O(n^3 m)$. In your example, the number is 4053803829558. Similarly, you can also use this method to construct the vector.

share|improve this answer
add comment

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.