Proof: Characterization of Extreme Points

I'm having trouble adhering to an evidence in guide Nonlinear Programming Theory and Algorithms, Third Edition by Bazaraa, Sherali, and also Shetty on web page 68 area 2.6.4. The evidence is duplicated listed below, approximately the component of the evidence I'm perplexed around.

My inquiry worries the writer is declaration:

But this indicates that $x_{11} = x_{21} = B^{-1}b$.

I do not see just how the writer makes that link.

Theory (Existence of Extreme Points)

Let $S = \{ x : Ax = b, x \geq 0\}$, where $A$ is an m x n matrix and also $b$ is an m - vector. A factor $x$ is a severe factor of $S$ if and also just if $A$ can be decayed right into $[B, N]$ such that

$ x = \begin{bmatrix} x_B \\ x_N \end{bmatrix} = \begin{bmatrix} B^{-1}b \\ 0 \end{bmatrix}$

Proof :

Suppose that $A$ can be decayed right into $[B, N]$ with $x = \begin{bmatrix} B^{-1}b \\ 0 \end{bmatrix}$ and also $B^{-1}b \geq 0$. It is noticeable that $x \in S$. Currently intend that $x = \lambda x_1 + (1 - \lambda)x_2$ with $x_1$, $x_2 \in S$ for some $\lambda \in (0,1)$. Specifically, allow $x^{t}_{1} = (x^{t}_{11}, x^{t}_{12})$ and also $x^{t}_{2} = (x^{t}_{21}, x^{t}_{22})$. After that.

$\begin{bmatrix} B^{-1}b \\ 0 \end{bmatrix} = \lambda \begin{bmatrix} x_{11} \\ x_{12} \end{bmatrix} + (1 - \lambda) \begin{bmatrix} x_{21} \\ x_{22} \end{bmatrix}$

Since $x_{12}, x_{22} \geq 0$ and also $\lambda \in (0,1)$, it adheres to that $x_{12} = x_{22} = 0$. Yet this indicates that $x_{11} = x_{21} = B^{-1}b$ and also therefore $x = x_1 = x_2$. This reveals that $x$ is a severe factor of $S$.

2022-06-07 14:33:07
Source Share
Answers: 1

Note that $x_1,x_2 \in S$ and also therefore $Ax_1 = b$ and also $Ax_2 = b$. Therefore, you get $x_{11} = x_{21} = B^{-1}b$ and also therefore $x_1 = x_2$.

To specify a little bit, given that $x_{1},x_{2} \geq 0$ and also $\lambda \in (0,1)$, we have $x_{12} = 0 = x_{22}$.

Currently, $Ax_1 = b \implies Bx_{11} + Nx_{12} = b \implies B x_{11} = b \implies x_{11} = B^{-1}b$.

In a similar way, $Ax_2 = b \implies Bx_{21} + Nx_{22} = b \implies B x_{21} = b \implies x_{21} = B^{-1}b$.

Therefore, $x_1 = x_2$ and also both amounts to $x$.

2022-06-07 14:51:36