# Basic Feasible solution

Given LPP: $\min c^tx$ subject to $Ax\leq b$, $x\geq 0$, where $rank$ $A_{m\times n}=m$, the SLPP is $\min [c^t$ $0]$$\begin{bmatrix} x \\y \end{bmatrix} subject to [A I_m]$$\begin{bmatrix} x \\y \end{bmatrix}=b$, where $b,x\geq 0, y\geq 0$. Show that $v$ is a BFS of $S$ if and only if $\begin{bmatrix} v \\b-Av \end{bmatrix}$ is a BFS of $S'$, where $S$ and $S'$ are the feasible sets for the LPP and the SLPP.

I have been able to show that BFS of $S$ implies BFS of $S'$, but I am having problem proving the converse. If we consider $w=$$\begin{bmatrix} v \\b-Av \end{bmatrix}_{(n+m)\times 1} to be a BFS of S', then writing w=$$\begin{bmatrix} w_B \\w_C \end{bmatrix}_{(n+m) \times 1}$, where $w_B=B^{-1}b$ and $w_C=0$, we observe that $Cw_C=0$, where $C$ has $n(\geq m)$ columns. Here $[A|I_m]_{m \times (m+n)}$=$[B|C]_{m \times (m+n)}$ and $B$ is the basis matrix of $w_B$. For $v$ to be a BFS of $S$, I think that $b-Av$ should be a component of $w_C$. But I can not come to see how, if at all I am right in being apprehensive here?

$\require{extpfeil} \Newextarrow{\xlf}{5,10}{0x2194}$ $$\cssId{lpS}{(S)} \quad \begin{array}{cc} Ax &\le b \\ x &\ge 0 \end{array} \xlf[\text{add slack variable } y]{} \begin{array}{cc} Ax + Iy &= b \\ x,y &\ge 0 \end{array} \quad \cssId{lpSp}{(S')}$$
Let's see a simpler version first: if $(S')$ has a solution $(x,y)$, you can simply discard $y$ so that $x$ satisfy $(S)$.
Apply this with $x = v$ and $y = b - Av$ to finish the problem.