BFS is vertex

Dependencies:

  1. Vertex of a set
  2. Basic feasible solutions
  3. Rank of a matrix
  4. Rank of a homogenous system of linear equations

Let $m$ and $n$ be positive integers. Let $I$ and $E$ be sets such that $I \cap E = \emptyset$ and $I \cup E = \{1, 2, \ldots, m\}$. Let $a_1, a_2, \ldots, a_m$ be vectors in $\mathbb{R}^n$ and $b_1, b_2, \ldots, b_m$ be real numbers. Let $P = \{x: (a_i^Tx \ge b_i, \forall i \in I) \textrm{ and } (a_i^Tx = b_i, \forall i \in E)\}$. Let $\xhat$ be a BFS of $P$. Then $\xhat$ is also a vertex of $P$.

Proof

Let $T = \{i: a_i^T\xhat = b_i\}$. Let $B$ be a matrix whose rows are $\{a_i^T: i \in T\}$. Since $\xhat$ is a BFS, $\rank(B) = n$.

Let $c = \sum_{i \in T} a_i$. Let $y \in P - \{\xhat\}$. Suppose $a_i^Ty = b_i$ for all $i \in T$. Then $B(y - \xhat) = 0$. Since $\rank(B) = n$, $y = \xhat$, which is a contradiction. Hence, $\exists k \in T$ such that $a_i^Ty \neq b_i$. Since $y \in P$, $\exists k \in T \cap I$ such that $a_i^Ty > b_i$. \begin{align} c^Ty &= \sum_{i \in T} a_i^Ty \\ &> \sum_{i \in T} b_i \\ &= \sum_{i \in T} a_i^T\xhat \\ &= c^T\xhat. \end{align} Hence, $c^T\xhat < c^Ty$ for all $y \in P - \{\xhat\}$. Hence, $\xhat$ is a vertex of $P$.

Dependency for:

  1. BFS iff vertex iff extreme point

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