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.
Can an h-polyhedron be checked for boundedness efficiently? How?
Our polytope is the intersection of a collection of half-spaces in . These half-spaces are given by inequalities of the form
Assume we have a total of half-spaces which define our polytope. Then the polytope can be more compactly written as the set of all solutions to
where is an matrix.
It turns out that our polytope is bounded if and only if has only the trivial solution.
Consider what happens if has a nontrivial solution . Then for any solution to and any we have
So, can increase in magnitude arbitrarily and will always remain in the polytope.
Thankfully, checking whether has only the trivial solution can be computed using Gaussian elimination in polynomial time.