Polyhedron is unbounded iff it has direction

Dependencies:

  1. Polyhedral set and polyhedral cone
  2. Direction of a convex set and Recession cone
  3. Basic feasible solutions
  4. Point in polytope is convex combination of BFS
  5. Convex hull of a finite number of points in Euclidean space is bounded

Let $P \defeq \{x \in \mathbb{R}^n: (a_i^Tx \ge b_i, \forall i \in I) \textrm{ and } (a_i^Tx = b_i, \forall i \in E)\}$. Then $P$ is unbounded iff it has a non-zero direction $d$.

Proof

Suppose $P$ has a non-zero direction $d$. Since $d \neq 0$, $\exists k \in [n]$ such that $d_k \neq 0$. Let $\xhat \in P$. Then $\xhat + \lambda d \in P$ for all $\lambda \ge 0$. By making $\lambda$ arbitrarily large, $(\xhat + \lambda d)_k$ can be made arbitrarily large, and so $\|\xhat + \lambda d\|$ can be made arbitrarily large. Hence, $P$ is unbounded.

Suppose $P$ doesn't have a non-zero direction. Then $P$ doesn't contain a ray. Hence, any point in $P$ can be represented as a convex combination of at most $n+1$ BFSes of $P$. Let $X$ be the set of BFSes of $P$. Then $P$ is the convex hull of $X$. Hence, $P$ is bounded.

Dependency for:

  1. Bounded section of pointed cone

Info:

Transitive dependencies:

  1. /linear-algebra/matrices/gauss-jordan-algo
  2. /linear-algebra/vector-spaces/condition-for-subspace
  3. /sets-and-relations/equivalence-relation
  4. Group
  5. Ring
  6. Polynomial
  7. Field
  8. Vector Space
  9. Cone
  10. Convex combination and convex hull
  11. Convex set
  12. Convex hull of a finite number of points in Euclidean space is bounded
  13. Direction of a convex set and Recession cone
  14. Transitivity of convexity
  15. Linear independence
  16. Span
  17. Integral Domain
  18. Comparing coefficients of a polynomial with disjoint variables
  19. Semiring
  20. Matrix
  21. Polyhedral set and polyhedral cone
  22. Basic feasible solutions
  23. Stacking
  24. System of linear equations
  25. Product of stacked matrices
  26. Matrix multiplication is associative
  27. Reduced Row Echelon Form (RREF)
  28. Elementary row operation
  29. Every elementary row operation has a unique inverse
  30. Row equivalence of matrices
  31. Matrices over a field form a vector space
  32. Row space
  33. Row equivalent matrices have the same row space
  34. RREF is unique
  35. Identity matrix
  36. Inverse of a matrix
  37. Inverse of product
  38. Elementary row operation is matrix pre-multiplication
  39. Row equivalence matrix
  40. Equations with row equivalent matrices have the same solution set
  41. Rank of a matrix
  42. Basis of a vector space
  43. Linearly independent set is not bigger than a span
  44. Homogeneous linear equations with more variables than equations
  45. Rank of a homogenous system of linear equations
  46. Condition for existence of BFS in a polyhedron
  47. Point in polytope is convex combination of BFS