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

The first $A\bar{x}\leq \bar{b}$ is stated to be convex in my book but why?

I cannot see it directly from the definition:

Let $S :=\{\sum \lambda_{i} x_{i} \}$.

$\text{S is a convex space iff } \begin{cases} \sum \lambda_{i} = 1 \\ \lambda_{i} \in [0,1]\\ \lambda_{i} \geq 0 \\ \end{cases} $

share|cite|improve this question
You are confused about the definition. Examine the answer and see if that helps. – GEdgar Oct 18 '11 at 23:47
up vote 3 down vote accepted

We shall prove that the set $S = \{x : Ax \leq b \}$ is convex. The same proof works for $Ax \geq b$.

Consider any $n \in \mathbb{N}$. Consider $n$ elements in $S$. Call them $x_1,x_2,\ldots,x_n$ i.e. $x_k \in S$ for $k \in \{1,2,\ldots,n\}$.

Consider $n$ scalars $\lambda_j$ such that $\displaystyle \sum_{j=1}^{n} \lambda_j = 1$. We want to show that $x = \displaystyle \sum_{j=1}^{n} \lambda_j x_j \in S$.

Since $x_j \in S$, we have $Ax_j \leq b$. Hence, we get $$Ax = A \left( \displaystyle \sum_{j=1}^{n} \lambda_j x_j \right) = \displaystyle \sum_{j=1}^{n} A \left(\lambda_j x_j \right) = \displaystyle \sum_{j=1}^{n} \lambda_j A x_j \leq \displaystyle \sum_{j=1}^{n}\lambda_j b = \left(\displaystyle \sum_{j=1}^{n} \lambda_j \right) b = b$$ Hence, we have $$Ax \leq b.$$ Hence, $S$ is a convex set.

share|cite|improve this answer
what about the space $Ax < b$ or the space $Ax > b$? – hhh Oct 19 '11 at 0:10
@hhh: the same thing holds and the same proof works. – user17762 Oct 19 '11 at 0:23

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.