The first equation is $m_1x_1 + m_2x_2 + \cdots + m_{n}x_{n} = K$, and then
$x_1 \geq x_2 \geq x_3 \geq \cdots \geq x_{n-1} \geq x_{n}$. Rather than solving is there any method which can tell me if this is solvable or not. All the numbers numbers are positive intgers or zero.
how can I solve the following linear inequalities
2
$\begingroup$
linear-algebra
inequality
-
0@Ross - Thanks. But my understanding is that for Chinese reminder you need to have more than one equality equation. How to handle inequality like this. – 2011-03-14
1 Answers
1
Response to comment-does that mean integers is the answer to my question: But CRT will tell you when it cannot be done. If all the $m_i$ share a common factor that $K$ does not, there is no solution. If $m_1$ and $K$ have no common factor, you can pick $x_2$ through $x_n$ arbitrarily (subject to your inequalities), and solve the equation mod $m_1$. If $x_1
-
0That is why I asked what the allowable values are. If you allow reals, $x_1=12/5, x_2=x_3=0$ is a solution. If you allow integers, $x_1=3,x_2=1,x_3=-6$ is a solution. In the positive integers, there is no solution with your ordering constraints. To put in the ordering constraints, you can define variables $y_i=x_i-x_{i+1}$ up to $y_{n-1}$ and keep $x_n$. Then all the variables just have to be $\ge 0$ and usual linear programming techniques apply. – 2011-03-15