Currently, I am reading some lecture notes on linear optimisation. I cannot see why the following (seemingly trivial) proposition holds. (How could I understand/proove it?)

Every polyhedron $P \ne \mathbb{K}^n$ equals an intersection of finitely many half spaces. ($\mathbb{K}$ is a field, $\mathbb{K}^n$ seems to be a vector space.)

Please note that the lecture notes define that a polyhedron is a set which may be represented using the form $$P = \{x \in \mathbb{K}^n \mid Ax \le b\}$$ where $A$ is a matrix and $b$ is a vector.

Hint: Prior to the mentioned proposition, the lecture notes state: If (i) a row of $A$ equals the zero vector and (ii) the corresponding component of $b$ is non-negative, then the row may be omitted; the omission does not affect $P$. I totally get this statement. However, if I am supposed to use it, I cannot see how.

  • $\begingroup$ How is the relation $\leq$ defined? $\endgroup$ Aug 20 '14 at 10:27
  • $\begingroup$ @user72694 We were able to solve it! Anyway: We found out that we were supposed to use $\mathbb{K} \in \{\mathbb{Q}, \mathbb{R}\}$ and the canonical ordering. $\endgroup$ Aug 20 '14 at 16:22
  • $\begingroup$ @dracomalfoy: It would be nice if you could edit your questiuon to include this $\mathbb K\in\{\mathbb Q,\mathbb R\}$ and then post an answer to your own question, including the solution you found. That way the question can help others. $\endgroup$
    – MvG
    Aug 21 '14 at 10:38

I think that the half-space are defined from the inequalities in the $Ax \leq b$ system. So we have to suppose that there are finitely many of those.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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