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?

  • $\begingroup$ Are you sure you want $ax=by$ and $cx=dy$ ? If the answer is yes, your LHS is the zero vector. $\endgroup$ – GreginGre Nov 27 '19 at 15:16
  • $\begingroup$ @GreginGre sorry, my mistake, I am not sure why I put that in there. No that constraint is not necessary. I updated the question to accurately reflect what I am asking. $\endgroup$ – Grassi Nov 27 '19 at 15:37
  • $\begingroup$ I am still not sure what you are asking. Unless $ab+cd=0,$ which happens in very few cases,your $2\times 2$ matrix is invertible, and you can write up the unique solution in terms of $v,w$. Precisely $(x,y)=((ad+bc)^{-1} (dv+bw), (ad+bc)^{-1}(cv+aw)$. Do you want to know when this solution satisfy $0<x,y<e$ provided $0<v,w< e?$ It will certainly depend on $a,b,c,d$. $\endgroup$ – GreginGre Nov 27 '19 at 16:33
  • $\begingroup$ @GreginGre then for any $x, y$ such that $0<x,y,<e$ does there exist a $a, b, c, d, v, w$ (under the given constraints) such that $(x,y)=((ad+bc)^{-1} (dv+bw), (ad+bc)^{-1}(cv+aw)$? $\endgroup$ – Grassi Nov 27 '19 at 16:37
  • $\begingroup$ Yes. $a=1,b=0,c=0,d=1, v=x,w=y$ should work. UNless $\mathbb{N}^+$ denotes $\{1,2,3,....\} ?$ $\endgroup$ – GreginGre Nov 27 '19 at 16:38

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.

  • $\begingroup$ Thank you, this certainly clears a lot up. However would you be able to go into more detail about how you manipulated the original inequalities to get the new ones you worked with? I am unclear as to what some of those intermediate operations were. If so I am happy to close the question with the bounty. $\endgroup$ – Grassi Nov 28 '19 at 1:58
  • $\begingroup$ I have edited the answer and added more detail there @Grassi. $\endgroup$ – user254873 Nov 28 '19 at 7:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.