# H-Polyhedron Boundedness

This is another question from quora. Not only is the question interesting in its own right, but the answer also reveals a nice application of a fundamental idea in linear algebra.

## Question

Can an h-polyhedron be checked for boundedness efficiently? How?

Absolutely!

Our polytope is the intersection of a collection of half-spaces in $\mathbb{R}^n$. These half-spaces are given by inequalities of the form

$a_1 x_1 + a_2 x_2 + \cdots + a_n x_n \leq b_1.$

Assume we have a total of $m$ half-spaces which define our polytope. Then the polytope can be more compactly written as the set of all solutions to

$Ax \leq b$

where $A$ is an $m \times n$ matrix.

It turns out that our polytope is bounded if and only if $Ax = 0$ has only the trivial solution.

Consider what happens if $Ax = 0$ has a nontrivial solution $x_0$. Then for any solution $x$ to $Ax \leq b$ and any $\varepsilon \gt 0$ we have

$A(x + \varepsilon x_0) = Ax + \varepsilon A x_0 = Ax + 0 \leq b.$

So, $x + \varepsilon x_0$ can increase in magnitude arbitrarily and will always remain in the polytope.

Thankfully, checking whether $Ax = 0$ has only the trivial solution can be computed using Gaussian elimination in polynomial time.