1

I want to show that a non-empty polyhedron $P=P(A,b)$ is unbounded iff $P(A,0)\neq \{0\} $

Definition: A Polyhedron is the set of points, satisfying the inequalities $Ax≤b$, where $A$ is a matrix and $b$ a vector.

For example, looking at the Matrix C: $\qquad C=\begin{pmatrix} 1\qquad 1\\ 1\quad -1\\-1\qquad 1\\ -1\quad -1\\\end{pmatrix}\qquad$ I can see that for $d=0,\;$ $P(C,d)=\{0\}$ and that for any $d\neq0$ $P$ is also bounded, however a formal proof does not come to mind.

Any help on this is highly appreciated!

user619755
  • 620

1 Answers1

1

It is easy to see that $P(A,b)=\{x \, | \, Ax\le b\}=\{x \, | \, Ax=c \ \text{ such that } \ c\le b\}=$ $N(A)+\cup_{c\le b }P_s(c),$ where $P_s(c)$ is a singleton set with one particular solution of the system $Ax=c$ or it is empty if this system does not have solution, and $N(A)$ denotes the null space of $A$.

To see that $\{x \, | \, Ax=c \ \text{ such that } \ c\le b\}=N(A)+\cup_{c\le b }P_s(c)$, assume $x\in \{x \, | \, Ax=c \ \text{ such that } \ c\le b\}$, so $Ax=c$ for some $c\le b$, thus $x\in N(A)+P_s(c)\subset N(A)+\cup_{c\le b }P_s(c)$. Conversely, assume that $x\in N(A)+\cup_{c\le b }P_s(c)$, so we have $x=z+y$ such that $z\in N(A)$ and $Ay=c$ for some $c\le b$. This umplies that $A(x)=A(z+y)=Az+Ay=Ay=c\le b$. So, $x\in\{x \, | \, Ax\le b\}=\{x \, | \, Ax=c \ \text{ such that } \ c\le b\}$.

As a result, $P(A,0)=\{x \, | \, Ax=c \ \text{ such that } \ c\le 0\}=N(A)+\cup_{c\le 0 }P_s(c),$

Having the proved equality in mind, consider two cases:

If $N(A)\ne \{0\}$, it means it is unbounded (nontrivial subspace), and, from the proved equality, we see the result of interest holds.

If $N(A)=\{0\}$, then $P(A,b)$ is unbounded iff $\cup_{c\le b }P_s(c)$ is unbounded. The latter is unbounded iff $\cup_{c\le 0 }P_s(c)$ is unbounded: because for any possible $x\in \cup_{0\le c\le b }P_s(c)$, we have $\|x\|_2\le \|A^{\dagger}\|_2\|b\|_2$, where $A^{\dagger}=(A^TA)^{-1}A^T$.

Sam
  • 364