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/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. Inner product space
  13. Vertex of a set
  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