# 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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 35, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.9648508429527283, "perplexity": 2782.6591798858635}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2020-05/segments/1579251694071.63/warc/CC-MAIN-20200126230255-20200127020255-00210.warc.gz"}