Condition for polyhedral cone to be pointed

Dependencies:

  1. Polyhedral set and polyhedral cone
  2. Basic feasible solutions
  3. Extreme point of a convex set
  4. Rank of a matrix
  5. Condition for existence of BFS in a polyhedron
  6. Condition for a point to be extreme

Let $C = \{x \in \mathbb{R}^n: (a_i^Tx \ge 0, \forall i \in I) \textrm{ and } (a_i^Tx = 0, \forall i \in E)\}$ be a polyhedral cone. Let $A$ be the matrix whose rows are $\{a_i: i \in I \cup E\}$. Then the following are equivalent:

  1. $C$ is pointed (i.e., $x \in C - \{0\} \implies -x \not\in C$)
  2. $C$ has a BFS.
  3. $C$ doesn't contain a line.
  4. $\rank(A) = n$.

Furthermore, if $C$ is pointed, $0$ is the unique BFS of $C$, and $0$ is the unique extreme point of $C$.

Proof

Lemma: $C$ is pointed iff $C$ doesn't contain a line.

Proof: If $C$ contains the line $\{\lambda x: \lambda \in \mathbb{R}\}$, where $x \neq 0$, then $x \in C - \{0\}$ but $-x \in C$, so $C$ is not pointed.

If $C$ is not pointed, $\exists x \in C - \{0\}$ such that $-x \in C$. By the definition of cone, $\lambda x \in C, \forall \lambda \in \mathbb{R}$. Hence, $C$ contains a line. So, $C$ is pointed iff $C$ doesn't contain a line. □

Lemma: $C$ contains a line iff $C$ has a BFS iff $\rank(A) = n$.

Proof: Follows from the condition for existence of BFS in a polyhedron. □

Lemma: If $C$ is pointed, then $0$ is the unique extreme point of $C$.

Proof: $0 \in C$. $0$ is an extreme point of $C$ by the condition for a point to be extreme. If $v \in C - \{0\}$, then $v$ is the midpoint of $v/2$ and $3v/2$, so it's not an extreme point. □

Lemma: If $C$ is pointed, then $0$ is the unique BFS of $C$.

Proof: $0$ is tight for all constraints of $C$. Since $\rank(A) = n$, we get that $0$ is a BFS of $C$. Let $v \in C$ be a BFS of $C$. Let $B$ be a matrix whose rows are $\{a_i: i \in I \cup E \textrm{ and } a_i^Tv = 0\}$. Then $Bv = 0$. Since $\rank(B) = n$, we get $v = 0$. □

Dependency for:

  1. Representing point in full-rank polyhedron
  2. 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. Extreme point of a convex set
  13. Condition for a point to be extreme
  14. Linear independence
  15. Span
  16. Integral Domain
  17. Comparing coefficients of a polynomial with disjoint variables
  18. Semiring
  19. Matrix
  20. Polyhedral set and polyhedral cone
  21. Basic feasible solutions
  22. Stacking
  23. System of linear equations
  24. Product of stacked matrices
  25. Matrix multiplication is associative
  26. Reduced Row Echelon Form (RREF)
  27. Elementary row operation
  28. Every elementary row operation has a unique inverse
  29. Row equivalence of matrices
  30. Matrices over a field form a vector space
  31. Row space
  32. Row equivalent matrices have the same row space
  33. RREF is unique
  34. Identity matrix
  35. Inverse of a matrix
  36. Inverse of product
  37. Elementary row operation is matrix pre-multiplication
  38. Row equivalence matrix
  39. Equations with row equivalent matrices have the same solution set
  40. Rank of a matrix
  41. Basis of a vector space
  42. Linearly independent set is not bigger than a span
  43. Homogeneous linear equations with more variables than equations
  44. Rank of a homogenous system of linear equations
  45. Condition for existence of BFS in a polyhedron