How to find the general solution set to a constrained system of linear equations

513 Views Asked by At

Consider the following general system of linear equations $$ \begin{pmatrix} a & -b\\ -c & d \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} v \\ w \end{pmatrix} $$ where $a, b, c, d \in \mathbb{N}^+$, $x, y, v, w \in \mathbb{R}^+$ so that the following constraints are also satisfied: $0 \leq v, w <e$, $0 < x,y < e$ where $e$ is the exponential constant.

I am trying to understand what the general solution set to such a system would look like. That is, for all $a, b, c, d \in \mathbb{N}^+$ and $ v, w \in \mathbb{R}^+$, what is the corresponding set of solutions $(x, y)^T$?

For example, I am unsure if every $x, y$ pair satisfying $0 < x,y < e$ is a solution to one of these general systems satisfying the constraints, or if only a subset of such $x, y$ values create the solution set to such an arbitrary system. If this is indeed the case, what would that (solution) subset be?

1

There are 1 best solutions below

2
On BEST ANSWER

According to your last paragraph it seems you are interested in the problem:

Given $0 < x, y, < \mathrm{e}$ find $a, b, c, d \in ℕ+$ and $\mathrm{e} > v, w \geq 0$ such that the above system of equations is true. Especially you want to know whether there is a solution for arbitrary $0 < x, y < \mathrm{e}$.

And the answer is that there is.

The problem can be reformulated in a following way: for given $x, y$ find $a, b, c, d \in ℕ+$: $$ \mathrm{e} > ax - by \geq 0\\ \mathrm{e} > -cx + dy \geq 0. $$

Let's take the first inequality. We can transform it -- add a term $by$ first and then divide by $bx$ (recall that $x, b > 0$ thus the inequalities don't switch the direction) to $$ \frac{y}{x} + \frac{\rm e}{bx} > \frac{a}{b} \geq \frac{y}{x}. \tag{1}\label{1} $$

Let's continue with the left hand side inequality. If we managed to find $a/b$ such that $$ \frac{y}{x} + \inf_{0 < x < \mathrm{e}} \frac{\rm e}{bx} > \frac{a}{b}\tag{2}\label{2} $$ then the LHS inequality of \eqref{1} would be fulfilled for free.

Well, let's try it. The infimum equals to $\frac{\rm e}{b{\rm e}}$. Cancel those $\rm e$ in it and replace the left inequality of \eqref{1} by \eqref{2} $$ \frac{y}{x} + \frac{1}{b} > \frac{a}{b} \geq \frac{y}{x}. $$

Now take the positive real number $y/x$ and round it upwards to the first decimal place. The error is clearly less than 1/10 and since it is rounded upwards it is at least 1/10. In other words: $$ \frac{y}{x} + \frac{1}{10} > \frac{a}{10} \geq \frac{y}{x}, $$ where $a/10$ is the rounded value. Clearly, $a \geq 1$ as the value is at least $1/10$. Thus, you have found $a, b \in ℕ+$ and it suffices to set $v = ax - by$.

The second inequality can be solved in the same way.