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

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 , $$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?

• Are you sure you want $ax=by$ and $cx=dy$ ? If the answer is yes, your LHS is the zero vector. – GreginGre Nov 27 '19 at 15:16
• @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. – Grassi Nov 27 '19 at 15:37
• 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$. – GreginGre Nov 27 '19 at 16:33
• @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)$? – Grassi Nov 27 '19 at 16:37
• Yes. $a=1,b=0,c=0,d=1, v=x,w=y$ should work. UNless $\mathbb{N}^+$ denotes $\{1,2,3,....\} ?$ – 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.

• 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. – Grassi Nov 28 '19 at 1:58
• I have edited the answer and added more detail there @Grassi. – user254873 Nov 28 '19 at 7:38