How to select non-singular new basis in revised simplex

23 Views Asked by At

In revised simplex, as described here (relevant pdf pages 21-23), after pricing phase is done and entering column is known, the ratio test phase is performed by considering non-zero rows of column

$$\alpha_{q} = B^{-1} a_{q} $$

with the goal of determining leaving index $p$ and exchanging $a_{q}$ with $p$th column of $B$:

$$ \bar{B} = B + (a_q - a_{k_p})e^{T}_p$$

By my understanding, this means basis is always expressed as a permutation of columns of the original immutable matrix $A$, however asserting $p$th element of $\alpha_q$ ($q$th column of $A$ multiplied by $B^{-1}$) not being zero does not guarantee $p$th element of $a_{q}$ ($q$th column of $A$) not being zero, which can result in permutation of columns of $A$ that form singular basis when exchange is performed, making refactoring new $B$ into new $B^{-1}$ impossible.

A similar question Revised simplex method: keep basis matrix non-singular exists, unfortunately accepted answer does not address how asserting on elements of $\alpha_{q}$ allows to select for non-zero elements of $a_{q}$ and end up with non-singular basis for subsequent factorization.