Permute the values in each row in a matrix such that the columns sum to the same amount.

Question

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.

Answer 1

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.