# Every polyhedron $P \ne \mathbb{K}^n$ equals an intersection of finitely many half spaces.

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.

• How is the relation $\leq$ defined? – Mikhail Katz Aug 20 '14 at 10:27
• @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. – DracoMalfoy Aug 20 '14 at 16:22
• @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. – 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.