Consider a system of $n$ linear equations with $n$ unknowns, all of whose coefficients and right hand sides are nonnegative integers, with a unique solution consisting of nonnegative rational numbers. Is it always possible to solve the system using restricted subtraction-moves that only let us subtract one equation from another if the coefficients and right hand side of the latter respectively dominate the coefficients and right hand side of the former? In addition to restricted subtraction, we’re also allowed to add equations without restriction, or to multiply an equation by a positive rational number.


Example (with $n=2$): To solve $2x+y=7$, $x+2y=8$, we may not subtract either equation from the other (since that would lead to a negative coefficient), but we can double the former, obtaining $4x+2y=14$, subtract $x+2y=8$ to get $3x=6$, and then multiply by $1/3$ to get $x=2$, and we can solve for $y$ in a similar way.


I do not require that at each stage one retain only $n$ equations (though if my question has an affirmative answer, that will be my next question, either here or in a separate post).



Solving systems of linear equations without introducing negative numbers
Here is a proof that it is always possible by keeping at most $n+1$ equations throughout.


Suppose the system $Ax=b$ has a unique solution $c \in \mathbb{Q}\_{\geq 0}^n$, where $A \in \mathbb{Z}\_{\geq 0}^{n \times n}$ and $b \in \mathbb{Z}\_{\geq 0}^n$. Note that the equation $x\_1=c\_1$ can be written as a linear combination of equations which appear in $Ax=b$. Thus, there exist $q\_1, \dots, q\_n \in \mathbb{Q}$ such that $\sum\_{i=1}^n q\_iA\_i=e\_1$ and $\sum\_{i=1}^n q\_i b\_i=c\_1$, where $A\_i$ is the $i$th row of $A$ and $e\_1$ is the first standard basis vector. Let $I$ be the set of indices $i$ such that $q\_i \geq 0$. The coefficients of $\sum\_{i \in I} q\_iA\_i$ dominate the coefficients of $\sum\_{i \notin I} -q\_iA\_i$, and $\sum\_{i \in I} q\_ib\_i \geq \sum\_{i \notin I} -q\_ib\_i$. Thus, we may subtract $\sum\_{i \notin I} -q\_iA\_i$ from $\sum\_{i \in I} q\_iA\_i$ to derive $x\_1=c\_1$. Then just repeat for each variable.


