Revised simplex standard-form linear program

Let $m,n$ be nonnegative integers, $A\in {\mathbb{R}}^{m\times n}$, $b\in {\mathbb{R}}^m$, and $c\in {\mathbb{R}}^n$. The standard-form minimization linear program with data $(A,b,c)$ is $\min \{c^{\mathsf{T}}x:Ax=b,x\ge 0\}\mathrm{.}$ Its feasible set is $P(A,b)=\{x\in {\mathbb{R}}^n:Ax=b,x_j\ge 0\text{ for every }j\}$, and a feasible $x$ is optimal if $c^{\mathsf{T}}x\le c^{\mathsf{T}}z$ for every $z\in P(A,b)$. The notation $x\ge 0$ is componentwise. The revised-simplex basis algorithms on this page require a full-row-rank matrix, meaning $\mathrm{rank}(A)=m$; a rank-deficient raw system must first be reduced by exact row operations, with inconsistent rows reported as infeasible. For $m=0$, the empty system has its usual zero-dimensional interpretation.

A vector $q\in {\mathbb{R}}^m$ satisfying $A^{\mathsf{T}}q\ge 0$ and $b^{\mathsf{T}}q<0$ is called a Farkas infeasibility certificate for this sign convention. Indeed, any feasible $x\ge 0$ would give $b^{\mathsf{T}}q=x^{\mathsf{T}}{A}^{\mathsf{T}}q\ge 0$.