# How to find solutions for linear equation?

I want to find the possible values for {$x_i$} for given that I know $y$, {$p_i$} and the sum of $x_i$. In other words, let:

$$x_1 \cdot p_1 + x_2 \cdot p_2 + \cdots + x_n \cdot p_n = y$$

$$\sum_{i=1}^n x_i = k$$

Example:

$$11 x_1 + 22 x_2 + 44 x_3 = 66$$

$$x_1+x_2+x_3 = 2$$

would result in the solution: $x_1 = 0, x_2 = 1, x_3 = 1$.

I wonder if this has to be done by brute force with trying all possible combinations or if there are smarter algorithms for this kind of problem.

What kind of problem is this at all? Not being a mathematician i even don't know what to search for (and probably asked totally wrong - Sorry).

Please feel free to improve the question and add better tags.

-

## migrated from stats.stackexchange.comNov 21 '11 at 20:31

This question came from our site for people interested in statistics, machine learning, data analysis, data mining, and data visualization.

Do you mean for $k$, $y$, the $x_i$ and the $p_i$ all to be non-negative integers? or are they allowed to be arbitrary reals? or what? – Gerry Myerson Nov 21 '11 at 21:57
X(i) and k are count of units (non-negative integers), y and p(i) are amounts of money with up to two significant digits with the data i want to apply an algorithm to. – Frank Martin Nov 21 '11 at 22:23
OK, then what you have is a system of linear diophantine equations, and that's what you want to look for. – Gerry Myerson Nov 21 '11 at 23:54
@Gerry: i would be happy to accept this answer - please change your comment to an answer so that i can do so :-) – Frank Martin Nov 22 '11 at 10:18
Done.${}{}{}{}$ – Gerry Myerson Nov 22 '11 at 11:39

## 2 Answers

Per request of OP: it's a problem in diophantine equations, more specifically in systems of linear diophantine equations.

-

While this question may make more sense at math.SE, for what it is worth you should review the topic of linear algebra and in particular how to solve a system of linear equatiions.

Your system of equations may have one unique solution, may have no solution or multiple (infinite) solutions depending on the nature of the system. See the link above for more details.

The problem moves from the domain of math to statistics if you assume that $y$ is measured with error. In other words, instead of an exact decomposition of $y$ into its constituent components, you have something like the below:

$$y = x_1 \cdot p_1 + x_2 \cdot p_2 + ... x_n \cdot p_n + \epsilon$$

where $\epsilon$ is an error term that captures uncertainty in the measurement of $y$.

If your situation is such that uncertainty in $y$ needs to be taken into account (as the above) then you should start with a review of linear regression.

-
OP writes about "trying all possible combinations," which makes sense only if OP intends for all variables to be nonnegative integers. If that's the case, then we're not talking linear algebra, we're talking number theory (in particular, diophantine equations) and/or combinatorics. – Gerry Myerson Nov 21 '11 at 21:56