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$ contains 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$ contains 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$ contains 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. Bounded section of pointed cone
  2. Representing point in full-rank polyhedron

Info:

Transitive dependencies:

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