Solving systems of linear equations without introducing negative numbers

Question

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).

Answer 1

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.

Answer 2

Yes, it is always possible. Rather than prove the general result, and drown in a sea of subscripts, I'll work through an example, and expect it to be clear how the general case works.

Let's solve the system, $$ \matrix{8x+y+6z=15\cr3x+5y+7z=15\cr4x+10y+2z=16\cr} $$ which has the unique solution $x=y=z=1$.

We consider the matrix of $x$ and $y$ coefficients: $$ \pmatrix{8&1\cr3&5\cr4&10\cr} $$ The rows must be linearly dependent over the rationals, indeed, over the integers. (In the general case, we'd have an $n\times n-1$ matrix). A linear relation is given by $$ 10(8,1)+37(4,10)=76(3,5) \qquad[=(228,380)] $$ so multiply our first equation by $10$ and add to it $37$ times the third equation, also multiply the second equation by $76$ to get the system, $$ \matrix{228x+380y+134z=742\cr228x+380y+532z=1140\cr4x+10y+2z=16\cr} $$ Subtract the first equation from the second to get $$ \matrix{228x+380y+134z=742\cr0x+0y+398z=398\cr4x+10y+2z=16\cr} $$ Divide the second equation by $398$, then subtract appropriate multiples of it from the other two equations to get $$ \matrix{228x+380y+0z=608\cr0x+0y+z=1\cr4x+10y+0z=14\cr} $$ and we are down to the case $n=2$.

In general, each time we run through this procedure, we find the value of one unknown, so reduce the number of unknowns by one.