# Show that intersection of a polyhedron and affine set is a polyhedron.

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?

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.
• I think I got what you mean, just change the last $\leq$ to $\geq$. – Saeed Dec 8 '18 at 5:02