BFS iff vertex iff extreme point

Dependencies:

  1. Extreme point of a convex set
  2. Vertex of a set
  3. Vertex implies extreme point
  4. Basic feasible solutions
  5. Extreme point iff BFS
  6. BFS is vertex

Let $P$ be a polyhedron and $x \in P$. Then $x$ is a BFS of $P$ iff $x$ is an extreme point of $P$ iff $x$ is a vertex of $P$.

Proof

Follows directly from the dependencies.

Dependency for: None

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