[proofplan] We prove the two implications separately. If $x$ is the basic feasible solution associated to a feasible basis $B$, then the equations $Ax=b$ together with the zero conditions outside $B$ determine $x$ uniquely; this uniqueness prevents $x$ from lying in a nontrivial line segment in $P$. Conversely, if $x$ is a vertex, the columns indexed by the positive support of $x$ must be linearly independent, because any linear dependence gives a feasible two-sided perturbation through $x$. Once that independence is known, the support can be extended to a full basis of $m$ columns, and the resulting basis-indexed basic feasible vector is exactly $x$. [/proofplan] [step:Show that a basic feasible solution cannot lie in a nontrivial feasible segment] Assume that $B \subset \{1,\dots,n\}$ is a feasible basis and that $x$ is the basic feasible solution associated to $B$. Define $A_B \in \mathbb{R}^{m \times m}$ to be the submatrix of $A$ whose columns are indexed by $B$, ordered according to the chosen ordering of $B$. For any vector $w \in \mathbb{R}^n$, write $w|_B \in \mathbb{R}^m$ for the subvector whose components are indexed by $B$, ordered according to the chosen ordering of $B$. Let $y,z \in P$ and let $\lambda \in (0,1)$ satisfy \begin{align*} x = \lambda y + (1-\lambda)z. \end{align*} For every $j \notin B$, we have $x_j = 0$, while $y_j \geq 0$ and $z_j \geq 0$. Hence \begin{align*} 0 = \lambda y_j + (1-\lambda)z_j. \end{align*} Since both coefficients $\lambda$ and $1-\lambda$ are positive, this forces $y_j = z_j = 0$ for every $j \notin B$. Because $y,z \in P$, we have $Ay=b$ and $Az=b$. Since the components of $y$ and $z$ outside $B$ vanish, these equations reduce to \begin{align*} A_B(y|_B) = b \end{align*} and \begin{align*} A_B(z|_B) = b. \end{align*} The matrix $A_B$ is invertible, so each of these systems has the unique solution $A_B^{-1}b$. Since $x \in P$ and $x_j=0$ for every $j \notin B$, the same reduction gives $A_B(x|_B)=b$, hence $y|_B=z|_B=x|_B$. Together with $y_j=z_j=0=x_j$ for $j \notin B$, we obtain $y=z=x$. Thus $x$ is a vertex of $P$. [/step] [step:Use vertexhood to force independence of the positive support columns] Assume now that $x \in P$ is a vertex. Define the support index set \begin{align*} S := \{j \in \{1,\dots,n\} : x_j > 0\}. \end{align*} We claim that the family of columns $\{A_j : j \in S\}$ is linearly independent, where $A_j \in \mathbb{R}^m$ denotes the $j$-th column of $A$. Suppose instead that these columns are linearly dependent. Then there is a vector $d \in \mathbb{R}^n$ such that $d \neq 0$, $d_j = 0$ for every $j \notin S$, and \begin{align*} Ad = 0. \end{align*} Since $S$ is finite and $x_j > 0$ for every $j \in S$, choose \begin{align*} \varepsilon := \frac{1}{2}\min\left\{\frac{x_j}{|d_j|} : j \in S \text{ and } d_j \neq 0\right\}. \end{align*} The set over which the minimum is taken is nonempty because $d \neq 0$ and $d$ is supported on $S$, so $\varepsilon > 0$. For $j \notin S$, we have $x_j=0$ and $d_j=0$, so $(x+\varepsilon d)_j=(x-\varepsilon d)_j=0$. For $j \in S$ with $d_j=0$, both components remain equal to $x_j>0$. For $j \in S$ with $d_j \neq 0$, the definition of $\varepsilon$ gives $\varepsilon |d_j| \leq x_j/2$, hence \begin{align*} x_j \pm \varepsilon d_j \geq x_j - \varepsilon |d_j| \geq \frac{x_j}{2} > 0. \end{align*} Thus $x+\varepsilon d$ and $x-\varepsilon d$ are componentwise nonnegative. Also, \begin{align*} A(x+\varepsilon d) = Ax + \varepsilon Ad = b \end{align*} and \begin{align*} A(x-\varepsilon d) = Ax - \varepsilon Ad = b. \end{align*} Therefore $x+\varepsilon d$ and $x-\varepsilon d$ both belong to $P$. They are distinct because $d \neq 0$ and $\varepsilon>0$, and \begin{align*} x = \frac{1}{2}(x+\varepsilon d) + \frac{1}{2}(x-\varepsilon d). \end{align*} This contradicts that $x$ is a vertex. Hence the columns indexed by $S$ are linearly independent. [guided] The goal is to show that the positive coordinates of a vertex cannot carry a linear dependence among their columns. Define \begin{align*} S := \{j \in \{1,\dots,n\} : x_j > 0\}. \end{align*} This set records precisely the coordinates where $x$ has room to move slightly in both positive and negative directions while preserving nonnegativity. Assume, for contradiction, that the columns $\{A_j : j \in S\}$ are linearly dependent. Then there is a nonzero vector $d \in \mathbb{R}^n$ supported on $S$ such that \begin{align*} Ad = 0. \end{align*} Here “supported on $S$” means $d_j=0$ for every $j \notin S$. The equation $Ad=0$ says that moving from $x$ in the direction $d$ does not change the equality constraint $Ax=b$. We now choose the step size small enough to preserve all inequalities. Since $d \neq 0$ and $d$ is supported on $S$, the finite set \begin{align*} \left\{\frac{x_j}{|d_j|} : j \in S \text{ and } d_j \neq 0\right\} \end{align*} is nonempty and consists of positive [real numbers](/page/Real%20Numbers). Define \begin{align*} \varepsilon := \frac{1}{2}\min\left\{\frac{x_j}{|d_j|} : j \in S \text{ and } d_j \neq 0\right\}. \end{align*} Then $\varepsilon>0$. For $j \notin S$, both $x_j$ and $d_j$ are zero, so the perturbed coordinates remain zero. For $j \in S$ with $d_j=0$, the coordinate remains $x_j>0$. For $j \in S$ with $d_j \neq 0$, the choice of $\varepsilon$ gives $\varepsilon |d_j| \leq x_j/2$, so \begin{align*} x_j \pm \varepsilon d_j \geq x_j - \varepsilon |d_j| \geq \frac{x_j}{2} > 0. \end{align*} Thus both $x+\varepsilon d$ and $x-\varepsilon d$ are componentwise nonnegative. They also satisfy the equality constraints: \begin{align*} A(x+\varepsilon d) = Ax + \varepsilon Ad = b \end{align*} and \begin{align*} A(x-\varepsilon d) = Ax - \varepsilon Ad = b. \end{align*} Therefore $x+\varepsilon d \in P$ and $x-\varepsilon d \in P$. These two feasible points are distinct because $d \neq 0$ and $\varepsilon>0$, while \begin{align*} x = \frac{1}{2}(x+\varepsilon d) + \frac{1}{2}(x-\varepsilon d). \end{align*} This writes $x$ as the midpoint of two distinct feasible points, contradicting the definition of a vertex. Hence the columns indexed by $S$ must be linearly independent. [/guided] [/step] [step:Extend the support to a feasible basis] Since $A$ has rank $m$, its columns span an $m$-dimensional subspace of $\mathbb{R}^m$, namely all of $\mathbb{R}^m$. We now prove the finite extension fact needed here. Let $I \subset \{1,\dots,n\}$ be any index set such that $S \subset I$ and the family $\{A_j : j \in I\}$ is linearly independent. If $\operatorname{span}\{A_j : j \in I\}=\mathbb{R}^m$, then $|I|=m$ and we may take $B=I$. If instead $\operatorname{span}\{A_j : j \in I\}\neq \mathbb{R}^m$, then because the full family $\{A_1,\dots,A_n\}$ spans $\mathbb{R}^m$, there is an index $k \in \{1,\dots,n\}$ with $A_k \notin \operatorname{span}\{A_j : j \in I\}$. Hence $k \notin I$, and the family $\{A_j : j \in I \cup \{k\}\}$ is linearly independent: any relation among this enlarged family would solve for $A_k$ as a linear combination of the vectors indexed by $I$, unless the coefficient of $A_k$ were zero, in which case the original independence on $I$ forces all coefficients to vanish. Repeating this finite enlargement process must stop after at most $m-|S|$ additions, because a linearly independent family in $\mathbb{R}^m$ has at most $m$ elements. It stops only when the span is $\mathbb{R}^m$. Thus there exists a set $B \subset \{1,\dots,n\}$ such that $S \subset B$, $|B|=m$, and the submatrix $A_B \in \mathbb{R}^{m \times m}$ of $A$ whose columns are indexed by $B$ is invertible. Because $S \subset B$, every coordinate of $x$ outside $B$ is zero. For any vector $w \in \mathbb{R}^n$, write $w|_B \in \mathbb{R}^m$ for the subvector whose components are indexed by $B$, ordered according to the chosen ordering of $B$. Since $x \in P$, we have $Ax=b$, and therefore \begin{align*} A_B(x|_B) = b. \end{align*} Define the basis vector $\bar{x}_B \in \mathbb{R}^n$ associated to $B$ to be the unique vector with $(\bar{x}_B)_j=0$ for $j \notin B$ and $A_B(\bar{x}_B|_B)=b$. Since $x$ has these same outside-$B$ zero coordinates and satisfies the same invertible linear system on $B$, uniqueness gives $x=\bar{x}_B$. Moreover $\bar{x}_B=x \in P$, so $B$ is a feasible basis. Hence every vertex of $P$ is a basic feasible solution for some feasible basis. [/step] [step:Combine the two implications] The first step proves that every basic feasible solution associated to a feasible basis is a vertex of $P$. The second and third steps prove that every vertex $x \in P$ is the basic feasible solution associated to a feasible basis obtained by extending the support of $x$. Therefore a point $x \in P$ is a vertex of $P$ if and only if $x$ is a basic feasible solution for some feasible basis. [/step]