1
$\begingroup$

Let $P=\{x \in \mathbb{R}^n \mid Ax \geq b\}$ be a nonempty polyhedron for a matrix $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^{m}$. Show that a nonempty intersection of $P$ and an affine set in $\mathbb{R}^{n}$ is a polyhedron.

To show this I just know that an affine set in $\mathbb{R}^{n}$ can be written as a subspace $L$ in $\mathbb{R}^{n}$ plus some $u$ in $\mathbb{R}^{n}$, that is

$$ L= \{v: cv=0\} $$

$$ u+L=\{u+v \mid v \in N(C)\} \,\,\,\text{or}\,\,\, u+L = \{z \mid Cz=d\} $$ where $d=Cu$.

To show the claim I need to assume $x$ is in $P$, so

$$ Ax \geq b $$

Also, $x \in u+L$, i.e., $Cx=d$ where $d=Cu$.

Now I need to show there exist an $A'$ and $b'$ where $A'x \geq b'$. How can I proceed?

$\endgroup$
1
$\begingroup$

Hint: first express your affine space as a system of linear equations $Cx = d$. Then append the rows of $C$ and $-C$ to $A$ to form a taller matrix $A$, as well as append $d$ and $-d$ to $b$ to form a taller column vector $b'$. Then the inequality $A'x \le b'$ describes the intersection.

$\endgroup$
  • $\begingroup$ I think I got what you mean, just change the last $\leq$ to $\geq$. $\endgroup$ – Saeed Dec 8 '18 at 5:02

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.