I am interested in nonnegative integer solutions $\{x_{mq}\}$ to a particular type of linear system. The system can be broken into a "horizontal" and "vertical" subsystem; that is, the horizontal subsystem is as follows
$$x_{11} + x_{12} + \ldots + x_{1Q} = h_1 $$ $$x_{21} + x_{22} + \ldots + x_{2Q} = h_2 $$ $$\vdots$$ $$x_{M1} + x_{M2} + \ldots + x_{MQ} = h_M $$
whereas the vertical system is $$x_{11} + x_{21} + \ldots + x_{M1} = v_1 $$ $$x_{12} + x_{22} + \ldots + x_{M2} = v_2 $$ $$\vdots$$ $$x_{1Q} + x_{2Q} + \ldots + x_{MQ} = v_Q $$
for constants $h_1, \ldots, h_M$ and $v_1, \ldots , v_Q$.
So the vertical system are simply summing restrictions formed from the "columns" of the horizontal system. In matrix form, the systems can be written as $$ X 1_Q = h $$ $$ X' 1_M = v $$ where $1_K$ denotes the vector of ones in $\mathbb{R}^K$.
I doubt that this system has a closed form for the family of solutions (but would be very glad to be proved wrong!). Does a straightforward algorithm exist instead? The plan that I'm currently implementing is as follows:
- Enumerate all solutions $x_{m1}, x_{m2}, \ldots , x_{mQ}$ to the horizontal system for each $m$.
- Iterate through all combinations of the above solutions, eliminating combinations that violate the vertical solution.
As one might guess, this is not a terribly efficient algorithm. I can save much time by placing restrictions on the horizontal solutions I find in (1) by first eliminating any that have $x_{mq} > v_q$. Even so, with just $M = Q = 6$, I'd be iterating over a list with something on the order of tens of billions of elements.
I'm exploring this, so for the beginning I assume, that the matrix $XX$ is a square-matrix, with #rows=#cols=n.
First we note, that $\sum_{k=1}^n h_k = \sum_{k=1}^n v_k $, so $v_n $ is not free to be set arbitrarily but is determined by the other given coefficients.
Keeping this in mind I begin with the matrix $XX=\{x_{r,c} \}_{r,c=1..n}=0$, and initially filling in $x_{1,1}=h_1$. The sum of the first row gives now correctly $h_1$.
Now the first column needs a compensation to be able to sum up to $v_1$: in the second row $x_{2,1}$ I set $x_{2,1}=v_1-x_{1,1}$ . From this follows the setting of $x_{2,2}=h_2-x_{2,1}$, then $x_{3,2}=v_2-x_{2,2}$ and so on with that simple recursive algorithm, down to the bottom right entry.
With an example of $n=4$ I get the following solution: $$ \small\begin{array} {rrrr|r} h_1&\cdot&\cdot&\cdot&h_1\\ v_1-h_1&h_1+h_2-v_1&\cdot&\cdot&h_2\\ \cdot&(v_1+v_2)-(h_1+h_2)&(h_1+h_2+h_3)-(v_1+v_2)&\cdot&h_3\\ \cdot&\cdot&(v_1+v_2+v_3)-(h_1+h_2+h_3)&(h_1+h_2+h_3+h_4)-(v_1+v_2+v_3)&h_4\\\hline v_1&v_2&v_3&v_4&\cdot\\ \end{array}$$ Note that I've appended the rowsums at the right and the column-sums at the bottom.
Note also, that the last entry $x_{4,4}$ requires (or simply: expresses) the equality which I've mentioned at the beginning of this post.