# Solution to underdetermined linear equations

I have some unknown numbers $x_i$ and I know only certains sums $y_i$ over them:

$\mathbf{A}\mathbf{x}=\mathbf{y}$

where this equation is underdetermined. Moreover, due to the origin of the problem I know that all $x_i>0$ are positive. I do know all $A_{ij}\in \{0,1\}$.

Do you know a way to find a solution? One "average and simple" solution would suffice.

EDIT: Some more information for that particular problem. All $x_i>0$ and $y_i>0$ and all $A_{ij}\in \{0,1\}$. There are more $x_i$ than $y_i$. And there are a lot of them, so that the method to solve it should be simple for the computer :) Something iterative would be nice.

-
It all depends: how many $\,x_i's\,,\,y_i's\,$ are there? Are there some zero or negative $\,y_i's\,$? This kind of problems can be easily (more or less) solved by means of matrix theory within linear algebra. – DonAntonio Dec 14 '12 at 14:40
You have to regularize the problem. For instance, by imposing an $L_2$ norm (determine $x$'s such that the sum of their squares is minimal). – Johannes Dec 14 '12 at 15:04
@Johannes: For that particular problem I'm not sure what the most sensible real-world regularization is. Maybe all $x_i$ should be concentrated maybe spread. I actually think making them rather spread and equal would be better. But any suggestion for an easy algorithm will do for now. – Gerenuk Dec 14 '12 at 15:17

The solution is given by

$$x = A^T (A A^T )^{-1}y .$$

Here is the reference.

-
Sounds pretty good for a simple answer :) Will this give me positive $x_i$? Is there any simplification for the inverse if I only have 0/1 entries? – Gerenuk Dec 14 '12 at 15:55
@Gerenuk: See here. – Mhenni Benghorbal Dec 14 '12 at 16:11
Thanks. Do you think with this method some $x_i$ can become negative? – Gerenuk Dec 14 '12 at 16:14
@MhenniBenghorbal The OP asks for a positive solution. Your answer does not promise that. For example, consider $A=\begin{pmatrix}1&0&1\\0&1&1\end{pmatrix}$ and $y=(3,1)^T$. Obviously $Ax=y$ has a positive solution, but $A^T(AA^T)^{-1}y=\frac13(5,-1,4)^T$ isn't one. Not to mention that $AA^T$ may be singular for a general binary matrix $A$. – user1551 Dec 14 '12 at 17:31
What's the downvote for? Why do you ask since you do not care, as you have shown again and again? Somebody who cares would not react to @user1551's fully justified remark with the shameful comment you posted. – Did Dec 19 '12 at 18:07

Although a bit inelegant, you may try to convert the problem into a linear programming problem: \begin{align} \textrm{maximize }&\ 0\\ \textrm{subject to }&\ Ax=y,\\ &\ x_i\ge0, \textrm{ for all } i. \end{align} (It's not elegant because we actually have nothing to maximize here; we just want to find a feasible $x$.) You may search the internet for "simplex method", or look up any undergraduate textbook on operations research to see how to solve the above linear program (sec. 10.8 the online version of the 2/e of Numerical Recipes also describes the simplex algorithm).

In the standard formulation of a linear program, each $x_i$ is only nonnegative. Some software libraries allow you to specify strict inequalities. If not, you may roll your own modified version of the simplex method, but you need to learn the details of the simplex method first.

-