# Why can't the hyperplane H intersected with polyhedral set S contain any line…

S is the polyhedral set

$S = \{ \mathbf{x} \in \mathbb{R}^{n} ; \mathbf{Ax}=\mathbf{b}, \mathbf{x} \ge \mathbf{0} \}$

and

$H : \mathbf{c}^{T}\mathbf{x} = \beta$

with

$\min_S ( \mathbf{c}^{T}\mathbf{x} )= \beta$

My textbook states that given the above, the set $S \cap H$ contains no line since $\mathbf{x} \ge \mathbf{0}$ in $S$. But I don't understand why.

-

## 1 Answer

Any line in $\mathbb R^2$ can be written as $$L = \left\{ \left(\begin{matrix}x \\ y\end{matrix}\right) + t \left(\begin{matrix}u \\ v\end{matrix}\right) : t \in \mathbb R \right\}$$ where $u$ and $v$ are not both zero. For some choice of $t$, either $x+tu < 0$ or $y + tv < 0$. So $L$ contains a point $\mathbf x$ that does not satisfy $\mathbf x \geq 0$. So $L$ cannot be contained in $S$ (and hence not in $S\cap H$, no matter what $H$ is).

-
I just realised that I put R^2 where it should have been R^n. But I guess what you are saying is true for R^n as well. Thank you. – evading Nov 24 '12 at 21:09
Yes, it works just the same in $\mathbb R^n$. – marlu Nov 25 '12 at 13:05