For polyhedron $P$, vector $a$, scalar $b$, prove that $Q:=\{x\in P:a^tx\leq b\}$ is a polyhedron. Also, can $Q=P$?

412 Views Asked by At

Let $P$ be a polyhedron in $\mathbb{R}^n, a\in\mathbb{R}^n$ a vector, and $b\in\mathbb{R}$ a scalar. Consider the set $Q=\{x\in P:a^tx\le b\}$

$a)$ Prove that $Q$ is a polyhedron

$b)$ Is it always possible to choose $b$ in such way so that $Q=P$? Explain your answer


Definition of polyhedron

A polyhedron is the intersection of finitely many halfspaces: $$P=\{x∈\mathbb{R}^n,a^tx≤b\}$$

$a)$

Proof

Let $Q:=\{x\in P:a_0^tx\le b\}$

Show that $Q$ is the intersection of finitely many half-spaces

Since $P$ is a polyhedron we have $$\exists a_1^t\dots a_n^t\in\mathbb{R}^n,c_1\dots c_n\in\mathbb{R},s.t.$$

$$P=\{x\in\mathbb{R}^n:a_1^tx\le c_1\}\cap\dots\cap\{x\in\mathbb{R}^n:a_n^tx\le c_n\}$$

$$=\{x∈\mathbb{R}^n:a_1^tx≤c_1\wedge\dots\wedge a_n^tx\le c_n\}$$

Then

$$Q=\{x\in P:a_0^tx\le b\}=\{x\in \mathbb{R}^n:x\in P\wedge a_0^tx\le b\}$$

$$=\{x\in \mathbb{R}^n:a_0^tx\le b\wedge a_1^tx≤c_1\wedge\dots\wedge a_n^tx\le c_n\}$$

$$=\{x\in \mathbb{R}^n:a_0^tx\le b\}\cap\{x\in\mathbb{R}^n:a_1^tx\le c_1\}\cap\dots\cap\{x\in\mathbb{R}^n:a_n^tx\le c_n\}$$

Which is the intersection of finite many half-spaces. $\tag*{$\square$}$

$b)$

No, consider case $n=1$ in $\mathbb{R}^2$, if $P=\{x∈\mathbb{R}^2:x_1+x_2≤0\},Q=\{x\in P:x_1-x_2\le b\}$

Where $b\in\mathbb{R}$

Then

$$Q=\{x∈\mathbb{R}^2:x_1-x_2\le b\wedge x_1+x_2≤0\}$$

For example $\left(\frac{b}{2},-\frac{b}{2}-1\right)$ is in $P$ but not in $Q$.

Since $\frac{b}{2}-\frac{b}{2}-1≤0$ that $\left(\frac{b}{2},-\frac{b}{2}-1\right)\in P$

But $\frac{b}{2}-\frac{b}{2}-1≤0\wedge\frac{b}{2}-(-\frac{b}{2}-1)\le b$ is false that $\left(\frac{b}{2},-\frac{b}{2}-1\right)\not\in Q$ for any real $b$.

That proves sometimes$$\forall b\in\mathbb{R},Q\neq P$$$\tag*{$\square$}$


$\dots$ Is my proof correct ? Any suggestions would be appreciated.

Also please tell me if there is a better method to prove it.

Thanks for your help.