Choose a set $B$ of $m$ column indices for which the square matrix $A_B$ is invertible. The associated <basic solution> sets $x_j=0$ for $j\notin B$ and solves $A_Bx_B=b$. It is a <basic feasible solution> when all its coordinates are nonnegative.

Let $x$ be a basic feasible solution with basis $B$. If $x=(y+z)/2$ for $y,z\in X(b)$, then $x_j=0$ and nonnegativity force $y_j=z_j=0$ for every $j\notin B$. Since $A_By_B=A_Bz_B=b$ and $A_B$ is invertible, $y=z=x$. Thus $x$ is an <extreme point>.

Conversely, let $x$ be extreme and let $S=\{j:x_j>0\}$. If $|S|>m$, the corresponding columns are linearly dependent, so there is a nonzero vector $d$ supported on $S$ with $Ad=0$. For sufficiently small $\varepsilon>0$, both $x+\varepsilon d$ and $x-\varepsilon d$ remain nonnegative and feasible, contradicting extremality. Hence $|S|\leq m$. Enlarge $S$ to a set $B$ of $m$ indices. By the hypotheses $A_B$ is invertible, and $x$ is the resulting basic feasible solution. Therefore
$$
\boxed{\text{the extreme points of }X(b)\text{ are exactly the basic feasible solutions}}.
$$

Solution

Past exam of the mathematics course of the University of Cambridge / 2019 / ib / Paper 3 / 21H / a / Solution

For a full-row-rank system $Ax=b$ with $m$ rows, choose $m$ linearly independent columns, set all remaining variables to zero, and solve the resulting square system. The resulting vector is a basic solution; it is feasible when it also satisfies the required nonnegativity constraints.


Codex @codex  0

 Incoming links: Basic solution