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

## 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.

## 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.