Phase I revised simplex and rank reduction

Input any exact equality system $Ax=b$ with $x\ge 0$, including a rank-deficient raw system. Let $D$ be diagonal with $D_{ii}=-1$ when $b_i<0$ and $D_{ii}=1$ otherwise; set $\tilde{A}=DA$ and $\tilde{b}=Db\ge 0$. Add artificial variables $u\in {\mathbb{R}}^m$ and solve the Phase I problem $\min {\mathbf{1}}^{\mathsf{T}}u$ subject to $\tilde{A}x+u=\tilde{b}$, $x,u\ge 0$, starting at $x=0,u=\tilde{b}$ with artificial basis $I_m$. Use the exact primal algorithm of Primal revised simplex with Bland's rule and its finite-termination result Bland-rule finite termination and optimal-basis existence.

At a terminal optimum, if ${\mathbf{1}}^{\mathsf{T}}u>0$, return infeasible and the basis multiplier $y$ for the Phase I objective. If the optimum is zero, set every artificial variable to zero and remove artificial basic variables as follows. For a zero-valued artificial basic variable, inspect its row in $B^{-1}\tilde{A}$. If some original nonbasic column has a nonzero coefficient there, pivot the least-index such column into the basis; the pivot may have either sign because the leaving basic value is zero. If no such coefficient exists, and the transformed right-hand-side entry is zero, delete that redundant equation and its zero artificial basic variable. Repeat until all remaining basic columns are original; return the row-reduced equivalent system and its original feasible basis. A zero row with nonzero transformed right-hand side returns inconsistent-row. All tests are exact; a finite-precision near-zero objective is not treated as zero.