# When does solution of $Ax = b$ exists, with $x_i \in [0, 1] ~\forall i \in \{1, \ldots, N\}$?

Suppose to have the following linear system: $$Ax = b$$ where $x, b \in \mathbb{R}^N$ and $A \in \mathbb{R}^{N\times N}$. Suppose also that $A = \{a_{i,j}\}$ has the following properties:

1. $a_{i,j} \geq 0 ~ \forall i,j \in \{1, \ldots, N\}$
2. $a_{i,i} = 0 ~ \forall i \in \{1, \ldots, N\}$
3. $\displaystyle\sum_{j=1}^N a_{i,j} = 1 ~ \forall i \in \{1, \ldots, N\}$
4. $\det{A} \neq 0$

Now, let's define $S \subset \mathbb{R}^N$ as follows:

$$S = \{x \in \mathbb{R}^N : x_i \in [0, 1] ~\forall i\}$$

What are the conditions on $A$ and $b$ that allow to say that $x = A^{-1}b \in S$?

Let's $X$ be the set of solutions when $\det{A} = 0$. What can I say about $X \cap S$?

Here is a results I was able to derive in a particular case.

Suppose that $b_i = \beta \in [0, 1] ~ \forall i \in \{1, \ldots, N\}$ and $\det(A) \neq 0$. Denote with $u$ the vector which all entries are equal to $1$. It turns out that $u$ is an eigenvector of $A$ with eigenvalue $\lambda_u = 1$. Then.

$$Au = u \Rightarrow u = A^{-1}u$$

Now, consider the unique solution of the system $x = A^{-1}b$. We know by definition that $b = \beta u$ and then:

$$x = \beta A^{-1}u = \beta u$$

This means that each $x_i = \beta \in [0, 1] ~ \forall i \in \{1, \ldots, N\}$ and hence $x \in S$.

-
$A^{-1}$Exists $\iff det(A) \neq 0$ –  Ale Jan 31 '14 at 17:04
@Ale I know that... I'm not asking when a unique solution exists... –  the_candyman Jan 31 '14 at 17:05
This was only a hint to the question $\text{"What are the condition an A and b that allow to say that} x= A^{-1}b$ –  Ale Jan 31 '14 at 17:06
@Ale "...to say that $x = A^{-1}b \in S$?"... you forgot $S$! –  the_candyman Jan 31 '14 at 17:08

Obviously, $b\in AS$. And $AS$ is the convex body determined by the images of the vertices of $S$. Is this enough for you?
I don't understand what you mean with $AS$. $A$ is a matrix, while $S$ is a set... –  the_candyman Jan 31 '14 at 20:05
The image set $AS=\{Ax\vert x\in S\}$. –  Martín-Blas Pérez Pinilla Jan 31 '14 at 20:40
Ok, that's right. But can I derive some properties on $A$ and $b$ such that $b \in AS$ without testing if $b \in AS$? –  the_candyman Jan 31 '14 at 20:53
Testing $b\in AS$ is the obvious way. $AS$ is a hyper-parallelepiped (a deformed hypercube). –  Martín-Blas Pérez Pinilla Jan 31 '14 at 20:57
Ok, it seems that $AS \subseteq S$, right? –  the_candyman Feb 1 '14 at 3:48