How to solve $\left\{\begin{matrix} x_1+x_2+x_3+\cdots+x_k=\Phi_1 \\ x_1+2x_2+3x_3+\cdots+kx_k=\Phi_2 \end{matrix}\right.$

Question

Recently, I have found this problem:

Given two natural numbers $\Phi_1$ and $\Phi_2$ ($\Phi_1,\Phi_2>1$), determine all possible natural integer solutions to the follwing system in the unkown $x_1,x_2,\cdots,x_k$: $$\left\{\begin{matrix} x_1+x_2+x_3+\cdots+x_k=\Phi_1 \\ x_1+2x_2+3x_3+\cdots+kx_k=\Phi_2 \end{matrix}\right.$$ where $k$ is a positive costant so that $k>2$.

To solve this, I have, first of all, shown that it must be $\Phi_2\geq \Phi_1$, because if I substarct the second the equation from the first, I obtain: $$0x_1-x_2-2x_3-\cdots-(k-1)x_k=\Phi_1-\Phi_2 \leftrightarrow x_2+2x_3+3x_4+\cdots+(k-1)x_k=\Phi_2-\Phi_1$$ And so, I must have $\Phi_2\geq\Phi_1$ because $x_1,x_2,\cdots,x_k\geq0$.

When $k=2$, the system can be solved with substitution or Gauss's method; what happens when $k>2$?

For example, let $M$ the matrix associated to the system: $$M=\begin{bmatrix} 1 & 1 & 1 & \cdots & 1 & \Phi_1\\ 1 & 2 & 3 & \cdots & k & \Phi_2 \end{bmatrix}$$

Can $M$ be used to find $(x_1,x_2,\cdots,x_k)$? Or are there any other methods?

Answer 1

You're asking for the partitions of $\Phi_2$ into $\Phi_1$ parts. See e.g. this Wikipedia section for a recurrence relation for their count. There’s an algorithm to generate all of them in Knuth’s The Art of Computer Programming, Volume $4$, Section $7.2.1.4$, Algorithm $H$ on p. $392$. As a general purpose method to solve this sort of system of linear equations with the variables restricted to certain ranges of integers, you could consider integer programming.

Answer 2

One thing which might help at least partially (but is too large for a comment) is to take the triangular matrix with ones

$${\bf T} = \begin{bmatrix}1&0&0\\1&1&0\\1&1&1\end{bmatrix}^T$$ Now, with $\bf I$ being identity matrix and ${\bf x}^T = [x_1,\cdots,x_k]$ $$[{\bf I_2} \otimes {{\bf 1}}^T] {\bf \begin{bmatrix}\bf I\\\bf T\end{bmatrix}x}=\begin{bmatrix}\Phi_1\\\Phi_2\end{bmatrix}$$

This does not utilize any number theoretic knowledge of the problem, only linear algebra.

For computational purposes we might want to do substitution $$\cases {t_k = x_{k+1}-x_{k}\\t_1=x_1}$$ This allows us to express the above using $\bf D$ matrix instead which for large $k$ will be much sparser:

$${\bf D} = \begin{bmatrix}1&0&0\\-1&1&0\\0&-1&1\end{bmatrix}$$

Only two non-zero diagonals.

Answer 3

As you noted:

$$ x_2 + 2 x_3 + \ldots + (k-1) x_k = \Phi_2 - \Phi_1 \tag{1}$$ Subtract from the first equation, obtaining $$ x_1 - x_3 - 2 x_4 - \ldots -(k-2) x_k = 2 \Phi_1 - \Phi_2 \tag{2}$$

Given integers $\Phi_1, \Phi_2, x_3, \ldots, x_k$, equations (1) and (2) determine integers $x_1$ and $x_2$. Now if you want the $x_i \ge 0$, you need $$ \eqalign{\Phi_2 - \Phi_1 - 2 x_3 - 3 x_4 - \ldots - (k-1) x_k &\ge 0\cr 2 \Phi_1 - \Phi_2 + x_3 + 2 x_4 + \ldots + (k-2) x_k &\ge 0\cr} \tag{3}$$ which can be rearranged as bounds for $x_3$: $$\frac{\Phi_2 - \Phi_1 - 3 x_4 - \ldots - (k-1) x_k}{2} \ge x_3\ge -2 \Phi_1 + \Phi_2 - 2 x_4 - \ldots - (k-2) x_k \tag{4}$$

The condition for the upper bound to be greater than or equal to the lower is: $$ 3 \Phi_1 - \Phi_2 + x_4 + 2 x_5 + \ldots + (k-3) x_k \ge 0 \tag{5}$$

Let $x_4, \ldots, x_k$ be any natural numbers such that (5) is true. Then $x_3$ can be any natural number satisfying (4), and $x_1$ and $x_2$ are obtained from (2) and (1).

However, you want $x_3 \ge 0$, so that imposes a requirement

$$ \Phi_2 - \Phi_1 - 3 x_4 - \ldots - (k-1) x_k \ge 0 \tag{6}$$

And (5) and (6) translate to lower and upper bounds on $x_4$. And so on...