1
$\begingroup$

The input consists of two integers $n\geq 2$ and $K\geq 2$, and a vector of positive integers $b$ of size $n$. We assume that $\sum_i b_i$ is a multiple of $K$.

The output is a matrix $A(n\times n)$ where each entry belongs to $\{0,1,...,K\}$ and where each column must sum to $K$.

We must have $Ax\geq b$ and $\sum_i x_i$ must be minimized. It is easy to see that the optimal value for $\sum_i x_i$ is $\frac{\sum_i b_i}{K}$, a corresponding matrix $A$ is for example the identity matrix multiplied by $K$ : $A=KI_n$.

My question is the following: for a given input, we know the optimal value of $\sum_i x_i$, but is there a matrix $A$ for which $\sum_i x_i$ is optimal and for which each component of $x$ is integer ?

Here is an example with $n=2$, $K=3$ and $b=(10\hspace{0.3cm}2)^T$. We have $\sum_i b_i=12$ which is a multiple of $K=3$.

As described above, an easy solution is: $$\begin{pmatrix}3 & 0 \\ 0 & 3\end{pmatrix}\begin{pmatrix}x_1 \\ x_2\end{pmatrix}\geq \begin{pmatrix}10 \\ 2\end{pmatrix},$$ it leads to $x_1=\frac{10}{3}$ and $x_2=\frac{2}{3}$. Now the question is: is there a matrix $A$ (with the constraints described above) such that $x_1+x_2=4$ where $x_1$ and $x_2$ are integers? It appears that it is yes in this case: $$\begin{pmatrix}2 & 3 \\ 1 & 0\end{pmatrix}\begin{pmatrix}x_1 \\ x_2\end{pmatrix}\geq \begin{pmatrix}10 \\ 2\end{pmatrix},$$ for which $x_1=2$ and $x_2=2$.

Up to now, I did not find any example where there is no integer solution. But is there a way to prove it ? Or is it not true ?

Thank you very much for your help.

$\endgroup$
3
  • $\begingroup$ It reduces to solving linear integer equations. For a two by two matrix, say $b_1 + b_2 = ck$, then the existence of a matrix A is equivalent to the solution of $a_1x_1 + a_2x_2 = b_1$. Given $x_1 + x_2 = c$, it reduces to $(a_1 - a_2)x_1 = b_1 - a_2c$, which always have integer solutions. Just choose $a_2 = [b_1/c]$, and then $a_1 = a_2 + 1$. The general case can also be reduced to solving system of linear equations which I think always have solutions with similar choices. $\endgroup$
    – Thanh Vu
    Oct 16, 2015 at 1:51
  • $\begingroup$ @ThanhVu When you say $a_1x_1+a_2x_2=b_1$, what are $a_1$ and $a_2$? Do you mean $a_{11}$ and $a_{12}$? And the sum of each column of $A$ must also be equal to $K$... Thanks! $\endgroup$ Oct 16, 2015 at 9:09
  • $\begingroup$ yes, since the sum of each column equal to K so it suffices to determine $a_{11}, a_{12}$. Indeed the general case can also be done like that. So the answer to your question is yes. Such an $A$ always exist. $\endgroup$
    – Thanh Vu
    Oct 17, 2015 at 13:31

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.