Phase I feasible-basis extraction and infeasibility certificate

Let $D_{ii}=-1$ when $b_i<0$ and $D_{ii}=1$ otherwise. Since $D$ is invertible and $D^{-1}=D$, $Ax=b$ is equivalent to $DAx=Db$, and $Db\ge 0$. The augmented matrix $[DAI]$ has full row rank because it contains the identity columns; $x=0,u=Db$ is feasible for the Phase I problem and has objective ${\mathbf{1}}^{\mathsf{T}}Db\ge 0$.

By [F2] the Phase I primal algorithm terminates at an optimum or an unbounded ray. Its objective is ${\sum }_i{u}_i\ge 0$ at every feasible point, so a negative-cost ray is impossible; it terminates at a minimum with nonnegative reduced costs.

Suppose the minimum $w^{\ast }>0$. Any feasible original $x$ would give a Phase I feasible point $(x,u=0)$ of objective zero, contradicting minimality. Let $y$ be the terminal basis multiplier for the Phase I objective $(0,\mathbf{1})$. Nonnegative reduced costs on the original columns, using [F3], give $(DA{)}^{\mathsf{T}}y\le 0$, and the basic-vector identity gives $(Db{)}^{\mathsf{T}}y=w^{\ast }>0$.

Suppose instead that $w^{\ast }=0$. Since every artificial variable is nonnegative and their sum is zero, each artificial variable has value zero, and the original coordinates satisfy $DAx=Db$. If an artificial variable is basic at tableau row $k$ and some original nonbasic column has a nonzero coefficient in row $k$ of $B^{-1}DA$, pivot that column in. The pivot is nonzero, and the entering variable and leaving artificial variable both have value zero, so the represented feasible point is unchanged and one artificial basic variable is removed.

Set $q=-D^{\mathsf{T}}y$. Then $A^{\mathsf{T}}q=-(DA{)}^{\mathsf{T}}y\ge 0$ and $b^{\mathsf{T}}q=-(Db{)}^{\mathsf{T}}y<0$, so [F4] identifies it as a Farkas certificate. The finite-system alternative [F5] says exactly one of feasibility and such a certificate holds; because this $q$ satisfies the certificate branch, the original system is infeasible.

If no original nonbasic column has a nonzero coefficient in row $k$, every original basic column has a unit column there at a different row, so the entire row $k$ of $B^{-1}DA$ is zero. Every nonbasic artificial variable is zero, every other basic artificial column has zero in row $k$, and the basic artificial value at row $k$ is zero; hence row $k$ of $B^{-1}Db$ is also zero. The transformed equation is $0=0$ and may be deleted without changing the feasible set; deleting that row and its artificial basis column leaves an invertible identity submatrix for the remaining basis.

Each pivot or row deletion removes one artificial basic variable, so after at most $m$ such operations no artificial variable remains basic. The remaining basis consists of original columns and is invertible for the retained row-reduced system; its basic vector is feasible because the represented point never changed. The retained equations are equivalent to the original system by the invertible row operations and deletion only of $0=0$ rows. This proves the zero-optimum extraction claim, including redundant-row removal.