Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Say we have a system of $m$ equations of the form: $$a_{11} x_1 + a_{12} x_2 + ... + a_{1n} x_n = p_1$$ $$...$$ $$a_{m1} x_1 + a_{m2} x_2 + ... + a_{mn} x_n = p_m$$ Where the $p_i,x_j \in \mathbb{R}$, but the $a_{ij}$'s are boolean values, i.e $a_{ij}\in\{0,1\}$.

So, if I want to solve for $\{a_{ij}\}$ and $\vec{x}$ for a given $\vec{p}$, a total of $(m+1)n$ variables,

  1. What are the conditions on $m$ ensuring the existence of at most one solution?
  2. Does it change anything if $p_i,x_j \in \mathbb{Z}$ instead of $\mathbb{R}$?
share|cite|improve this question
[Ignore this] Seemed like the total is $m\,(n+1)$ unknowns, but I mistook $p_i$ for the unknowns rather than $x_i$. – ccorn Jul 10 '13 at 21:30
up vote 1 down vote accepted

Here is a generic construction for this problem. Let $\vec{x} = \vec{1}$ and set all $a_{ij}=0$ except $a_{ii} = p_i$. That is a solution.

Note that this is an integer solution as well, as long as $\vec{p}$ is an integer vector.

I am surprised how you set up the problem though - typically, don't we have $a_{ij}$ fixed?

EDIT Even more than that. For any non-zero vector $\vec{x}$ there is a solution which works for any $\vec{p}$. Let $a_{ij} = 0$ when $i \neq j$ and let $a_{ii} = p_i/x_i$.

share|cite|improve this answer
$p$ is real.. but I think what you are saying is that there will always be a trivial solution.. – nbubis Jul 10 '13 at 21:35
Actually, I'm claiming there will be an uncountably multiplicity of solutions. About the integer solution: you must at least supply integer boundary conditions and then you are guaranteed that an integer solution will also exist... – gt6989b Jul 10 '13 at 21:40

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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