Understanding the characterization of extreme points, basic feasible solution

385 Views Asked by At

I believe this is just a small question, but I cannot seem to understand it convincingly. In Bazaraa, Sherali, and Shetty, $3$rd edition, Characterization of Extreme Points theorem says something like:

Given an $m\times n$ matrix $A$ of rank $m$ and an $m$-vector $b$, a point $x\in\mathbb{R}^n$ is an extreme point of $S:=\{x:Ax=b,x\geq0\}$ if and only if $\{1,2,...,n\}$ can be partitioned into two sets $B,N$, where $|B|=m$, such that $A_B$ (matrix obtained by columns of $A$ indexed by $B$ increasingly) is non-singular and $x=\begin{pmatrix}x_B \\ x_N \end{pmatrix}=\begin{pmatrix}A_B^{-1}b \\ 0 \end{pmatrix}\geq0$.


I am confused with the second-to-last equal sign, which is $x=\begin{pmatrix}x_B \\ x_N \end{pmatrix}$. Then, I went to Wikipedia https://en.wikipedia.org/wiki/Basic_feasible_solution#Examples and found an example. After reading through it, I think there is a mistake in the above theorem, and for now I conclude that the above should be written as just

$$\begin{pmatrix}x_B \\ x_N \end{pmatrix}=\begin{pmatrix}A_B^{-1}b \\ 0 \end{pmatrix}\geq0$$

instead of

$$x=\begin{pmatrix}x_B \\ x_N \end{pmatrix}=\begin{pmatrix}A_B^{-1}b \\ 0 \end{pmatrix}\geq0$$.

I mean, the first $x$ must not exist in the first place, because it will mean that our $x$ in the Wiki example will be $x=\begin{pmatrix}x_2 \\ x_4\\x_1\\x_3\\x_5 \end{pmatrix}$, and I am convinced this is not the case. Is my reasoning correct? Any suggestion is appreciated!

EDIT: Forgot to put $|B|=m$.

1

There are 1 best solutions below

12
On BEST ANSWER

Yes, there was an abuse of notation.

$x_B$ need not be the first $m$ entries.

There is a permutation corresponding to $B$ such that

$$P_Bx = \begin{bmatrix}x_B \\ x_N \end{bmatrix}$$